cs230 Lecture Notes
Week 9, Thursday

Homework 8 is due on Monday.

Also, for Monday, please do the practice exam and bring questions.

Exam #2 is next Thursday.


Today's topics
--------------

1) Tree traversals (from notes16.txt)

2) Expression trees

3) Using an abstract class for encapsulation

4) hw06 solutions and process objects


Quiz 8 Solution
---------------



















Expression trees
----------------

Algorithm for parsing a postfix expression and building an
expression tree:

1) if the next token is an operand, create and push a singleton
   (a tree with a single node)

2) if the next token is an operator, pop two subtrees
   and create a new node with the subtrees as children

3) at the end of input, there should be one tree on the
   stack and it should be a singleton.


Using an abstract class to improve encapsulation
------------------------------------------------

Example:

    public static void print (Tree tree) {
        if (tree == null) return;
        System.out.print (tree.cargo + " ");
        print (tree.left);
        print (tree.right);
    }

Goal: generalize print to traverse a tree and apply
some action to each cargo element.

Problem: only a tree knows how to traverse, but only
the cargo elements know what to do when they are visited.

Solution: define an abstract class called Visitable and
have the Tree code invoke the visit method:

    public static void preorder (Tree tree) {
        if (tree == null) return;
        tree.cargo.visit ();
        preorder (tree.left);
        preorder (tree.right);
    }

Abstract class definition:

(in Visitable.java)

public interface Visitable {
    public void visit ();
}

Each member of the Visitable abstract class defines what
it means to visit a node


Member class definition:

(in Token.java)

public class Token implements Visitable {
    String str;

    public void visit () {
        System.out.print (str + " ");
    }
}


Expression tree builder:

(in Translator.java)

    String expr = "1 2 3 * +";
    StringTokenizer st = new StringTokenizer (expr, " +-*/", true);
    String token = st.nextToken();
    Tree tree = new Tree (new Token (token), null, null));
    Tree.preorder (tree);

The infix generator is basically an inorder traversal of
the expression tree, except that it might have to insert
parentheses under certain conditions.

For hw08, you have the option of using the Visitable abstract
class to enforce encapsulation of the Translator code in the
Translator class.

It is not necessarily the best choice, but it is worth investigating.