CSCI 235 Lab 12: Trees

0. Revisiting lists

Check out a fresh copy of the code from lab 11:

Even if you did it on Friday, repeat parts 3 and 4 of Friday’s lab. Take up to about 30 minutes to write removeFromFront() and insertSorted() in a single version of the file. If one of you finished it Friday and one did not, let the partner who did not previously finish take the lead.

Hand in IList.java as assignment lab11b.

1. Set up

The goal of this lab is to practice writing operations for binary trees, as an application of and variation on linked lists.

As usual, clone the repository for this lab and then cd into it. If your are in the directory where you were completing lab11, move up to the containing directory

before cloning the repository

Note that because it is a repository, you should feel free to commit your changes at any point that you deem appropriate.

2. Introduction

We have worked some with lists, and in class we introduced another kind of linked structure: the tree. In a tree, a node can have multiple children; the case of at most two children is called a binary tree. If we draw a picture with each node above its children, we get something like this:

We call the node at the top, which has no parent, the root, and the nodes at the bottom, that have no children, are called leaves. (Yes, computer scientists grow trees upside down.)

Change into the tree subdirectory and look at the code there. You’ll see that there are two classes, TreeNode and TreeDriver, that are very similar to what we saw in class. For warm-up, you’ll repeat complete what we started in class.

Look at the main method in TreeDriver to see how it builds the tree drawn above. (Note that, in general, either child of a node might be null.) Note that the node 2 is the left child of the node 1, but it is also the root of a subtree made up of it and its children (and its children’s children...).

Trees are natually traversed in a recursive manner. We wrote the method count() in class; it tells you how many nodes there are in the subtree rooted at the node on which it is called. Note that the number of nodes in a tree is 1 (for the node) plus the number of nodes in its left subtree, plus the number of nodes in its right subtree.

When walking a binary tree recursively, you have three choices for when to process a node relative to its children. If you do the node before the children, it is called preorder; if you do it after the children, it is called postorder; and if you do a node between its children, it is called inorder. We wrote these methods in class yesterday.

Modify the the construction of the tree to add some more nodes, and be sure that that there are nodes that have only a left child or only a right child. Compile and run.

Note that in this version of trees we have a single node class, and we use null to indicate that a particular child (subtree) is empty. In the next program, we will use two different node classes: one will represent interior nodes (which will always have two children), and the other leaf nodes.

3. Parsing

Change into the other directory for this lab; from the tree directory, you can do that with

(Had you noticed that directories form a tree, and that .. names the parent?)

One of the files there is ExprStringSlicer.class, which saves you some work. It would be a good idea if you make it harder to discard, which you can do by taking away your own permission to write it. The command to do that is

(A brief explanation: “chmod” means “change mode”; “mode” is another name for permissions. The next part “u-w” says to take away write (w) permission from the user (u) who owns the file—which is you.)

One use for trees is in the grammatical (or syntactical) analysis (or “parsing”) of languages—both human languages and programming languages. (You might recall that we have encountered “parse” in the name of the library method Integer.parseInt(), which converts a string representing an integer into an int value.)

We can write a description of a language as a grammar; in the notation below, the → means “consists of” and the | separates alternatives. So we can specify a language of fully parenthesized arithmetic expressions with this grammar:

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. The final line says that an operator can be one of the four symbols listed.

According to this grammar, the following are expressions:

• 15
• (42 - 17)
• ((18 * 10) / 147)
• ((14 * 91) + (22 - 17))

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

Note that an expression tree can be represented in Java with a node-like interface plus two classes that implement it: 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 post-order traversal of the tree.

3a. ExprNode classes

You have been provided with the ExprNode interface. Your first task is to design the two classes that model the two kinds of nodes. These nodes will have to have evaluate() methods, but we’ll deal with that later—for now you can just put in a stub so that your classes will compile.

So, write two classes, one for leaf/integer nodes, the other for non-leaf/operation nodes. What instance variables will each have? What parameters should you pass to the constructor for each?

(So that your repository knows about the new files, you will want to either use hg copy to make them as copies of ExprNode.java or hg add if you make them some other way.)

3b. Building expression trees

Next, you will need to write code to build an expression tree given a String containing a fully-parenthesized expression; this process of extracting the structure from a sequence is called parsing. The driver program Interpreter is intended to work so that the user can write an expression on the command-line, and the program will build an appropriate expression tree, and then evaluate the expression using the tree. The main() method in Interpreter expects the (static) method parse() to turn a string into the appropriately constructed tree of the node classes that you wrote above.

You have been provided with a class file for ExprStringSlicer, which gives you a method named slice() that takes a single String as its parameter and returns an array of strings. When passed a string that represents an integer, slice() returns an array of length 1, containing the string representation of the integer. If it is passed a parenthesized expression, it returns an array with length 3, containing (in order) the first operand expression, the operator, and the second operand. For example, given "5", it will return "5" . Given "((14 * 91) + (22 - 17))", it will return "(14 * 91)", "+", "(22 - 17)".

Note how the latter case ends up with two strings representing expressions, which will need to each be passed to parse() to turn them into suitable trees.

(Extra credit: After you finish the rest of the lab, try writing our own slice() method and use it instead of the provided one.)

Note that ExprStringSlicer.slice() will throw 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

The quotes tell the shell to pass ((14 * 91) + (22 - 17)) to Java 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.

Running that will call evaluate() on the root of your tree; so the result you get is probably not correct (yet).

3c. Evaluating expression trees

Finally, write the evaluate() methods for your two classes so that they return the correct integer value for the expression-tree they represent.

Create a script file in which you compile Interpreter.java and then run the program for several different expressions.

4. Turn in

To turn in all of your files, get in the lab12 directory (the one containing directories tree and parse) and hand in the entire directory with

Note the dot, which refers to the current directory.

Be sure that you copy your code from both the list (lab11) and tree (lab12) portions of today’s work to your own accounts.