7/9/02
Amir Kamil

Topic: Op Trees, Review


Announcements:
- Midterm today at 6:40 pm in 155 Dwinelle, open book and open notes.
- Project 1 due Sunday. If you haven't started, you're in for a long 
  week...


Scoping Revisited:
- A useful heuristic to use when considering method calls is compiler 
  replacement:
    1. Every call to an object's own method of the form 
       "<method>(...)" is replaced by "this.<method>(...)".
    2. Every call to a static method of the form 
       "<object>.<method>(...)" is replaced by 
       "<st(object)>.<method>(...)", where st(object) gives the 
       static type of the object.
    NOTE: The static type of "this" is the class in which the keyword 
          is used.
- ex.

class Homer {
  public void talk() {
    System.out.println(who() + "D'oh!");
  }
  public static String who() {
    return "Homer: ";
  }
}

Line three above is replaced as follows:

    System.out.println(who() + "D'oh!");
                  |
                  V 
    System.out.println(this.who() + "D'oh!");
                  | 
                  V
    System.out.println(Homer.who() + "D'oh!");

Then it becomes clear that this will always call who() defined in 
Homer, even if the object is actually a child class of Homer.

- The scope of a method body is the scope in which the method was
  defined. So if you change the method who() in Homer to private, it
  would still work if you called the talk() method from a Bart
  object. The call to who() from within talk() is legal in the
  scope in which talk() is defined.


WeirdList:
- Similar to HW2 #3, but a little simpler.
- We will use a singly linked list and only implement a few trivial
  methods, in order to get the picture without worrying about the gory 
  details.
- Implement the methods declared in class WeirdList without any
  conditionals or loops:

class WeirdList {

  protected Object data;     // the value stored in this node
  protected WeirdList next;  // the next node

  // Constructors
  public WeirdList(Object data, WeirdList next) {
    this.next = next;
  }
  public WeirdList() {
    this(null, null);
  }

  // Iterates through the end of the list and terminates without error.
  public void stop() {
    next.stop();
  }

  // Returns the number of elements in this list.
  public int length() {
    return 0; // FILL IN
  }

}

We want to implement the method stop(), without using conditionals, but 
we want a call to wl.stop() (assuming wl is a WeirdList) to terminate 
without exception. Consider, what does the next field of the last node 
in the list contain? Normally, it would be a null pointer. However, 
when you try calling next.stop() from the last node, you'll get a 
NullPointerException. So we need to use something else other than null 
to put in the last node's next field. But the next field is declared to 
be of type WeirdList, so this restricts the type of objects we can 
assign to it. What types can we assign to it? If you remember from the 
discussion on static and dynamic types, we can assign an instance of a 
child class of List to a List variable. So we can create a subclass of 
WeirdList and use it to replace the value null in the last node. So 
let's define a subclass:

class NullList extends WeirdList {

  // Constructor
  public NullList() {
    super(null, null);
  }
  
}

What's the problem with this implementation? Well, when execution 
reaches the last node in the list and passes on the the NullList, the 
call to the stop() method in the NullList produces the same problem as 
before, since the method is inherited and therefore identical. But it 
doesn't have to be identical. Remember, we can override methods. So 
let's do so:

class NullList extends WeirdList {

  // Constructor
  public NullList() {
    super(null, null);
  }
  
  // Terminates without exception.
  public void stop() {
    return;
  }  

}

Now when execution reaches the NullList, the call to the stop() method 
in NullList returns immediately, and the calls to the preceding nodes' 
stop() method terminate cleanly.
We can also implement the length() method similarly:

class WeirdList {
  ... // fields and methods
  // Returns the number of elements in the list.
  public int length() {
    return 1 + next.length();
  }
}

class NullList extends WeirdList {
  ... // fields and methods
  // Returns 0.
  public int length() {
    return 0;
  }
}


Op Trees:
- After you have constructed an op tree, how do you evaluate it? One
  way of doing it is using a depth-first search, but there is a much
  easier way to do it. Let's consider arithmetic expressions involving
  only addition and multiplication. Define the op tree as follows:

abstract class OpTree {

  public OpTree left;
  public OpTree right;

  public OpTree(OpTree left, OpTree right) {
    this.left = left;
    this.right = right;
  }

  // Evaluates the subtree rooted at this node.
  public abstract int eval();

}

Now you can define subclasses of OpTree that evaluate themselves
distinctively:

class ValTree extends OpTree {

  public int val; // the value in this node
  
  public ValTree(int val, OpTree left, Optree right) {
    super(left, right);
    this.val = val;
  }

  // Returns the value in this node.
  public int eval() {
    return val;
  }

}

class AddTree extends OpTree {

  // Returns the sum of the left and right trees.
  public int eval() {
    return left.eval() + right.eval();
  }

}

class MultTree extends OpTree {

  // Returns the product of the left and right trees.
  public int eval() {
    return left.eval() * right.eval();
  }

}

ex:         -- + --
           /       \
          +         *
        /   \     /   \
       *     5   +     4
      / \       / \
     6   3     2   1

       
          +                              *
        /   \                          /   \
       *     5          +             +     4
      / \                            / \
     6   3                          2   1


       *                                   +     
  (   / \    +    5  )       +        (   / \     *    4  )
     6   3                               2   1


  (  ( 6 * 3 )  +  5  )      +      (  ( 2 + 1 )  *  4  )


  (  18 + 5  )         +         (  3 * 4  )


    23     +    12


    35

When you call eval() from the root, and AddTree, it will recursively
evaluate the results of its two subtrees and return their sum. This is
called recursive-descent parsing.


Questions?


Next Time: BSTs, Heaps, Algorithm Analysis