To Run the Program at the Command Line Type

Expression Tree Evaluator

Usage:

To run the program at the command line type:

java TreeProg

This will display a few trees that were pre-coded.

Basic Organization:

Trees are made up of nodes. These trees are predefined in the TreeProg class. The Iterator allows moving through tree in specific orders, depending on the type of Iterator defined.

Classes:

The following is a listing of the classes used in the program:

Node – A generic object in a specific location

TreeNode – A node in a tree

Int_Node – A node that holds a single integer

Unary_Node – A node that holds one operator and a tree

Binary_Node – A node that holds one operator and two trees

Ternary_Node – A node that holds one operator and three trees

Iterator – Class for iterating through a tree

PreIterator – Moves through the tree by printing in “pre-order” (current, left child, right child)

Tree – Structure that contains nodes

TreeProg – The main program

Patterns used:

Adapter

Convert the interface of a class into another interface that clients expect. Adapter lets classes work together that couldn't otherwise because of incompatible interfaces. By implementing the toString() method we are able to use the standard System.out.print(Object) method for printing.

Bridge

Decouple an abstraction from its implementation so that the two can vary independently. We created a print() method in Tree that called the abstract print() method in the Node class, and therefore the concrete print() method in the resulting nodes. This allowed us to keep the print() method in Tree while we could vary the implementation in the nodes.

Factory

Define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses. The Tree class has multiple constructors that are called based on what type of data is passed to it. The Tree also implements a createIterator(String) method that creates a given iterator for that tree.

Façade

Provide a unified interface to a set of interfaces in a subsystem. Facade defines a higher-level interface that makes the subsystem easier to use. By implementing the print() method for trees, we hide the complexity of printing each individual node in order.

Iterator

Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. An Iterator was created to display the objects in a tree in a given order. The PreIterator class visits the nodes in the tree in pre-order. This is the pattern that was chosen to extend the original C++ implementation.

Java “Tricks”:

Because we implemented the toString() method for each of the TreeNodes we are able to change the print() method to used the standard System.out.print(String) method. This allows us to move the print() method to the Node class rather than specific implementations in the children.

Observations:

Rather than creating multiple types of nodes it would be easier to create an n-ary node that allowed for multiple sub-trees related to a given operator. This modification was not implemented.