In this assignment you will write a program that will take a mathematical expression written in post-fix notation and generate an expression tree

In this assignment you will write a program that will take a mathematical expression written in post-fix notation and generate an expression tree from it. Normally, we use what's called in-fix notation like: 1 + 1. Post-fix puts the operator after the two numbers like: 1 1 +. An expression tree is a type of binary tree that has the operators as parents of the two values that go into them.

Your program must do the following in order to receive full credit on this assignment.

1. Download the attached java files and get them into your project and ensure they compile.
2. In the Utilities class, the isOperator method is a stub from the interface. Implement this
3. method.
4. The parameter s can be any string. This method should return true if s is any of
5. the five basic operators.
6. That is the method returns true if s is + or - or * or / or %. Otherwise it will return
7. false.
8. Also in the Utilities class, the allValidTerms method from the interface is also a stub.
9. Implement this method as well.

a. In order for this method to return true, every element must be either a number or

an operator. If any of them are not, it should return false.

1. Create a new class called NumberNode. This class will represent a leaf node at the
2. bottom of the tree. It must implement the Node interface.
3. NumberNode only needs an int value for an instance variable. It should have one
4. constructor which takes an int parameter and stores it as this Node's value.
5. You will have to implement all methods from the Node interface.

a. Since a NumberNode does not have any children, what value should getLeft and getRight return?

7. Create a new class called OperatorNode, which represents the operators stored in the tree with two Nodes under it. This should also implement the Node interface.

1. This will need a string instance variable to hold its operator.
2. It will also need one for each Node under it.

i. What type should these be?

8. As with NumberNode, implement the methods from the Node interface.

a. The tricky one this time is getValue. We don't have an int value to return. What do we do when when a class inherits or implements a method that it does not support?

9. As always when dealing with user input, we have no idea what they will give us. They might give us garbage, so we will need some error handling. While there are other potential ways to handle these, we will be using exceptions. To start, create a new class called OperatorOnlyException. This exception will be thrown when the user provides an expression that is only operators with no numbers in it.

1. This class must inherit from RuntimeException in order to be thrown.
2. Note: Some compilers may issue a warning that you have not defined a final static
3. long serial number. This comes from serialization and can be ignored. You can also just define a serial number, add an annotation to suppress the warning (@suppressWarnings("serial")), or change your compiler settings to not warn you about that.
4. Define a default constructor for this class. It should generate a message that an expression cannot be only operators.
5. See example outputs.
6. Since you are inheriting from RuntimeException, you inherit everything from that
7. class. The constructor can be as short as one line. Look up the constructors for
8. RuntimeException and remember how inheritance works to find the shortcut.
9. Create another class called InvalidExpressionException.

a. b.

12. In the a. b. c.

This also must inherit from RuntimeException.

Again, create a single default constructor that generates a message that the expression is invalid.

ExpressionTree class implement a new method called parseExpression.

It is public and does not return a value.

It takes an array of strings as a parameter.

It can throw either of the exceptions we've defined, but it will also possibly throw an EmptyCollectionException as we'll soon see, so be sure to add a throws clause for all three of these.

13. Before we can try to parse the expression, we must first check if we even can. There are several possible situations we need to check for.

a. If the entire expression is operators, throw an OperatorOnlyException.

i. The rest of these situations will throw an InvalidExpressionException.

1. If it starts with an operator.
2. If the expression is even in length, it cannot be valid.

i. Might sound odd but think about it. d. If there are any invalid terms.

1. Having eliminated all of those possibilities, if the expression is one term long, we can just create a new NumberNode with it and set it as our root and be done.
2. Otherwise, parse the expression into the tree.
3. The built in Stack class is imported for you. Think of how you can use it to track
4. what will be the children of your next operator node.
5. Remember, the pattern should be number number operator. After that initial part,
6. the only thing that can be added would be another number followed by another operator. You can't be sure how many times this pair will repeat, but that will be the pattern.

i. Keep in mind, the left child of one of these pairs would be the OperatorNode from the previous set.

c. You should assume that this is the pattern you are given. There is a scenario that passes the above checks, but should cause you to pop from an empty stack. This is what causes the EmptyStackCollection exception to be thrown. Think about what

that scenario would be as it might help you figure out how to use the stack if

you're not sure yet.

d. At the end make sure the top Node is set as the root.

16. Implement a way to do an in-order traversal of the expression tree to generate the in-fix notation version of the expression.

a. You have two basic choices for doing this. You can write new method in ExpressionTree that will do it (recursion will help) or you can implement the provided toString method stub (This will instead have you implement toString methods in your Node classes). The choice is yours.

17. In the Assignment12 class, complete the main method to try and parse the expression.

1. Insert your code at the provided spot, there should be no need to edit anything
2. above or below that point.
3. Make sure you catch all the potential exceptions!
4. For each, print "Error!" followed by the message from the exception, and then further explain and ask the user to try again.
5. See example outputs.
6. If you parse it successfully, then print out the in-fix notation version of the
7. expression.

Example Inputs