CSIS 3103 - Lab 5 : Evaluating Expression Trees
Nov 17, 2010

You can work in pairs for this lab.

Objectives:

• Practice with binary trees
• Practice with recursion
• Practice with expression trees

(This lab is based on Programming Project 1. on p. 356)

You will need the BinaryTree.java file in your project to complete this lab.

ExpressionTree

Complete the following class as described below:

public class ExpressionTree {

   /** Initialize this expression tree with exp
    * @param exp The expression tree 
    */
   public ExpressionTree(BinaryTree exp) {
      // TODO: Complete this method
   }

    /** Evaluates this expression tree
    * @return The value if this expression tree
    */
   public int evaluate() {
      // TODO: Complete this method
   }
}

The ExpressionTree class needs a data field that is a BinaryTree which will store the expression to be evaluated. Note that in an expression tree, the interior nodes contain operators and the leaf nodes contain operands. For this exercise, all operands will be integers.

The evaluate method should implement the following algorithm:

if the root node is a leaf
   Return the value in the root
else
   Evaluate the left subtree
   Evaluate the right subtree
   Return the value obtained by applying the operator in the root to the results of the previous two steps

Note that private helper methods will be needed.

Driver

Add a class with a main method that reads an expression tree from a file and uses an ExpressionTree to evaluate it.

An expression tree representing (10 + 6) * (28 / 4) is in the file: expr.txt.

Use this to test your implementation.

Also make a file to represent the expression:  25 + (12 + 9 * 4 - 10) * 8

Test your Implemention with this expression also

Hand In:

Submit the completed  ExpressionTree class and the data file for the second expression.