Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-04-26 Expression Tree

posted Apr 26, 2017, 6:09 AM by Samuel Konstantinovich   [ updated Apr 26, 2017, 6:19 AM ]
Solution to eval: (without the isOp, or perform methods)

public static double eval(String s){
    String[] tokens = s.split(" ");
    Stack<Double> values = new Stack<Double>();
    
    for(String token : tokens){
      if(isOp(token)){
       	 values.push(perform(token,values.pop(),values.pop()));
      }
      else{
        values.push(Double.parseDouble(token));
      }
    }
    
    return values.pop();
}


Equivalent infix, postfix, and prefix expressions:
(((5.0 + 2.0) * 3.33) - 1.0)
5.0 2.0 + 3.33 * 1.0 -
- * + 5.0 2.0 3.33 1.0



/*This expression tree is a binary tree that represents
an arithmetic expression. The results are always doubles,
no int operations nor booleans/strings etc.
-Example:
  +
 / \
3   *
  /  \
 2   10
- Any node with children is treated like an operator.
- Any node without children is treated like a value.

Assumptions that can be made:
- A TreeNode has 0 or 2 children.
- A TreeNode with children must have an operator.
- For now all operators are binary and are one of these: '+', '-', '*', '/'.
*/

public class ExpressionTree{
  /*instance variables, constructors, and some methods not shown*/
  
  /*accessor method for the value, precondition is that isValue() is true.*/
  private double getValue(){    /*implementation not shown*/ }
  /*accessor method for the operation, precondition is that isOp() is true.*/
  private char getOp(){    /*implementation not shown*/  }    
  /* accessor method for left, precondition is that isOp() is true.*/
  private ExpressionTree getLeft(){    /*implementation not shown*/  }
  /* accessor method for right, precondition is that isOp() is true.*/
  private ExpressionTree getRight(){    /*implementation not shown*/  }

  private boolean isOp(){    /*implementation not shown*/  }
  private boolean isValue(){    /*implementation not shown*/  }


  /* you write these four methods, hint: think recursively */

  /*return the expression as an infix notation string with parenthesis*/
  /* The sample tree at the top would be: "( 3 + (2 * 10))"     */
  public String toString(){    /*you are to write this method*/  }

  /*return the expression as a postfix notation string without parenthesis*/
  /* The sample tree would be: "3 2 10 * +"     */
  public String toStringPostfix(){    /*you are to write this method*/  }

  /*return the expression as a prefix notation string without parenthesis*/
  /* The sample tree would be: "+ 3 * 2 10"     */
  public String toStringPrefix(){    /*you are to write this method*/  }

  /*return the value of the expression tree*/
  public double evaluate(){    /*you are to write this method*/  }

}
Comments