CIT 594 Assignment 5: Tree API and Expression Evaluation
Spring 2015, 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.

Skeletal code can be gotten from https://github.com/DavidMatuszek/Trees-and-Expressions; the method descriptions on the rest of this page essentially duplicate what is in the code. In the event of any inconsistencies (I don't think there are any), the code on Github is correct. The provided code also contains some (complete or incomplete) helper methods; regard these as suggestions, not as requirements.

If your Eclipse/Java setup is compatible with mine, you should be able to just clone the project and import it into Eclipse. If not, you will have to download the source files and copy them into a project that you create.

The Tree API

The project on Github contains a package named tree, which contains 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..

If adding the children to the new root node would result in a structure containing a cycle (see below), throw an IllegalArgumentException. (You won't be able to perform this check until after you have written the contains method, but you can start with an initial version of the constructor that omits this check.)

Implementation note: Keep 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(Tree<V> child): Adds the child as the new last child of this Tree.

This method should throw an IllegalArgumentException if the result would be a structure containing a cycle (see below).
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 structure containing a cycle (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 structure containing a cycle (see below).
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.)
@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.
@Override public int hashCode(): If two Trees are equal, they must have the same hash code. Unequal Trees should have a high probability of having unequal hash codes.

The following methods are somewhat more difficult (especially parse):

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:

For assistance in writing this method, see Tree Parsing.

A Tree may not contain cycles. 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.

The methods toString, equals, hashCode, contains, and parse should all be written recursively.

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 as an expression. 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.

Note: Strings are not operators, and there is no way to, for instance, make the string "+" perform an addition. You have to write if statements to test what the string is, and for each string representing an operator, write code to perform the corresponding operation.

@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.

The evaluate and toString methods should be written recursively.

Other requirements

All non-private methods should be unit tested, using JUnit 4. It is strongly recommended that you follow industry best practices, and write the unit tests first (or at least concurrently).

All methods, and all non-private fields, should have good Javadoc comments. Generate the Javadoc and save it within the project. Look it over for any obvious mistakes or omissions.

Include a readme file in which you estimate, for each class, how many hours you think it will take, and how many it actually took. See if you can make a more accurate pre-estimate than in your previous assignments.

Due date

Turn your assignment in to Canvas before 6 a.m. Tuesday, February 17. Late programs, even if only a minute late, will be penalized 5 points per day, up to a maximum penalty of 50 points. Programs may not be accepted after grades have been published.