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.java


The 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  e

a 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 c


DO 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   
  }
}
Comments