Question

For this assignment you will write a class that transforms a Postfix expression (interpreted as a sequence of method calls) into an expression tree, and provides methods that process the tree in different ways.

We will test this using our own program that instantiates your class and calls the expected methods. Do not use another class besides the tester and the ExpressionTree class. All work must be done in the class ExpressionTree. Your class must be called ExpressionTree and have the following public methods:

public class ExpressionTree {

    public void pushNumber(double d);
    public void pushAdd();
    public void pushMultiply();
    public void pushSubtract();
    public void pushDivide();

    public double evaluate();
    public String infixString();

    public int height();        
    public void clear();

    // For bonus:
    // public void pushVariable();
    // public void evaluate(double variableVal);

}

Required methods

The methods should behave as follows:

1. pushNumber(double d) should push a node containing a number to the internal stack.
2. push (Add,Multiply,Subtract,Divide) should push a node representing the corresponding operation.
3. infixString() should return a String containing a parenthesized inorder traversal of the expression tree. Note: this should interpret the top of the internal stack as the root of the tree.
4. evaluate() should return the numeric value associated with the tree. This must operate recursively on the expression tree. Note: this should interpret the top of the internal stack as the root of the tree.
5. height() should return the height of the expression tree (distance in edges between the root and the farthest leaf). Note: this should interpret the top of the internal stack as the root of the tree.
6. clear() should reset the internal Stack

//////////TESTER CLASS THAT THE EXPRESSION TREE CODE MUST WORK WITH/////////////

public class ETreeValidator {
    public static void main(String[] args) 
    {
        ExpressionTree etree = new ExpressionTree();

        etree.pushNumber(10);
        etree.pushNumber(20);
        etree.pushOp("+");

        System.out.println("Expecting (10.0 + 20.0): " + etree.infixString());
        System.out.println("Expecting 30.0: " + etree.evaluate());
        System.out.println(("Expecting 1: " + etree.height()));

        etree.clear();

        
        etree.pushNumber(10);
        etree.pushNumber(20);
        etree.pushOp("+");
        etree.pushNumber(5);
        etree.pushNumber(3);
        etree.pushNumber(1);
        etree.pushOp("*");
        etree.pushOp("-");
        etree.pushOp("/");

        
        System.out.println("Expecting ((10.0 + 20.0) / (5.0 - (3.0 * 1.0))): " + etree.infixString());
        System.out.println("Expecting 15.0: " + etree.evaluate());
        System.out.println(("Expecting 3: " + etree.height()));
        etree.clear();
        
        // Uncomment this if you did the bonus
        etree.pushNumber(1.5);
        etree.pushNumber(12);
        etree.pushVariable();
        etree.pushOp("/");
        etree.pushOp("*");
        etree.pushVariable();
        etree.pushOp("-");
        System.out.println("Expecting ((1.5 * (12.0 / VAR)) - VAR): " + etree.infixString());
        System.out.println("Expecting 7: " + etree.evaluate(2));
        System.out.println(("Expecting 3: " + etree.height()));
        


    }
}

Answer 1

Data Structures used : stack, tree; A String variable is used to exp is used to maintain the string representation of given postFix expression, so that, it can be used while calculating other values easily; Tree is constructed only when calculating height all the other values are calculated using stack only.

Pushing an operator, operand or variable on top of Stack: The String representation is pushed on top of stack. Along with pushing the element on top of stack, exp is also updated by concatinating this new element to exp seperated by space(seperated by space, so that it becomes easy to convert exp to array containing all the elements of postfix expression using exp.split(" ") method.)

Converting into Infix String: To calculate infix representation string variable exp is used, it is first converted into an array denoting a collection of operands and operators using exp.split(" ") but before this exp.trim() is used so that any whitespace character from the start or end of exp is removed, so that, we don't get unexpected elments added to array of postfix elements due to extra whitespace. Now, since we have array of elments of postfix expression we can easilty run the algorithm of converting postfix to infix expression using stack.

Computing the Height of the Expression Tree: First we construct the expression tree using the method constructTree() which returns the root of the expression tree and then we a traversal on that tree calculated the height of the tree.

Evaluating the Expression Tree: Since, we have postfix expression we don't need to construct or use expression tree to evaluated the expression, we just use exp variable as we used it while finding Infix String, and whenever we find an operator, instead of finding expression we calculate the result of the expression depending upon which operator we have encountered. To calculate the value of expression with variables, we do a check on operands while calcualting the value of any expression when an operator encountered, if operand is a variable we replace it by the value passed to evaluate() method and evaluate the expression as in normal evaluate() method.

Implementation:

import java.util.Stack;

class Node {

String value;

Node left, right;

Node(String value) {

this.value = value;

left = right = null;

}

}

class ExpressionTree {

Stack<String> stack = new Stack<String>();

String exp = "";//String representation helps to easily evaluate infix expression;

private int height;

public ExpressionTree(){

stack = new Stack<String>();

exp = "";

height = 0;

}

public void pushNumber(double value){

String strRep = Double.toString(value);

exp = exp + strRep + " ";

stack.push(strRep);

}

public void pushOp(String op){

exp += op + " ";

stack.push(op);

}

public void pushVariable(){

exp += "VAR ";

stack.push("VAR");

}

//utility function to check whether an element is operator or operand;

private boolean isOperator(String s) {

if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {

return true;

}

return false;

}

//return infix string, use exp and a temporary stack to calculate

public String infixString() {

Stack<String> tempStack = new Stack<String>();

//trim whitespace characters from start and end of the expression if any

exp = exp.trim();

//split by whitespace characters and convert to array;

String[] expArr = exp.split(" ");

for (int i = 0; i < expArr.length; i++) {

if (isOperator(expArr[i])) {

String op1 = tempStack.peek();

tempStack.pop();

String op2 = tempStack.peek();

tempStack.pop();

tempStack.push("(" + op2 + " " + expArr[i] + " " + op1 + ")");

}

else

tempStack.push(expArr[i] + "");

}

return tempStack.peek();

}

public String evaluate() {

Stack<String> tempStack = new Stack<String>();

//trim whitespace characters from start and end of the expression if any

exp = exp.trim();

//split by whitespace characters and convert to array;

String[] expArr = exp.split(" ");

for (int i = 0; i < expArr.length; i++) {

if (isOperator(expArr[i])) {

String op1 = tempStack.peek();

tempStack.pop();

String op2 = tempStack.peek();

tempStack.pop();

double res;

if(expArr[i].equals("+"))

res = Double.valueOf(op2) + Double.valueOf(op1);

else if(expArr[i].equals("-"))

res = Double.valueOf(op2) - Double.valueOf(op1);

else if(expArr[i].equals("*"))

res = Double.valueOf(op2) * Double.valueOf(op1);

else

res = Double.valueOf(op2)/Double.valueOf(op1);

tempStack.push(Double.toString(res));

}

else

tempStack.push(expArr[i] + "");

}

return tempStack.peek();

}

public String evaluate(double varValue) {

Stack<String> tempStack = new Stack<String>();

//trim whitespace characters from start and end of the expression if any

exp = exp.trim();

//split by whitespace characters and convert to array;

String[] expArr = exp.split(" ");

for (int i = 0; i < expArr.length; i++) {

if (isOperator(expArr[i])) {

String op1 = tempStack.peek();

if(op1.equals("VAR")) op1 = Double.toString(varValue);

tempStack.pop();

String op2 = tempStack.peek();

if(op2.equals("VAR")) op2 = Double.toString(varValue);

tempStack.pop();

double res;

if(expArr[i].equals("+"))

res = Double.valueOf(op2) + Double.valueOf(op1);

else if(expArr[i].equals("-"))

res = Double.valueOf(op2) - Double.valueOf(op1);

else if(expArr[i].equals("*"))

res = Double.valueOf(op2) * Double.valueOf(op1);

else

res = Double.valueOf(op2)/Double.valueOf(op1);

tempStack.push(Double.toString(res));

}

else

tempStack.push(expArr[i] + "");

}

return tempStack.peek();

}

//clears stack and so exp and height;

public void clear(){

exp = "";

stack = new Stack<String>();

height = 0;

}

// first constructs the tree from the elements of exp and then recursively

// calculate the height of the tree using calcHeight

public int height(){

Node treeRoot = constructTree(exp.trim().split(" "));

height = 0;

calcHeight(0,treeRoot);

return height;

}

public void calcHeight(int tempHeight, Node root){

if(root != null){

if(height < tempHeight){

height = tempHeight;

}

calcHeight(tempHeight+1, root.left);

calcHeight(tempHeight+1, root.right);

}

}

//utility

Node constructTree(String postfix[]) {

Stack<Node> st = new Stack<Node>();

Node t, t1, t2;

// Traverse through every character of input expression

for (int i = 0; i < postfix.length; i++) {

// If operand, simply push into stack

if (!isOperator(postfix[i])) {

t = new Node(postfix[i]);

st.push(t);

} else // operator

{

t = new Node(postfix[i]);

// Pop two top nodes

// Store top

t1 = st.pop();

t2 = st.pop();

// make them children

t.right = t1;

t.left = t2;

// Add this subexpression to stack

st.push(t);

}

}

// only element will be root of expression tree

t = st.peek();

st.pop();

return t;

}

}