CIT
594 Assignment
7: Building Trees Spring 2008, David Matuszek |

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

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

Create a package named `tree`

, containing a `Tree<V>`

class.
Implement and test the following constructor and methods:

The following methods are somewhat more difficult:

`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 avar 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.)

`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 thissamenode, not just anequalnode.

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`becomes the Tree:`

"one (two three (four five(six seven eight)) )"

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

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.

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 usesprefixnotation, 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
infixString representation of this Expression. For example, the example in the constructor might be returned asExcess (unnecessary) parentheses are perfectly acceptable; but you must have enough parentheses to correctly represent the expression. `"(5 + 10 + ((15 * 20) - 25) + 30)"`

.

Required, as usual.

Zip the complete project and submit via Blackboard before midnight Monday, March 24.