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. 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 Refer to the previous assignments if you forgot. 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. 

BXT.txt

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 inorder string and a preorder string. **********************/ class BXT { private int count; private TreeNode root; public BXT() { count = 0; root = null; } /* enter your instance methods here. buildTree, display, inorderTraverse, preorderTraverse, evaluateTree */

}

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: "); tree.inorderTraverse(); System.out.print(" Prefix order: "); tree.preorderTraverse(); 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; } }