Question

I need help creating the methods for using a linked binary tree to build,evaluate, and paranthesize the expression. We have to use linked stack to pop and push the operands into the expression.

Theres two classes:

Expression: Constructor, set/gets, methods.

ExpressionTest: Test driver for defining exp, and calling methods

I need to put the mathematical exp (from the test class) into a binary tree, evaluate the exp in the binary tree, paranthesize it and print it out.

So i need to create 3 methods for building the tree, evaulating it, and paranthesizing it.

package lab5;

import net.datastructures.*;

public class Expression<T> {
  
/** Contain Linked Tree and Linked Stack instance variables **/
   LinkedBinaryTree<T> tree;
   LinkedStack<LinkedBinaryTree<T>> stack;
  
  
   public Expression () {
       tree = new LinkedBinaryTree<T> ();
       stack = new LinkedStack<LinkedBinaryTree<T>>();
      
   } // end constructor
  
   public LinkedBinaryTree<T> buildExpression (String expression) {// LinkedBinaryTree<T> is a type of LinkedBinaryTree
       // major TODO to implement the algorithm]
       LinkedBinaryTree<T> operand, op1, op2;
       LinkedStack<LinkedBinaryTree<T>> newStack = new LinkedStack<LinkedBinaryTree<T>>();
       String symbol;
      
       int i = 0;
       int len = expression.length();
      
       for (i = 0; i < len; i++) {
           symbol = expression.substring(i, i+1);
          
           if ((!symbol.equals ("(")) && (!symbol.equals (")"))) {
               operand = new LinkedBinaryTree<T> ();
               operand.addRoot((T)symbol);
               newStack.push(operand);
           } else if (symbol.equals ("(")){
               continue;
           } else {
               op2 = newStack.pop();
               operand = newStack.pop();
               op1 = newStack.pop();
           tree.attach(operand.root(), op1, op2);
           newStack.push(operand);
           }
       }
       tree = newStack.pop();
       return tree;

   } // end method buildExpression
  
   public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) {
       int result = 0;
       LinkedStack<String> opStack = new LinkedStack<String>();
       LinkedStack<String> valStack = new LinkedStack<String>();
       if (tree.isInternal(v)) {
           for (Position<T> c : tree.children(v)){
               String x = (String)c.getElement();
               if (!x.equals("+") && !x.equals("-") && !x.equals("x") && !x.equals("/")) {
                   valStack.push(x);
                   valStack.push(x);
                   String opPop = opStack.pop();
                   switch (opPop) {
                   case "+":
                       String a = valStack.pop();
                       String b = valStack.pop();
                       System.out.print(a);
                       break;
                   }
               } else {
                   opStack.push(x);
                  
               }
               //System.out.print(x);
               evaluateExpression(tree, c);
              
           }
       }
       /*if (tree.isInternal(v)) {
           for (Position<T> c : tree.children(v)) {
               System.out.print(tree.right(c));
               System.out.print(v.getElement());
           }
       }*/
       return result;
   }
  
   public void parenthesize (Tree<T>tree, Position<T> p) {
       if (tree.isInternal(p)) {
           boolean firstTime = true;
           for (Position<T> c : tree.children(p)) {
               System.out.print((firstTime ? "(" : ","));
               System.out.print(c.getElement());
               firstTime = false;
               parenthesize(tree, c);
           }
           System.out.print(")");
       }
   }

}

Ouput:

The Tree: net.datastructures.LinkedBinaryTree@12a3a380

The Parenthesize Tree:(/(x(+(3,1),3),+(-(9,5),2)),+(x(3,-(7,4)),6))

Exception in thread "main" java.lang.NullPointerException
   at lab5.Expression.evaluateExpression(Expression.java:60)

it won't evaluate the expression inside the binary tree. i just keep getting nullpointerexception.