CSCI 235 Lab 13: Expression Trees

This lab session will continue what you did in lab on Thursday. If you made any progress on the “Parsing” portion of lab 12, get with your partner from Thursday. You can pair up with someone else if you don’t have work to build on.

If you are continuing, change into your directory lab12/parse. If you are starting from scratch, you can either go to a repository that you already have or clone a new one.

You’ll also want the lab handout from lab12, which is available online.

Additional background

As mentioned in class, trees have many uses in computation. They fit very well with the idea of mathematical expressions—both for dealing with expressions’ written form and for evaluating expressions. Trees are a good fit because expressions can be defined recursively, as in the grammar from lab 12, which covers fully parenthesized expressions:

expression → integer | ( expression op expression ) op → + |-| / | *

The first line tells us that an expression can be a single integer; the second says that an expression can also consist of a left parenthesis, an expression, an operator, another expression, and a right parenthesis. So here are some example expressions

and the corresponding trees:

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

The alternatives in the first two lines of the grammar correspond to the two kinds of nodes in the tree: each expression corresponds either to a leaf node (with an integer value) or to an interior node that has an operator and two child expressions.

You have three problems to solve:

  1. writing classes to represent expressions as trees;
  2. parsing—that is, turning a string into an equivalent expression tree; and
  3. providing the methods to evaluate an expression tree.

1. Representing expressions as trees

You have been provided with and interface ExprNode, which is the type that you will use to represent any expression. You need to provide classes that implement this interface, corresponding to the two cases for what an expression can be.

You have to decide what instance variables each class should have, and you decide what parameters to pass to the constructors. You may not get that figured out until you solve the other problems.

For your code to compile, you will need to fill in something for the method evaluate() in your classes. You can write a “stub” that simply returns a recognizable value until you figure out what should be there.

2. Parsing

In the driver program Interpreter there is a static method parse() that should take a single string as its parameter and returns the corresponding tree (as an instance of a subclass of ExprNode). You need to fill this method in so that it works properly.

You have been provided with a compiled version of the class ExprStringSlicer. It gives you a single static method

public static String[] slice(String *expr)

that will be helpful. This method processes the string you give it, returning an array that is either

  1. of size one, in which case the string in it should represent an integer, or
  2. of size three, in which case the three strings in it are, respectively, the first operand (an expression), an operator, and the second operand (also an expression)

You do not need to worry about what happens if you are passed a string that is not a legal expression. The slice() method will throw an exception for some malformed strings; you do not need to catch and handle those. It is also reasonable if your parse() or your constructors throw exceptions (such as NumberFormatException when parse() is passed a bad string.

If you’ve written at least a stub for the evaluate() methods, you can do some testing now by running Interpreter with a single argument that is the expression to parse and (eventually) evaluate. On the command line, you will need to put quotes around the expression, as in

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

The answer printed will not be correct until you complete the next part.

3. Evaluating expression trees

The main method calls evaluate() on the tree returned from parse(). It is now time for you to complete the evaluate() methods so that they work correctly. An interior (operator) node will need to evaluate its children and then, based on whatever you passed its constructor for the operator, do the appropriate operation to produce its result.

Turning it in

Plan several expressions to demonstrate your program working, plus some badly-formed expressions to show it throwing an exception. Then create a script file in which you

  1. remove the .class files corresponding to your source files (do not remove ExprStringSlicer.class!);
  2. compile; and
  3. run the Interpreter program for several different expressions (including some badly formed ones).

After you end the script, hand in the typescript and the three files you worked on today with

$ /cslab/class/csci235/bin/handin lab13 typescript *.java

Be sure you copy your code from today to your own directory; you will want it for a future project.

Extra credit: slicing a string

If you have time (or want to do it later), you can write your own method slice() and us it instead of the provided one. That isn’t trivial, but you may enjoy the challenge.