In java programming language Question 2: Expression Trees Read through all of the instructions for question 2 before beginning. You will use an expression tree to store and manipulate algebraic expressions. Your expression tree will be constructed from nodes, as described below. Examples of expression trees are shown in Figure 8.11 of Lafore, and in Introducing Trees in the Unit 6 notes. Some additional examples of expression trees are + * * / \ / \ / \ A - A ^ + - / \ / \ / \ / \ B C B + A B C D / \ C D (A+(B-C)) (A*(B^(C+D))) ((A+B)*(C-D)) One advantage of postfix and prefix notations is that parentheses are not needed to specify order of operations. In this question you will create expression trees from both postfix and prefix forms of algebraic expressions. You will also simplify the expression trees and print infix, postfix, and prefix versions of the expressions stored in the trees. Your program will read commands from a file and output the result of executing those commands. Input The input file will consist of one command per line, where the command will be one of the 6 options below. If additional information is needed, it will follow on the same line. Possible commands are: COMMENT A line beginning with COMMENT should be echoed to the screen. No manipulation of the tree is required. NEW A line beginning with NEW will construct a new expression tree. Any existing tree will be discarded and replaced with the new tree. The expression that follows NEW will be either prefix or postfix notation. Your program should be able to determine which notation is used. All operands and operators will be separated by spaces, so that you may split the line read from file into tokens, where each token contains a String that will correspond to a node in the tree. Output a single statement, New tree constructed, when a tree is successfully created. Please see the sections below on constructing expression trees for some hints on how to read in expressions and construct trees. PRINTPREFIX A line beginning with PRINTPREFIX will print the current tree using prefix notation. Similar to the prefix notation used when reading from the input file, separate all operands and operators with a space. PRINTPOSTFIX A line beginning with PRINTPOSTFIX will print the current tree using postfix notation. Similar to the postfix notation used when reading from the input file, separate all operands and operators with a space. PRINTINFIX A line beginning with PRINTINFIX will print the current tree using infix notation. Infix notation requires parentheses to indicate order of operations, and you will print a fully parenthesized expression, where each operand-operator-operand is enclosed in parentheses. Examples of fully parenthesized expressions are ( ( 8 + 6 ) * ( 4 - 5 ) ) and ( ( ( B + 5 ) * 4 ) ^ 3 ). SIMPLIFY A line beginning with SIMPLIFY will simplify the current tree as much as possible, following common arithmetic rules, and output the statement Tree simplified when complete. Traverse the tree and stop to consider each node containing an operator. Look at the subtree consisting of the operator node and its left and right subtrees, and simplify where possible. Some examples to get you started: If both children of an operator are numeric values, perform the operation and replace that subtree with the result stored in a single node. A * 1 = A. If the operator is * and one of the children is 1, replace the subtree with the other child. A * 0 = 0. If the operator is * and one of the children is 0, replace the subtree with 0. A 1 = A. If the operator is and the right child is 1, replace the subtree with the left child. Nodes for Expression Trees The nodes in the expression tree will have the ability to hold three types of information: operators, variables, or constants. Possible operators will be +, -, *, and . We will omit division so that we can deal only with integers. Variables will be a string of any number of alphabetic characters (e.g. A, first, cat). Constants will be integers. The fields in your nodes should be: A type that identifies the node as an operator, variable, or a number. Something similar to enum NodeType{OPERATOR, VARIABLE, NUMBER;} is appropriate. A character that will store the operator for operator nodes. The only valid characters are +, -, *, and . A String that will store the variable name for variable nodes. An integer that will store the value for number nodes. Two Node references, that refer to the left child and the right child. For leaf nodes these will be null. The Expression Tree Class Your expression tree class must have methods that allow it to carry out the expected commands. Recursion should be used as appropriate. While the tree class from question 1 gives you an idea of how to manipulate tree objects, note that expression trees are sufficiently different that you should write a new class rather than trying to modify the class from question 1. A Queue to store Nodes You will need a queue of nodes to aid in the construction of an expression tree from prefix notation. This queue should be similar to the queue in question 1, except that the nodes stored are now nodes from your expression tree rather than nodes that contain only an integer. Hint: If you name your node classes Node in both questions, and use good coding practices, you should be able to use the Queue class from question 1 without modification. A Stack to store Nodes You will need a stack of nodes to aid in the construction of an expression tree from postfix notation. Create a Stack class where each item stored in the Stack is a Node. As for the Queue class, you may choose the underlying implementation for your stack that you think is most appropriate (e.g. linked list or array). The implementation that you choose should be hidden from a user of the class. That is, the user will push and pop Nodes, and will not know how they are managed inside the stack. Your stack must have the following methods: A constructor that creates an empty stack. A boolean isEmpty() method that returns a boolean, indicating whether the stack is empty. A boolean push(Node toAdd) method that will insert the given Node into the stack. This method will return true if the push is successful, and return false if the push fails. A Node pop() method that will pop and return the Node on the top of the stack. This method removes the returned Node from the stack. This method should return null if the user tries to pop from an empty stack. A Node peek() method that returns the Node on the top of the stack. This method does not remove the returned Node from the stack. This method should return null if the user tries to peek at an empty stack. Constructing An Expression Tree From Postfix Notation Constructing an expression tree from postfix notation is discussed in Lafore, on page 387-388. Also see the comments on solving postfix expressions in Introducing Trees of the Unit 6 online notes. Using a stack of nodes to temporarily store subtrees, you will construct an expression tree from postfix notation. As you process the expression from the input file, consider one token at a time, create a node of the appropriate type and proceed as appropriate, either (i) pushing the node onto the stack or (ii) popping nodes, creating a larger subtree, and pushing that onto the stack. Note that if you push the root of a subtree onto the stack and the child references are appropriately set, you are effectively pushing the entire subtree onto the stack. In the comments of your postfix-to-tree method, in one paragraph, describe the algorithm you use to construct an expression tree from postfix notation. Constructing An Expression Tree From Prefix Notation To constuct an expression tree from prefix notation, make use of a queue of nodes to temporarily store subtrees as you build the full tree. See the comments on solving prefix expressions in Introducing Trees of the Unit 6 online notes to help you get started on designing your algorithm. Hint: Note that while operator nodes should always have two non-null children in a valid tree, you will sometimes want to queue operator nodes temporarily without children while building the tree. In the comments of your prefix-to-tree method, in one paragraph, describe the algorithm you use to construct an expression tree from prefix notation. Your Main Class (please name it A3Q2) Write a main method that will process commands, as described above, until the end of file. You may assume that the data file will be named A3Q2input.txt. Sample program input: COMMENT Starting tests... NEW C 3 + 5 4 - * PRINTINFIX SIMPLIFY PRINTINFIX PRINTPOSTFIX PRINTPREFIX COMMENT End of tests. Sample program output: Starting tests... New tree constructed ( ( C + 3 ) * ( 5 - 4 ) ) Tree simplified ( ( C + 3 ) * 1 ) C 3 + 1 * * + C 3 1 End of tests. Additional Notes You may assume that the input file is free of errors. That is, you may assume that the file contains one command per line, that all tokens within a line will be separated by a space, and that only valid commands are provided. You may also assume that given expressions are valid expressions (i.e. the number and order of operands and operators are such that they construct a valid algebraic expression). Official test data will be provided one week before the due date. Until then, create your own test data.