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.