Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-04-05 Expression tree

posted Apr 5, 2019, 5:55 AM by Konstantinovich Samuel   [ updated Apr 5, 2019, 11:30 AM ]

IN CLASS:  
    evaluate
    toStringPostfix

HOMEWORK (on the same paper is fine!):
    toString
    toStringPrefix


Goal: Write a solution to an AP style question on paper.
25 minutes: solo read + solo write out solutions on paper. 

Write the solution on a new page of paper.
Do not worry about exceptions, you just have to pay attention to preconditions.

/*This expression tree is a binary tree that represents
an arithmetic expression. The results are always doubles,
no int division, no booleans/strings etc.
-Example:
    +
  /   \
 3.0  *
     /  \
  2.0   10.0

- An ExpressionTree has 0 or 2 children.
- An ExpressionTree with 0 children must be a value.
- An ExpressionTree with 2 children must be an operator.
- 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*/  }

 /* return true when the tree is an operation, false otherwise.*/
  private boolean isOp(){    /*implementation not shown*/  }

 /* return true when the tree is a value, false otherwise. The negative of isOp()*/
  private boolean isValue(){    /*implementation not shown*/  }

  /* precondition: op is '+','-','*' or '/'. 
     returns: the resultant value of using the operator on a and b.*/
  private double perform(char op, double a, double b)
                            {    /*implementation not shown*/  }
  /* you write these four methods, hint: think recursively */

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

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

  //IN CLASS YOU CAN STOP HERE. IF YOU FINISH EARLY, YOU CAN CONTINUE.
 
  /*return the expression as an infix notation string with parenthesis*/
  /* The sample tree at the top would be: "(3.0 + (2.0 * 10.0))"     */
  public String toString(){    /*you are to write this method*/  }


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

}
Comments