2008 October 13 / jjddaavviiss@@ccaarrlleettoonn..eedduu

Carleton College CS 201, Prof. Joshua R. Davis

In this assignment you will implement a binary tree, a tree using a list, and a tree using a binary tree. You will also use the binary tree datastructure to parse and evaluate simple algebraic expressions.

`BinaryTree`

Here is the ADT spec we will use for `BinaryTree`

. By the way, it is slightly different from the one we discussed in class (the only difference is that the constructor takes a value now) and quite different from the one in the book.

`BinaryTree(rootValue)`

returns a binary tree with the given root value and no children.`setRootValue(rootValue)`

sets the root value.`getRootValue()`

returns the root value.`setLeftChild(binaryTree)`

sets the left child to the given binary tree. You do not need to check that`binaryTree`

is a true`BinaryTree`

, but you may if you like.`getLeftChild()`

returns the left child.`setRightChild(binaryTree)`

sets the right child to the given binary tree.`getRightChild()`

returns the right child.`__str__()`

is a special Python method that returns a string representation of the binary tree, as described below.

mytree = BinaryTree('rooty') mytree.setRightChild(BinaryTree('righty')) mytree.getRightChild().setLeftChild(BinaryTree('rightylefty'))...then at the end the string representation should be

[rooty, [], [righty, [rightylefty, [], []], []]]Notice that this looks like a nest of Python lists. That's no accident; a nest of lists is one of our favorite ways to describe trees (more on that another time).

For this part of the assignment, implement the entire `BinaryTree`

class, including `__str__()`

, in a file binarytree.py.

Our book describes a notion of fully-parenthesized arithmetic expressions, and describes how to scan, parse, and evaluate them. In this part of the assignment we do much the same thing, but with some important changes. First, we allow our expressions to involve not just numbers but also variables with names such as `'x'`

, `'y'`

, etc. Second, we clearly distinguish among the scanning, parsing, and evaluating processes (whereas the book combines them somewhat).

Let's briefly review the main ideas and jargon using an example. Suppose that we begin with a fully-parenthesized expression stored in a string:

mystring = '( ( 3 + x ) * 15 )'Using the Python string method

`split()`

, we can easily mytokens = mystring.split()Keep in mind that each token is a string. That is, the "15" is a string, not a number. It will not turn into a number until we do the evaluation step, later.

Once you have scanned the string into a list of tokens, you feed the list of tokens to the `parse()`

function (which you will write). This function outputs a parse tree — that is, a binary tree in which the tokens are the values of the various tree nodes. Continuing our example, the parse tree's string representation is

[*, [+, [3, [], []], [x, [], []]], [15, [], []]](Draw this tree out yourself, to understand why it is correct.) Again, keep in mind that the tokens stored in the parse tree are all strings; "15" is still a string, not a number. This is a key difference between our approach and the book's.

Finally, you feed the tree to an `evaluate()`

function (which you will write) to turn it into a numeric value. When you do this, you must specify the numeric value of each variable occurring in the original expression. For simplicity, let us assume that there is only one variable in any given expression — e.g. `'x'`

or `'y'`

, but not both. So your `evaluate()`

function should take in a parse tree, a variable name, and a value to plug in for that variable; it should return the overall numerical value of the expression. Continuing our example, suppose that the parse tree above is stored in `mytree`

; then

evaluate(mytree, 'x', 2)should return

`75`

, since ( ( 3 + 2 ) * 15 ) = 75.
For this part of the assignment, write your `parse()`

and `evaluate()`

functions in a file called algebra.py.

`Tree`

Using A List
In class and in this assignment, our general `Tree`

ADT is specified by the following method list. Notice that it is somewhat different from our book's.

`Tree(rootValue)`

returns a tree with the given root value and no children.`setRootValue(rootValue)`

sets the root value.`getRootValue()`

returns the root value.`numChildren()`

returns the number of children.`appendChild(tree)`

appends a`Tree`

as a child. Again, you do not need to check that`tree`

is a`Tree`

, but you may if you like.`insertChild(index, tree)`

inserts the given tree at the given index, similarly to how one inserts an object into a list in Python.`popChild(index=None)`

removes the child at the given index and returns it, similarly to how one pops an object from a Python list. The`index=None`

syntax specifies that the user may omit the`index`

argument, in which case it is assumed to have a value of`None`

. This is how Python's list`pop()`

behaves.`__setitem__(index, tree)`

is a special Python method that sets the child at the given index to the given tree.`__getitem__(index)`

is a special Python method that returns the child at the given index.`__str__()`

is that special Python method that returns a string representation. See details below.

`Tree`

behaves a little differently from that of a `BinaryTree`

due to the variable number of children. Namely, we do not insert commas and "[]" to indicate the place of a missing child; instead, we just list the children that are there. For example, the code...
mytree = Tree('rooty') print str(mytree) mytree.appendChild(Tree('oney')) print str(mytree) mytree.appendChild(Tree('twoy')) print str(mytree) mytree[0].appendChild(Tree('oneyoney')) print str(mytree) mytree[0].appendChild(Tree('oneytwoy')) print str(mytree) mytree[0][0].appendChild(Tree('oneyoneyoney')) print str(mytree) mytree.popChild(0) print str(mytree)...produces this output:

[rooty] [rooty, [oney]] [rooty, [oney], [twoy]] [rooty, [oney, [oneyoney]], [twoy]] [rooty, [oney, [oneyoney], [oneytwoy]], [twoy]] [rooty, [oney, [oneyoney, [oneyoneyoney]], [oneytwoy]], [twoy]] [rooty, [twoy]]

For this part of the assignment, implement the `Tree`

class, including the three special methods, in a file treeusinglist.py. Follow the implementation idea we discussed in class, where each tree node stores (1) its value and (2) a Python list of children. (Note: This is different from the idea that a tree is simply a "nest of lists", with the 0th item in the list being the root value, and the other items being children. As we discussed it, that produced a different ADT, so it is not what I'm talking about in this assignment. Nevertheless, our string representation does give the impression that the tree is a nest of lists, because that is a standard way to write down trees, no matter what the exact ADT is.)

`Tree`

As A Binary Tree
In class we've discussed a "first child, next sibling" trick that lets you implement an arbitrary tree using a binary tree. In this part of the assignment, you will implement the `Tree`

ADT described in the preceding section as a subclass of `BinaryTree`

, as follows.

In the file treeusingbinarytree.py, declare `Tree`

as a subclass of `BinaryTree`

. Implement these four methods using `BinaryTree`

's methods:

`setFirstChild(tree)`

sets the first child to the given tree.`getFirstChild()`

returns the first child.`setNextSibling(tree)`

sets the next sibling to the given tree.`getNextSibling()`

returns the next sibling.

`Tree`

ADT using only these four methods. If you do it the way I expect, then you should not need to override `__init__()`

, `setRootValue()`

, or `getRootValue()`

.

By Wednesday at 11:59 PM, submit your four files (binarytree.py, algebra.py, treeusinglist.py, and treeusingbinarytree.py) electronically, either using `hsp`

or by putting it on COURSES manually. Your work will be graded based on these criteria:

`BinaryTree`

is correct (3 points) and clear/well-commented (1 point).`parse()`

and`evaluate()`

are correct (3 points) and clear/well-commented (1 point).`Tree`

based on a list is correct (3 points) and clear/well-commented (1 point).`Tree`

based on a binary tree is correct (3 points) and clear/well-commented (1 point).