Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

### 2018-04-24

posted Apr 24, 2018, 9:51 AM by Konstantinovich Samuel   [ updated Apr 24, 2018, 12:15 PM ]
 ```Homework:Don't Forget your Practice Exam!Expression Tree in your git:11ExpressionTree/ExpressionTree.javaThe height of the tree minimally log n. Ideally we can maintain the minmum height.To add a node the the runtime is O(height) which is between O(log n) O(n). How do we print these trees?  (Hint: your toStrings from yesterday)Traversals!Tree Transversals - O(n)Tree Traversals: (V=Value, CL=Left Child, CR=Right Child)VCLCR  (Pre-Order)CLCRV   (Post-Order)CLVCR   (In-Order)a pre-order traversal, of the following tree:     a   /   \      b     c    \   /       f  ea b _1 f _2 _3 c e _4 _5 _6   (where _x signifies no child)_1 is the left child of b_2 and _3 are the children of f_4 and _5 are the children of e_6 is the right child of cDO NOW:Test your expression tree code!Here is the ExpressionTree class, just drop in your methods from yesterday, compile and run. Except you need to write the apply method!public class ExpressionTree{ /*return the expression as an infix notation string with parenthesis*/ /* The sample tree would be: "(3 + (2 * 10))" */ public String toString(){ /*you are to write this method*/ return ""; } /*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 ""; } /*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 ""; } /*return the value of the specified expression tree*/ public double evaluate(){ /*you are to write this method*/ return 0.0; } /*use the correct operator on both a and b, and return that value*/ private double apply(char op, double a, double b){ /*you are to write this method*/ return 0.0; } ////////////////////ONLY EDIT ABOVE THIS LINE//////////////////// private char op; private double value; private ExpressionTree left,right; /*TreeNodes are immutable, so no issues with linking them across multiple * expressions. The can be constructed with a value, or operator and 2 * sub-ExpressionTrees*/ public ExpressionTree(double value){ this.value = value; op = '~'; } public ExpressionTree(char op,ExpressionTree l, ExpressionTree r){ this.op = op; left = l; right = r; } public char getOp(){ return op; } /* accessor method for Value, precondition is that isValue() is true.*/ private double getValue(){ return value; } /* accessor method for left, precondition is that isOp() is true.*/ private ExpressionTree getLeft(){ return left; } /* accessor method for right, precondition is that isOp() is true.*/ private ExpressionTree getRight(){ return right; } private boolean isOp(){ return hasChildren(); } private boolean isValue(){ return !hasChildren(); } private boolean hasChildren(){ return left != null && right != null; } public static void main(String[] args){ //ugly main sorry! ExpressionTree a = new ExpressionTree(4.0); ExpressionTree b = new ExpressionTree(2.0); ExpressionTree c = new ExpressionTree('+',a,b); System.out.println(c); System.out.println(c.toStringPostfix()); System.out.println(c.toStringPrefix()); System.out.println(c.evaluate());//6.0 ExpressionTree d = new ExpressionTree('*',c,new ExpressionTree(3.5)); System.out.println(d); System.out.println(d.toStringPostfix()); System.out.println(d.toStringPrefix()); System.out.println(d.evaluate());//21 ExpressionTree ex = new ExpressionTree('-',d,new ExpressionTree(1.0)); System.out.println(ex); System.out.println(ex.toStringPostfix()); System.out.println(ex.toStringPrefix()); System.out.println(ex.evaluate());//20 ex = new ExpressionTree('+',new ExpressionTree(1.0),ex); System.out.println(ex); System.out.println(ex.toStringPostfix()); System.out.println(ex.toStringPrefix()); System.out.println(ex.evaluate());//21 ex = new ExpressionTree('/',ex,new ExpressionTree(2.0)); System.out.println(ex); System.out.println(ex.toStringPostfix()); System.out.println(ex.toStringPrefix()); System.out.println(ex.evaluate());//10.5 } }```