| CS 635 Object-Oriented Design & Programming |
|---|
The problems in this assignment will use a binary tree to represent a simple arithmetic expression. The expressions will contain the operators "+", "-", "*", and absolute value (which will be shortened to the letter "a"). The operators will operate on integers (or if you prefer floats). A binary tree has internal nodes and external nodes (leaves). An internal node has either one or two subnodes (children). An external node (leaf) has no children. You need at least two different classes to represent the two types of nodes. These classes can be related by inheritance. The data for the internal nodes will be the strings "+", "-", "*", "a". AbsoluteValue is an unary operator that computes the absolute value of the value represented by the node's one subtree. The data for the external nodes will be integers (or floats if you prefer). If an internal node has the operator "+", its left child is a leaf with the value 3, its right child is a leaf with the value 5, then the internal node represents the expression 3 + 5. To simplify input and parsing you can assume that all input integers are one digit long. However you can have negative integers, so integers can be up to two characters long. Of course you can use longer integers if you like.
You can use either C++, Java, Object Pascal, Smalltalk, Eiffel, or Ada 95 for this assignment. C++ and Java are preferred. The intent of this assignment is for you to implement some of the patterns, not to find code or libraries to already do it for you. So implement your own trees, visitors, strategies, commands, interpreters and observers.
1. Implement a visitor that will print out the nodes of a binary tree in preorder. That is print out the root of the tree, print the left subtree in preorder, then print out the right subtree in preorder.
2. We will want to have a number of visitors for binary trees. We would like to have each visitor use either preorder (root, left subtree, right subtree), or inorder (left subtree, root, right subtree). Use either the strategy or iterator pattern to allow the same visitor to use different traversals algorithms. Modify the visitor in problem one to use the different traversals.
3. Implement a visitor that multiplies any negative values in an external node by negative one, but leaves the positive values unchanged. Use the command pattern (or command processor) to allow the changes to be undone.
4. Make the internal nodes observers of their subtrees, so that the internal node always has the correct values for expression represented by that node and its subtrees.
5. (Extra Credit) Implement a binary tree structure as an interpreter that will evaluate the simple arithmetic expression stored in the tree. Contrast this implementation with one using a visitor to evaluate the expression stored in the tree?
What to turn in. You need to turn in commented source code produced for
this assignment. Problems 1-3 can use the same classes for the tree
structure, so you only need to turn in one copy of them. If your visitor
implemented for problem one can use the different traversal algorithms
given in problem two, you do not have to turn in a separate visitor for
problem one and two. Each problem must have input and output
demonstrating that the code works. The input and output for each problem
is to be clearly marked. It does not matter how you read in the input
values (read from a file, command line, hardcoded values). Your
expressions can be in any convenient format. Note your binary tree,
visitors, traversal algorithms, observers, commands, etc. should work for
any valid expression using the operators listed above.