CIT 594 Assignment 3: Trees and Expressions
Spring 2013, David Matuszek
Build a basic general-purpose API for trees. Use this API to evaluate arithmetic expressions.
Create a package named
tree, containing a
Implement and test the following constructor and methods:
public Tree(V value, Tree<V>... children)
Treewith the given
valuein 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.
public void setValue(V value)
public V getValue()
public void addChild(int index, Tree<V> child)
childas the new
index'th child of this Tree; subsequent nodes are "moved over" as necessary to make room for the new child.
IllegalArgumentExceptionif the result would be a circular tree (see below), or an
indexis negative or is greater than the current number of children of this node.
public void addChildren(Tree<V>... children)
childrento this node after any current children. Throws an
IllegalArgumentExceptionif 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
indexis 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)
node, and returns
thatNodeoccurs 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)
treeDescriptionhas the form
value(child child ... child), where a
valueis any sequence of characters not containing parentheses or whitespace, and each
childis either just a (String) value or is another treeDescription. Whitespace is optional except where needed to separate values.
becomes the Tree:
"one (two three (four five(six seven eight)) )"
public void print()
public String toString()
parsemethod expects as input.
public boolean equals(Object obj)
objis a Tree and has the same shape and contains the same values as this Tree.
|Given 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,
be rejected if
someTree already contains
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
"/", or a String representing an unsigned integer. If a node has value
"*", it must have two or more children; if a node has value
"/", 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()
"+", 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.
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
6am Sunday, February 3, via Canvas.