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.

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