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

2019-04-08 ExpressionTreeLab

posted Apr 8, 2019, 5:53 AM by Konstantinovich Samuel   [ updated Apr 8, 2019, 5:58 AM ]
 ```Don't Forget your Practice Exam on paper! (for tomorrow)If you are not able to take the exam Friday, speak to me in person tomorrow.General Trees:The height of a tree is 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 earlier)Traversals!Tree Traversals:Runtime Complexity : O(n)V=RootValue CL=Left ChildCR=Right Child)There are 3 ways to traverse a binary tree. Much like traversing a list, we only care that we are able to touch every value. It doesnt matter if we print the elements or do any other operation with them/on them.VCLCR  (Pre-Order traversal)CLCRV   (Post-Order traveersal)CLVCR   (In-Order traversal)a pre-order traversal, of the following tree:     a   /   \      b     c    \   / \      f  e  xa b _ f c e x   (where _ signifies no child when a node has only 1 child)The 1st _ is the left child of bClasswork/Homework:MKS22X-ExpressionTreeIf you are not able to take the exam Friday, speak to me in person tomorrow.Expression Tree:MKS22X-ExpressionTree/ExpressionTree.javaHere is the ExpressionTree class, just drop in your methods from the classwork/homework, compile and run. Except you need to write the apply method.. which you probably have from your stack calc!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; } //If you are not able to take the exam Friday, speak to me in person tomorrow. ////////////////////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 } }```