CSE 326 - Winter 2003

Assignment 2

Assigned: Wednesday, Jan. 22
Due: Friday, Jan. 31, 11:00am

This is a group assignment. You can work in groups of 2 or 3. Read all the specifications carefully.

This assignment is designed to help you become familiar with implementing binary trees and stacks and using them in solving a problem. The objective of the assignment is to represent postfix expressions using binary trees and manipulate them.

Postfix expressions

The conventional way of writing expressions is called infix notation. The arithmetic operators appears between the two operands. Parentheses are required to specify the order of the operations. For example: 
((x * x) + 2)/(x + 1)
Postfix notation (also known as reverse Polish notation) eliminates the need for parentheses. In this notation, the operator is written after the operands. There are no precedence rules to learn, and parentheses are never needed. For example, the above expression can be written as: 
x x * 2 + x 1 + /

Expression Trees

To easily manipulate postfix expressions, they are converted into and stored as expression trees. In an expression tree, each non-leaf node is an operand and leaf nodes are values. For example, the expression above can be represented as: 
             [/]
             / \
            /   \
           /     \
         [+]      [+]
         /\       / \
        /  \     /   \
      [*]  (2) (x)   (1)
     /  \
    /    \
  (x)    (x)

Problem Specification

Write a Java (or C++) program to implement a class ExpTree suitable for representing expression trees. Implement the following methods in the class:
  1. void parsePostfix(String expression)

    The expression would consist of (possibly multiple occurrences of) a single variable (x), any single digit (representing a value 0, ..., 9), and the four operands (+, -, *, /). To construct the tree, use the following algorithm:

    1. Create a Stack
    2. Read next input symbol
    3. If the symbol is a numeric value or a variable, create a new expression tree with a single node representing the value/variable and push it into the stack.
    4. If the symbol is an operator, pop out two trees (T1 and T2) from the stack. Create a new tree with the operator as the root and T1 and T2 as two children. Push this new tree back into the stack.
    5. Repeat this procedure until the whole input is read.
    6. At the end, the stack will contain a single tree which would be the output.

    You should implement a class ExpStack suitable for representing a Stack whose elements are objects of ExpTree. You can read Chapter 4.2.2 in Weiss for details.

  2. double evaluate(double xval)
    The method should evaluate the expression for the given value xval of the variable x. (HINT: use recursion.)
  3. ExpTree derivate()
    The method creates a new ExpTree which is the derivative of given expression tree. Implement the method using recursion and the following rules:
  4. String toInFix()
    The method prints the given expression using infix notation and by adding parentheses.
  5. In the main method, write the following code for testing: 
        ExpTree expt = new ExpTree();
    expt.parsePostfix("x x * 2 + x 1 + /");
    System.out.println(expt.evaluate(3)); 
    System.out.println(expt.toInfix()); 
    System.out.println(expt.derivate().toInfix());

Turnin Instructions

One submission per group is sufficient. The names of all the group members, as well as the sections they attend, must be included with the submission.

For this homework, you will need to turn in the two files, ExpTree.java and ExpStack.java, with the corresponding classes, as well as any other .java files that are used. For sections AA/AB: if you program in C++, you should submit all the relevant .cpp and header files instead.

You must submit your files electronically by the above deadline. Follow these electronic turnin instructions.

Paper printouts of your files are due at the beginning of class on the same day (Friday, 1/31). You are encouraged to print double-sided, for example, with the following command, which sends your files from Unix to the printer in Sieg 232: 
	enscript -2r -G -p - ExpTree.java ExpStack.java | lpr -Zduplex -Pps232