Expression Trees

The Goal

Your task is to write a Java program that reads a text file with one math expression per line, written in Reverse Polish Notation. It will transform each line into an expression tree, print out that expression in a more familiar form, and evaluate the expression to find its value.

Reverse Polish Notation

Our first challenge is representing an expression in a way that we can easily parse. Standard math expressions like "1 + 2 - 3 / 4" can be difficult to process, as we need additional precedence rules to determine which operations should be performed first. This type of notation is known as in-fix notation, which means that the operator appears between the operands.

Since in-fix notation can be tricky to parse, we'll be parsing expressions that are written in post-fix notation(also known as Reverse Polish Notation (Links to an external site.)Links to an external site. or RPN). In this form, the operator comes after the operands. For example:

"1 + 2" is written as "1 2 +" in post-fix notation

"1 + 2 - 3 / 4" is written as "1 2 3 4 / - +" in post-fix notation

While this notation may seem strange at first, it is much easier to parse, as it does not need precedence rules or parentheses: the order of operations is specified entirely by the expression itself.

What to Do

Part I: Building the Expression Tree

Each node of our expression tree will store a String, representing either a value (a numeric string), or an operator (+, -, *, or /). For example, the following tree represents the in-fix expression "(((3 + 1) * 4 ) / ((9 - 5) + 2))", which is the post-fix expression "3 1 + 4 * 9 5 - 2 + /":

First, we need to convert an RPN expression into an expression tree. Create a class ExpressionTreeHelper, and add a static method with the following signature:

public static TreeNode expressionTreeFromRPN(String rpnString)

Use the following pseudocode to convert an RPN expression into an expression tree:

expressionTreeFromRPN(String rpnString): let S be a stack of TreeNodes tokens = an array of strings in rpnString, separated by whitespace for each token in tokens: if token is a number: push a new leaf node to S, with token as its value else str is an operator: right = S.pop left = S.pop push a new node with left and right as children, and token as its value return S.top

This processes an RPN expression with the following ideas. If a token is a numeric value, we create a leaf node for it. If a token is an operator, it should be an internal node. It must have been preceded by two expressions, which occupy the previous two locations on our stack, so we use those two expressions as children.

Hint: to split a string into tokens there are several methods. One approach is to use a Scanner (see the constructor Scanner(String) here (Links to an external site.)Links to an external site.). Another approach is to use String methods (see the split method here (Links to an external site.)Links to an external site.).

Part II: Printing Out an Expression Tree

Once we have an expression tree, we would like to be able to print it out in a more human-readable form using in-fix notation. Add a static method printExpressionTree to our ExpressionTreeHelper class, which takes an expression tree as a parameter, and returns nothing.

This should be a recursive method with two cases:

If the node is a leaf, just print out the value.

If the node is internal, join the left and right trees with the given operator: "( )"

Hint: this is very similar to the in-order traversal method we wrote in class.

Part III: Evaluating the Expression

We can evaluate the expression tree using a similar traversal. Instead of just printing out the expression, we can calculate the values of each child tree and combine them using the provided operation. Add a static method evaluateExpressionTree to our ExpressionTreeHelper class, which takes an expression tree as a parameter, and returns a double.

This should be a recursive method with two cases:

If the node is a leaf, return the value as a double (Hint: use a method from the Double wrapper class (Links to an external site.)Links to an external site.)

If the node is internal, calculate the values of its children, then combine them using the specified operator. Hint: a switch-case statement is a good way to choose which operator to apply.

Part IV: Putting It All Together

Lastly, create a Driver class with a main method. This method should do the following:

Read each expression from a given file (each line is a single expression)

For each expression:

Create an expression tree (using the method from Part I)

Print out that expression in in-fix notation (using the method from Part II)

Print out the value of that expression (using the method from Part III)

Here is a sample input and output file to test on:

sampleInput.txt

1 2 + 1 2 + 4 5 - - 1 2 / 1 2 / / 1 2 3 4 5 6 * * * * * 3 1 + 4 * 9 5 - 2 + /

sampleOutput.txt

(1 + 2) = 3.0 ((1 + 2) - (4 - 5)) = 4.0 ((1 / 2) / (1 / 2)) = 1.0 (1 * (2 * (3 * (4 * (5 * 6))))) = 720.0 (((3 + 1) * 4) / ((9 - 5) + 2)) = 2.6666666666666665

What to Submit

When you have completed the assignment, submit all project files to Canvas. These should include:

Driver.java

ExpressionTreeHelper.java

TreeNode.java

? 4 2