Your assignment is build a data structure that represents a mathematical equation, and you$$ll

use the Calculator that you built in Homework #$2.$ You already have a method that converts

user input into a postfix expression. This time, you will take the postfix expression and convert

it into an expression tree. The exact implementation is left up to you, though you must read

input from the console$/$terminal$.$

After you create the tree, you should do preorder, inorder, and postorder traversals in order

to print prefix, infix $($with appropriate parenthesis$),$ and postfix expressions representing the

input. Your application should be able to handle multiple inputs before exiting $($ie via Ctrl$-$C$)$;

after printing the results, it should ask for a subsequent infix expression on the console.

You can assume that only valid infix expressions $($bracket balanced$)$ will be used as inputs.

Your console should do the following when the user types in an expression $-$

$1.$ convert infix to postfix $($same as hw$2)$

$2.$ convert postfix to expression tree

$3.$ print all three traversals

Results from Step $1$ and $2$ should not be printed out as outputs. Only the tree traversals

should be printed.

Expression Trees

An expression tree is a data structure used to represent an arithmetic expression. There are

two types of nodes in an expression tree: operators and numbers. Number nodes are leaves

and have no children. Operator nodes have two children that are also expression trees $($each

child can be an operator or a number$).$ For example, the expression $(4-2)$ will be represented

by an expression tree with a root operator node. It'll store the fact that it's the subtraction

operator, and it will have two children, each number nodes $4$ and $2.$

A more complicated expression will have more nodes associated with it$.$ Consider the

expression $(9+6*2/(8-3)).$ This expression is the sum of two other expressions, so the root will

be an operator node, with operator $"+",$ and two child expressions. The left child will be the

leaf node with number $"9",$ but the right child is going to be an operator node with operator

$"/".$ It's children are also operator nodes: the left child is $6*2$ and the right child is $8-3.$

Tips for Getting Organized

The first step you should take is to figure out how to represent an expression tree in Java. A

class that represents a node in an expression tree has already been provided $($Node$.$java$).$ Try

creating some expression trees manually, and make sure that you can represent the full variety

of arithmetic expressions that can be handled by your original calculator. Once you've done

that, you'll need to build four methods in your expression tree class:$-$

Required Methods

These methods should be present in the expression tree class$($ExpressionTree$.$java$)$ Note: You

may use whatever method signatures you like.

buildTree$(),$ which takes a postfix expression as input and creates an expression tree out

of it

prefix$(),$ a preorder traversal of the tree

infix$(),$ an inorder traversal of the tree

postfix$(),$ a postorder traversal of the tree

Once these methods are built, they will need to be called in Main.java $($input console class$)$

so the results get printed on each input.

Algorithm to build expression tree

The algorithm for converting a postfix expression into an expression tree is similar to some of

the other conversion algorithms that you've done. Here are the steps:

$1.$ Create an empty stack. Each element in the stack is going to be an expression tree

node, so set the generic type accordingly.

$2.$ Loop through each token in the postfix expression created by your converter.

a$.$ If the token is a number, create a new expression tree node that represents

just that number and push it onto the stack

b$.$ If the token is an operator, create a new operator expression node. Pop two

expression nodes off the top of the stack, and set them as children of this new

node. Then push this operator node onto the stack

$3.$ Once all the tokens in the postfix expression have been processed, the stack will contain

only one expression tree node. Pop it out, and return it$.$

Console Output

Type your expression:

$3*4+5$

Prefix: $+*345$

Infix: $((3*4)+5)$

Postfix: $34*5+$

Other Notes

Unlike previous homeworks, you should write your own Main file and submit it$.$ Students

should ensure that their input method can run indefinitely and only exiting the

console$/$terminal $($Ctrl$+$C$)$ should exit the program. Graders will run the program on console

only, not on IDE.

It is recommended to use the ArrayStack class, but it not necessary. Students can use the

inbuilt Java Stack as well.

Remember: postorder traversal of a tree prints the children of the node first, and then

prints the data inside the node. Preorder traversal prints the node data first. When printing

out these traversals, no parenthesis are needed.

Inorder traversal will print the left child, followed by the operator, followed by the right child.

The result should look very simil