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 scan this string into a list of tokens. Try it yourself.
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).