CIT 594 Assignment 3: Trees and Expressions
Spring 2013, David Matuszek

Purposes

To give you experience building a Tree API
To give you more experience with recursion
To teach the internal representation of expressions

General Idea

Build a basic general-purpose API for trees. Use this API to evaluate arithmetic expressions.

The Tree API

Create a package named tree, containing a Tree<V> class. Implement and test the following constructor and methods:

public Tree(V value, Tree<V>... children): Constructs a Tree with the given value in the root node, having the given children. Note that this constructor uses a var parameter; if you have not used var parameters before, now is your chance to learn about them.

If adding the children to the new root node would result in a circular tree (see below), throw an IllegalArgumentException.

Implementation note: I recommend keeping the children of a node in an ArrayList<Tree<V>>.
public void setValue(V value): Sets the value in this node to the given value.
public V getValue(): Returns the value in this node.
public void addChild(int index, Tree<V> child): Adds the child as the new index'th child of this Tree; subsequent nodes are "moved over" as necessary to make room for the new child.

This method should throw an IllegalArgumentException if the result would be a circular tree (see below), or an IndexOutOfBoundsException if index is negative or is greater than the current number of children of this node.
public void addChildren(Tree<V>... children): Adds the new children to this node after any current children. Throws an IllegalArgumentException if the result would be a circular tree (see below). This method also uses a var parameter.
public int getNumberOfChildren(): Returns the number of children that this node has
public Tree<V> getChild(int index): Returns the index'th child of this node.. Throws an IndexOutOfBoundsException if index is negative or is greater than or equal to the current number of children of this node.
public Iterator<Tree<V>> iterator(): Returns an iterator for the children of this node. (Hint: One line.)

The following methods are somewhat more difficult:

boolean contains(Tree<V> node): Searchs this Tree for a node that is == to node, and returns true if found, false otherwise. Example: thisTree.contains(thatNode) tests whether thatNode occurs somewhere in thisTree. It is important to note that we are looking for this same node, not just an equal node.

Note: This method should normally be private, but I've given it package visibility so that it can be JUnit tested.
public static Tree<String> parse(String treeDescription): Translates a String description of a tree into a Tree<String> object. The treeDescription has the form value(child child ... child), where a value is any sequence of characters not containing parentheses or whitespace, and each child is either just a (String) value or is another treeDescription. Whitespace is optional except where needed to separate values.

For example, the String "one (two three (four five(six seven eight)) )" becomes the Tree:
public void print(): Prints a multiline version of the tree (see below).
@Override public String toString(): Returns a String representing this Tree. The returned String must be in the same format as the parse method expects as input.
@Override public boolean equals(Object obj): Returns true if obj is a Tree and has the same shape and contains the same values as this Tree.

Given this Tree:

toString() should return:
one(two three(four five(six seven eight)))

print() should print:

one
|  two
|  three
|  |  four
|  |  five
|  |  |  six
|  |  |  seven
|  |  |  eight

A Tree may not contain loops. That is, there must be no path from a node in the Tree back to itself. To prevent this, care must be taken when adding children to a node. In particular, someNode.addChild(someTree) must be rejected if someTree already contains someNode. To avoid this problem, use your contains method whenever you construct a new Tree or add children to an existing Tree.

Expressions

In a separate Expression class, write the following constructor:

public Expression(String expression): Constructs a Tree<String> representing the given arithmetic expression, using the Tree.parse(String) method, then verifies that the newly created Tree is valid. If the Tree is invalid, the constructor throws an IllegalArgumentException.

Here are the validity rules: The value of each node must be one of "+", "-", "*", "/", or a String representing an unsigned integer. If a node has value "+" or "*", it must have two or more children; if a node has value "-" or "/", it must have exactly two children; and if a node contains a numeric string, it must be a leaf.

Note that the input parameter uses prefix notation, for example: "+ (5 10 -( *(15 20) 25) 30)"

Write the following methods:

public int evaluate()

Evaluates this Expression and returns the result. The rules for evaluation are as follows:

If the value of the node is a numeric string, return its int value.
If the value of the node is "+", evaluate all its children and return their sum.
If the value of the node is "*", evaluate all its children and return their product.
If the value of the node is "-", evaluate its two children and return the first value minus the second value.
If the value of the node is "/", evaluate its two children and return the first value divided by the second value.

@Override public String toString()

Returns an infix String representation of this Expression. For example, the example in the constructor might be returned as "(5 + 10 + ((15 * 20) - 25) + 30)". Excess (unnecessary) parentheses are perfectly acceptable; but you must have enough parentheses to correctly represent the expression.

JUnit and Javadoc

This is an API for possible use by other people. All public methods should be well and thoroughly documented.

All methods, except print which does I/O, should be unit tested. Pay special attention to all "edge" cases.

Due date

6am Sunday, February 3, via Canvas.