title: Recursive evaluate() in expression tree class
body: <p>I am new in Java and trying to add evaluate method to my class. The ExpTree class and its testing program is given to me. I wrote my code as I learned in the class, but do not know why it does not work.</p>
  
  <blockquote>
    <p>An evaluate() method, which returns the arithmetic evaluation of the ExpTree.   This should be done recursively, so you will need 2 methods to do it.  In the case where it would result in division or mod by 0, it should throw a new ArithmeticException with a descriptive String.   If the tree is empty, evaluate() should also throw a new ArithmeticException with a descriptive String.</p>
  </blockquote>
  
  <p>Here is my code:</p>
  
  <pre class="lang-java prettyprint-override"><code>// This will implement an "Expression Tree" which stores an arithmetic expression
  
  import java.util.*;
  
  public class ExpTree
  {
      //-------data
      private ExpNode root;
  
      //-------constructor
      public ExpTree()
      {
          root = null;
      }
  
      //constructor where a string is passed in.  It is parsed and stored
      public ExpTree(String expString)
      {
          //declare StringTokenizer, Stacks, and other variables used in parsing
          StringTokenizer tokenizer = new StringTokenizer (expString, "()+-*/%", true);
          String token;
          ExpNode operator, leftOperand, rightOperand;
          Stack&lt;ExpNode&gt; operators = new Stack&lt;ExpNode&gt;();
          Stack&lt;ExpNode&gt; operands = new Stack&lt;ExpNode&gt;();
  
          //break up expString into tokens
          while (tokenizer.hasMoreTokens())
          {
              token = tokenizer.nextToken();
  
              // if the current token is a left paren, ignore it
              if (token.equals ("("))
                  ;
  
              // if the current token is an operator, put it on the
              // operator stack
              else if ((token.equals ("+")) || (token.equals ("-")) ||
                          (token.equals ("*")) || (token.equals ("/"))  || (token.equals ("%")))
                  operators.push (new ExpNode(token));
  
              //if the current token is a right paren, pop the operators stack
              //to get the operator, pop the operands stack twice to get the two
              //operands (stored as expression trees).   Then make the two operands
              //children of the operator and push back on the operands tree.
              else if (token.equals (")"))
              {
                  operator = operators.pop();
  
                  rightOperand = operands.pop();
                  leftOperand = operands.pop();
  
                  operator.setLeft(leftOperand);
                  operator.setRight(rightOperand);
  
                  operands.push(operator);
              }
  
              //otherwise, the token should be a number - put it in the operands stack
              else
                  operands.push (new ExpNode(token));
  
          } // while (tokenizer.hasMoreTokens())
  
          //when finished parsing, the operands stack should contain the fully-built
          //expression tree.
          if (!operands.isEmpty())
              root = operands.pop();
      }
  
      //-------methods
  
      //isEmpty()
      public boolean isEmpty()
      {
          return (root == null);
      }
  
      //printTree methods - prints the tree in RNL order, with indents.  Called from "outside"
      public void printTree()
      {
          if (root == null)
              System.out.println("The tree is empty");
          else
              printTree(root, 0);    //start with the root with 0 indentations
      }
  
      //recursive, private version of printTree
      private void printTree(ExpNode subTree, int indents)
      {
          //if there is a right side, handle it first (with 1 more indent)
          if (subTree.getRight() != null)
              printTree(subTree.getRight(), indents+1);
  
          //then print the node itself (first move over the right amount of indents)
          System.out.println("\n\n\n");
          for (int i=0; i&lt;indents; i++)
              System.out.print("\t");
          System.out.println(subTree);
  
          //if there is a left side, handle it first (with 1 more indent)
          if (subTree.getLeft() != null)
              printTree(subTree.getLeft(), indents+1);
      }
  
      //inorder traversal - starts the recursive calls to print inorder
      public String inOrder()
      {
          return inOrder(root);
      }
  
      //inorder traversal - recursive left side of tree, print node, right side of tree
      private String inOrder(ExpNode theTreeToTraverse)
      {
          if (theTreeToTraverse == null)
              return "";   //don't try to do anything if tree is null
  
          //else build up a String to return.  It will involve recursive calls
          String returnString = "";
          if (theTreeToTraverse.getLeft() != null)
          {
              returnString += "(" + inOrder(theTreeToTraverse.getLeft());
          }
          returnString += theTreeToTraverse;
          if (theTreeToTraverse.getRight() != null)
          {
              returnString += inOrder(theTreeToTraverse.getRight()) + ")";
          }
  
          return returnString;
      }
  
      //public version of evaluate  
      public double evaluate(){
      if (root == null)       //Am I null?
      throw new ArithmeticException("The tree is empty, nothing to be evaluated!");
  
      else                    //You handle it!
          return recursiveEvaluate(root);  
      }
  
      //Recursive version of evaluate
      private double recursiveEvaluate(ExpNode subTree){
          //If subTree is empty
          if (subTree == null)
              return 0;
  
      //What are you subTree? A number? An operator? 
      else if(subTree.getData().equals("+"))
          return recursiveEvaluate(subTree.getLeft()) +
                  recursiveEvaluate(subTree.getRight()) ;
  
      else if(subTree.getData().equals("-"))
          return recursiveEvaluate(subTree.getLeft()) -
                  recursiveEvaluate(subTree.getRight()) ;
  
      else if(subTree.getData().equals("*"))
          return recursiveEvaluate(subTree.getLeft()) *
                  recursiveEvaluate(subTree.getRight()) ;
  
      else if(subTree.getData().equals("/")){
          double right = recursiveEvaluate(subTree.getRight());
  
      if(right == 0.0)
          throw new ArithmeticException("Divide by zero is undefined!");
              return recursiveEvaluate(subTree.getLeft()) / right;
      }
  
      else if(subTree.getData().equals("%")){
          double right = recursiveEvaluate(subTree.getRight());
  
      if(right == 0.0)
          throw new ArithmeticException("Mod by zero exception");
              return recursiveEvaluate(subTree.getLeft()) % right;
      }
  
      //Converting String type to double
      else
          return Double.parseDouble(subTree.getData());
  
      }
  
      //Public version of numPlus
      public int numPlus(){
          return recursiveNumPlus(root);
      }
  
      //Recursive version of numPlus
      private int recursiveNumPlus(ExpNode subTree){
          if (subTree == null)
              return 0;
  
      //If you are a '+' sign
      if(subTree.getData().equals("+"))
          return recursiveNumPlus(subTree.getLeft()) +
                  recursiveNumPlus(subTree.getRight()) + 1;
  
      else
          return recursiveNumPlus(subTree.getLeft()) +
                  recursiveNumPlus(subTree.getRight());
      }
  
  }
  
  //***************************************************************************
  // ExpNode holds a "node" for an ExpTree.
  class ExpNode
  {
      //data
      private String data;
      private ExpNode left;
      private ExpNode right;
  
      //constructor
      public ExpNode(String el)
      {
          data = el;
          left = right = null;
      }
  
      //methods
      //toString() - this is how an ExpNode represents itself as a String
      public String toString()
      {
          return data;
      }
  
      //getLeft - returns the reference to the left subTree
      public ExpNode getLeft()
      {
          return left;
      }
  
      //getRight - returns the reference to the right subTree
      public ExpNode getRight()
      {
          return right;
      }
  
      //getData - returns the data (could be an operator or a number, so returns as a String)
      public String getData()
      {
          return data;
      }
  
      //setLeft - sets the left subTree to whatever is passed in
      public void setLeft(ExpNode newNode)
      {
          left = newNode;
      }
  
      //setRight - sets the right subTree to whatever is passed in
      public void setRight(ExpNode newNode)
      {
          right = newNode;
      }
  
  }
  </code></pre>