Lab 11: Parse trees

These can be represented as trees. (We can ignore the parentheses now, since the information they give about grouping is contained in the structure of the tree itself.)

15      -        /           +
       / \      / \        /   \
     42   17   *   147    *     -
              / \        / \   / \
            18   10    14  91 22  17

Expression can be modelled by a node-like interface with two implementing classes: one for leaf nodes containing integers, and one for nodes containing an operator and having two children. Evaluation of the expressions can be performed with a depth-first post-order traversal of the tree.

3. ExprNode classes

Your first task is to design classes that model the two kinds of nodes, implementing the ExprNode interface. These nodes will have to have evaluate() methods, but we'll deal with that later.

So, write two classes, one for leaf/integer nodes, the other for non-leaf/operation nodes. What instance variables will they have?

4. Building expression trees

Next, you will need to write code to build an expression tree given a String containing a fully-parenthesized expression. The driver program Interpreter is intended to work so that the user can write a expression in the commandline, and the program will build an appropriate expression tree, and then evaluate the expression using the tree. Implement this in the main method of Interpreter and the the constructors of the classes you wrote in part B.

One thing you will find useful is a method Dr. Van Drunen wrote and included in the code you copied. In the class ExprStringSlicer, the static method slice() takes a String, assumed to contain an expression in our grammar. It will return an array of Strings: if the String passed to it is just an integer, then it will return an array with exactly one element, a String version of that integer; if it is passed a String with a parenthesized operation over subexpressions, it will return an array with three elements, the first subexpression, the operator, and the second subexpression. For example, given "5", it will return { "5" }. Given "((14 * 91) + (22 - 17))", it will return { "(14 * 91)", "+", "(22 - 17")}.

(Extra credit: Do not use my ExprStringSlicer class. Write your own slice() method.)

Note that ExprStringSlicer.slice() will thrown one of several unchecked exceptions if you hand it a malformed string; the most likely is StringIndexOutOfBoundsException. It is reasonable for your constructors to throw similar exceptions (e.g., NumberFormatException) if the arguments passed to them are not well-formed.

When you test out your program, you will need to put quotes around the string you give to Interpreter. For example, you could run the program with

java Interpreter "((14 * 91) + (22 - 17))"

The quotes tell Java to treat ((14 * 91) + (22 - 17)) as a single String (it will be the zeroth item in args). Otherwise every space would be assumed to begin and end a separate String; furthermore, the parentheses would really mess things up.

5. Evaluating expression trees

Finally, the interpreter calls the evaluate() method on the trees you have built. Write the evaluate methods so that they return the integer value of the given expression.

6. Turn in

Create a script file in which you remove the .class files and then compile and run your program. Print that script together with the .java files you have changed.

Turn in the class files and your script using

/cslab/class/csci231/handin lab11 typescript ...source file names...