red black tree

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

Page 1 of 4http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw5.html

CS 212 — Homework Five Can't see the forest...

Due: 30 October 2012, 11:59p

Worth: 75 points

Part One: Implement a Binary Tree

Worth: 15 points

The first step is to build a simple BinaryTree ADT (so it should support generics). Our needs for the tree are pretty simple, so you will only need to implement the following interface:

BinaryTree(BinaryTree<E> left, E value, BinaryTree<E> right) BinaryTree<E> getLeftChild() BinaryTree<E> getRightChild() void setLeftChild(BinaryTree<E>) void setRightChild(BinaryTree<E>) void setValue(E) E getValue() boolean isLeaf()

For this tree, you will be implementing it in "linked-list" style, as described in class. For the second part of the assignment you will be doing a lot of merging of the binary trees and that would be something of a pain that outweighs the trouble of the extra null references.

I, of course, expect to see JUnit tests included with this class.

Part Two: Parsing Expressions

Worth: 60 points

One use of trees is to build expression trees. For this assignment, you will be building an arithmetic expression tree that can represent arithmetic expressions. The idea behind expression trees is that inner nodes are operators (in our case, +,-,*,/), and the leaves are operands (either constant values or variables). The value of an expression tree is either the value stored in the node (if the node has no children) or the result of applying the operator stored in the node to its left and right subtrees. So, for example, the expression x + 5 - 6 would be represented as:

Your task will be to read in an expression, parse it into a tree, and then let the user perform some basic operations on the expression. You will create a class called ArithmeticExpression with the following

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

Page 2 of 4http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw5.html

interface:

ArithmeticExpression(String expression) [25 pts] This is the constructor. It will take a String containing the expression. The expression will contain operators (+,- ,*,/), integer constants, and arbitrary strings that should be interpreted as variables.There is no guarantee that this expression is valid. If the expression is not valid, this should throw a ParseException (be sure to indicate where you had a problem with the parse). To make your lives a little easier, the expression will be space delimitated. Being the constructor, this function should only perform the parse a build the resulting data structure (using a BinaryTree, of course).

String toString() [10 pts] This method should return a String containing the parsed expression. In this case, that means fully parenthesized according to operator precedence (i.e., * and / have higher precedence than + and -). For example, "6 + 5 * 2" should result in "(6+(5*2))". The result should contain no spaces. Hint: this should sound like some kind of traversal — what kind?

void setVariable(String name, int value) [10 pts] This allows the user to set a value for a variable in the expression. If the variable does not exist in the function, throw a NotBoundException.

int evaluate() [15 pts] Obviously, this should return the integer result of evaluating the expression. Unset variables should be considered to have the value of 0.

Example usage

Code:

ArithmeticExpression expression = new ArithmeticExpression("x + 5 * 6"); System.out.println(expression); expression.setVariable("x", 5); System.out.println(expression.evaluate()); expression.setVariable("x", 10); System.out.println(expression.evaluate());

Output:

(x+(5*6)) 35 40

Implementation details

The hardest part of this is implementing the parser that builds the expression tree so that the correct operator precedence is maintained. For example, given the expression x + y * 2, assuming that we interpret the left and right sides of the operators as left and right children, there are two trees we could build, but only one of them is correct.

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

Page 3 of 4http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw5.html

So, we can't just start chaining nodes together. Instead, we are going to use a pair of Stacks to help us out (that's right, you'll need to pull out your Stack class from the first homework). One stack will be the operator stack, and it will hold operators that we don't know how to use yet. The other stack will be a tree stack, and will hold the partial binary trees that we have not fit together yet. As we read tokens from the input expression, the operation will then be:

If the token is an operand, make it into a tree and push it on the tree stack If the token is an operator, operator stack is empty OR the operator is either * or /, push the operator on the operator stack Otherwise: While the operator stack is not empty Pop an operator from the operator stack Pop the top two trees from the tree stack Create a new tree with the two trees and the operator Push the new tree on the tree stack Push the new operator onto the operator stack When the String is consumed, repeat the above loop to clear out any unused operators

At the end, the expression tree should be sitting alone in the tree stack. Clearly, if any of the pops fail, or if there are more trees in the tree stack at the end of the process, the expression was invalid.

Another issue you will have is storing the variable values. The obvious answer would be to replace any variables in the tree with the value when they get set. Of course, then you won't be able to change the variable's value and re-evaluate the expression (which would rather remove the value of having variables there). So, we want to build a lookup table to hold the current values of all of the variables. Very soon, we will start talking about a data structure tailor-made for this purpose, but for right now we will just use an ArrayList. You will need to create some kind of inner class to hold name/value pairs. Stick these in the ArrayList and just iterate through everything to find the right entry. This isn't terribly efficient, but we are unlikely to have very many variables. Very soon, we will start talking about a data structure that is tailor-made to this, but for right now we will put up with this little bit of inefficiency.

Bonus round

I decided that I would give you the opportunity to earn a little extra credit on this one. If you chose to do any of these, be very clear that you did it in your comments, and provide appropriate test cases demonstrating them in action.

(4 points) Adjust your code so that it can handle input strings without spaces. (4 points) Handle implicit multiplication on variables (i.e., 2x + 5). (5 points) Rewrite the parser so that it can handle parentheses in the input string. You will have to think a little bit about how to handle the logic of this case since the parentheses affect the precedence of operations (i.e., they will not be represented in the tree, they will affect the structure of the tree). (5 points) Allow for unary operators. A unary operator would be an operator that takes only a single operand (i.e., -5 or +34). Again, you will have to think about how to change the logic of the parse to allow these (5 points) Write a new method called toPostfixString() that will return the expression in postfix form.

Turning the assignment in...

Commented source files and tests should be put into a single directory, zipped, tarred or jarred, and submitted online into your course dropbox on ella (I only want source files, I do not want any class files). Please name your files cs211_pid_hw5.suffix, where pid is your Mount Holyoke email account name and suffix is the appropriate suffix for your archive format.

Last modified: Tue Oct 23 18:03:05 EDT 2012

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

Page 4 of 4http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw5.html