CIT 594 Assignment 3: Trees and Expressions
Spring 2013, David Matuszek
Build a basic generalpurpose 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:
public Tree(V value, Tree<V>... children)
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.IllegalArgumentException
. ArrayList<Tree<V>>
. public void setValue(V value)
value
.public V getValue()
public void addChild(int index, Tree<V> child)
child
as the new index
'th child of this
Tree; subsequent nodes are "moved over" as necessary to make room for the
new child.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)
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()
public Tree<V> getChild(int index)
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()
boolean contains(Tree<V> node)
==
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.private
, but I've given it package visibility
so that it can be JUnit tested.public static Tree<String> parse(String treeDescription)
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."one (two three (four five(six seven eight)) )"
becomes
the Tree:public void print()
@Override
public String toString()
parse
method expects as input.@Override
public boolean equals(Object obj)
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:

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)
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
."+"
, ""
,
"*"
, "/"
, 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."+
(5 10 ( *(15 20) 25) 30)"
Write the following methods:
public int evaluate()
int
value. "+"
, evaluate all
its children and return their sum. "*"
, evaluate all
its children and return their product. ""
, evaluate its two children and return
the first value minus the second value. "/"
, evaluate its two children
and return the first value divided by the second value.@Override
public String toString()
"(5 + 10 + ((15 * 20)  25) + 30)"
. 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.
6am Sunday, February 3, via Canvas.