Expression Trees

For programming project 5, you will implement a class to store and evaluate expression trees. An example of an expression tree is as follows: See image.

The content of this tree can be displayed as a fully parenthesized expression in the form: ( ( x * y ) + ( ( 10 * x ) / y ) ). Your task is to design and implement a binary tree class to store binary expression trees called exprTree. Your expression tree class must provide at least the following functionality:

constructor() This method creates an empty expression tree.

constructor( String operand ) This method receives a string representing the label of an operand and constructs an expression tree. Example: “x”

constructor( Integer operand ) This method receives an integer representing an integer operand and constructs an expression tree. Example: 10

exprTree add ( exprTree t2 ) This method combines copies of the content of two expression trees to form a new expression tree with a root node containing a plus (+) operator and a left subtree containing the a copy of “this” expression tree and a right subtree containing a copy of expression tree t2.

exprTree subtract ( exprTree t2 ) exprTree multiply ( exprTree t2 ) exprTree divide ( exprTree t2 ) These member functions should perform the same sequence of actions described for the add method, but insert a different operator (-, * or /) as the value of the root node.

void displayInfix() This member function should display the tree using an inorder traversal. During the display, insert parentheses to print a fully parenthesized infix expression. Example: ( ( x * y ) + ( ( 10 * x ) / y ) )

void displayPrefix() This member function should display the tree using a preorder traversal. Example: + * x y / * 10 x y

void displayPostfix() This member function should display the tree using a postorder traversal. Example: x y * 10 x * y / + + * x y / 10 y x *

void displayTree() This method should display the tree using indentation and symbols (|,=) to represent the preorder tree structure. Make sure to display exactly 5 equal symbols when displaying a line (e.g. “=====”) and use spaces not tabs to indent items. Example:

+
|===== *
| |===== x
| |===== y
|===== /
|===== *
| |===== 10
| |===== X
|===== y

int numberOfOperators( ) This method should return the number of operators in the tree by traversing and counting the interior nodes. Example: 4

int numberOfOperands( ) This method should return the number of operands in the tree by traversing and counting the leaf nodes. Example: 5

boolean isEqual( exprTree t ) This method should return true if “this” expression tree and t contain the same expressions.

boolean isNotEqual( exprTree t ) This method should return true if “this” expression tree and t contain different expressions.

You are free to add additional public and/or private methods as needed.

The following example illustrates the use of the exprTree class.

void main()
{
exprTree t, t1(“x”), t2(“alpha”), t3(10);
t = t1.add( t2 );
t.displayInfix(); // ( x + alpha )
t = t .multiply( t1.divide( t3 ) );
t.displayInfix(); // ( ( x + alpha ) * ( x / 10 ) )
t.displayPrefix(); // * + x alpha / x 10
t.displayPostfix(); // x alpha + x 10 / *
t.displayTree();

/*
displays:
*
|===== +
| |===== x
| |===== alpha
|===== /
|===== x
|===== 10
*/
System.out.println ( t.isEquals( t ) ); // display true
System.out.println ( t.isNotEquals( t ) ); // display false
System.out.println ( t.numberOfOperators() ); // 3
}

Extra Credit:

Provide a method to evaluate the expression tree. This method should have the form:

int evaluate() The method should prompt the user to provide a value for each labeled operand (e.g. x, y, …) and then compute the value of the tree. For example to evaluate the expression tree containing ( ( x * y ) + ( ( 10 * x ) / y ) ) your function should prompt the user for values for x and y:

Enter x: 3
Enter y: 2

And then compute the value of the expression e.g. ( ( 3 * 2 ) + ( ( 10 * 3 ) / 2 ) ) -> ( 6 + ( 30 / 2 ) -> ( 6 + 15 ) -> 21

On the assigned due date submit two source files named project5.java and exprTree.java. The exprTree.java should contain the implementation of the class exprTree. The project5.java should contain the code you used to test the implementation of the exprTree class. Make sure there is a comment at the top of each file listing your name, your instructor’s name and your GTA’s name