For this assignment, we will build a binary expression tree, display it, and evaluate it. This time, we will encapsulate the behavior in a BXT class. The driver class, tree node, as well as the BXT class are provided. Please implement appropriate methods in BXT class to build, display and evaluate a tree. Let's also allow decimal input and output, and negative numbers. For simplicity, all tokens in the input string be separated by a space. 

Sample run

Postfix Exp: 14 -5 / BXT: -5 / 14 Infix order: 14 / -5 Prefix order: / 14 -5 Evaluates to -2.8 ------------------------

Postfix Exp: 20 3 -4 + * BXT: -4 + 3 * 20 Infix order: 20 * 3 + -4 Prefix order: * 20 + 3 -4 Evaluates to -20.0 ------------------------

Postfix Exp: 2 3 + 5 / 4 5 - * BXT: 5 - 4 * 5 / 3 + 2 Infix order: 2 + 3 / 5 * 4 - 5 Prefix order: * / + 2 3 5 - 4 5 Evaluates to -1.0 ------------------------

Build a BXT You need to change the string into a tree. Hint1: In a postfix string the operator is preceded by two operands (numbers). This suggests a stack of TreeNodes would be useful. Hint 2: Each operator is a TreeNode with two children. Hint 3: If the token is an operator, do what? Else it's a number, so do what? Display Infix and Prefix orders Infix is characterized by the placement of operators between operands; Prefix expression notation requires that all operators precede the two operands that they work on; Postfix requires that its operators come after the corresponding operands. See following examples: Infix Expression Prefix Expression Postfix Expression A + B + A B A B + A + B * C + A * B C A B C * + Evaluating the Expression Do this recursively. If the node is an operator, recursively evaluate the left child and the right child, and return the result. Else the node is a number, so it can be converted into a double, and returned. Print the infix order with parentheses.

given

BXT.txt

/** INSTRUCTION * Create a class named BXT.java then copy and past the content */ import java.util.*; /******************* Represents a binary expression tree. The BXT can build itself from a postorder expression. It can evaluate and print itself. It also prints an infix string, a prefix string and a postfix. **********************/ class BXT{ private int count; //will be used in another assignment if we have time private TreeNode root; public BXT(){ count = 0; root = null; } public void buildTree(String str){ //TO DO } public double evaluateTree(){ //To DO } public String display(){ //TO DO } public String infix(){ //TO DO }

public String prefix(){ //TO DO } public String postfix(){ //TO DO }

}

BXTDriver.txt

/*******************

Driver for a binary expression tree class.

Input: a postfix string, each token separated by a space.

**********************/

public class BXTDriver{

public static void main(String[] args){

ArrayList postExp = new ArrayList();

postExp.add("14 -5 / ");

postExp.add("20 3 -4 + * ");

postExp.add("2 3 + 5 / 4 5 - *");

for( String postfix : postExp ){

System.out.println("Postfix Exp: " + postfix);

BXT tree = new BXT();

tree.buildTree( postfix );

System.out.println("BXT: ");

tree.display();

System.out.print("Infix order: ");

System.out.println( tree.infix());

System.out.print(" Prefix order: ");

System.out.println( tree.prefix());

System.out.print("Postfix order: ");

System.out.println( tree.postfix() );

System.out.print(" Evaluates to " + tree.evaluateTree());

System.out.println( " ------------------------");

}

}

}

/***************************************

Postfix Exp: 14 -5 /

BXT:

-5

/

14

Infix order: 14 / -5

Prefix order: / 14 -5

Evaluates to -2.8

------------------------

Postfix Exp: 20 3 -4 + *

BXT:

-4

+

3

*

20

Infix order: 20 * 3 + -4

Prefix order: * 20 + 3 -4

Evaluates to -20.0

------------------------

Postfix Exp: 2 3 + 5 / 4 5 - *

BXT:

5

-

4

*

5

/

3

+

2

Infix order: 2 + 3 / 5 * 4 - 5

Prefix order: * / + 2 3 5 - 4 5

Evaluates to -1.0

------------------------

*/

TreeNode.txt

public class TreeNode{ private Object value; private TreeNode left, right; public TreeNode(Object initValue){ value = initValue; left = null; right = null; } public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight){ value = initValue; left = initLeft; right = initRight; } public Object getValue(){ return value; } public TreeNode getLeft() { return left; } public TreeNode getRight(){ return right; } public void setValue(Object theNewValue){ value = theNewValue; } public void setLeft(TreeNode theNewLeft){ left = theNewLeft; } public void setRight(TreeNode theNewRight){ right = theNewRight; } }