CS210
Fall 2007

Programming Project 3

 

Date: Tuesday, November 06, 2007.

Due: Wednesday November 21, 2007.

 

 

A Binary Expression Tree is used to represent arithmetic expressions (addition, subtraction, multiplication and division). It is a special kind of binary tree in which:

 

1.  Each leaf node contains a single operand (an integer)

 

2.  Each non-leaf node contains a single binary operator ( '+', '-', '*' or '/'), and

 

3.  The left and right subtrees of an operator node represent subexpressions that must be evaluated before applying the operator at the root of the subtree.

 

The Expression Tree class should include methods to:

-         Build an expression tree from an arithmetic expression read as input in infix form, like ( 3 + 41 ) * 2. Also, assume that the expression does not include any redundant parentheses. In other words, expressions like 3.2 + ( ( 2 * 4 ) ) and 64 - ( 2 / 3 ( ) ) are not legal. Your program does not have to handle these illegal expressions.

-         Evaluate the expression tree.

-         Print the nodes of the tree in graphical form, preorder, postorder and inorder formats as described in class.

 

How do you build an expression tree from an infix expression?

In broad strokes the algorithm has two steps:

1. convert the infix expression to a postfix expression
2. convert the postfix expression to an expression tree

Infix to postfix

Here is how to convert an infix expression to a postfix one (this algorithm is called precedence operator parasing):

1. Examine the next element in the input.
2. If it is an operand, hold it in a string stream.
3. If it is an opening parenthesis, push it on to stack (since it's of lowest priority).
4. If it is an operator, then
1. If stack is empty, push operator on stack.
2. If the top of the stack is an opening parenthesis, push operator on stack.
3. If it has higher priority than the top of stack, push operator on stack.
4. Else pop the operator from the stack and put it in the stream. Repeat step 4.
5. If it is a closing parenthesis, pop operators from the stack and output them until an opening parenthesis is encountered; pop and discard the opening parenthesis.
6. If there is more input go to step 1
7. If there is no more input, unstack the remaining operators to output.

 

Postfix to tree

Here is how to convert a postfix expression into an expression tree:

1. Examine the next element in the input.
2. If it is an operand then
1. create a leaf node, i.e. a node having no child
2. copy the operand in data part
3. PUSH node's address on stack
3. If it is an operator, then
1. create a node
2. copy the operator in data part
3. POP address of node from stack and assign it to node->right
4. POP address of node from stack and assign it to node->left
5. PUSH new node's address on stack
4. If there is more input go to step 1
5. If there is no more input, POP the address from stack, which is the address of the ROOT node of Expression Tree.

Evaluating the Expression

Now that the expression is represented as a binary tree, it is extremely easy to evaluate using a recursive method. Simply evaluate the left child and the right child of the root node, then combine the results using the operator stored in the root node.

The data member of the binary node is either a number (if the node contains an operand) or a character (if the node contains an operator. One way to solve this is to have in our expression tree node, a variable that keeps track of what kind of node it is. We store both the value and the operators as numbers, just to make storage a little easier. Note that we have two constructors that build an operator node (if the constructor is sent a number and two pointers) and an operand node (if the constructor is only sent a number).

 

Work in groups of 2-3 students to:

 

1.    Implement the Binary Tree class template in the files BinaryTree.h and BinaryTree.cpp. You may only include methods that will be needed for the class Expression Tree.

2.    Derive the Expression Tree class from the Binary Tree class in the files ExpressionTree.h and ExpressionTree.cpp. Note that since BinaryTree is a template class, you might need to include it's implementation file rather than the header file.

3.    You are free to use the <stack> class from the STL library, or, you may also use your own implementation of the stack.

4.    Write a client program that uses the Expression tree ADT above to:

1.    Read an arbitrary arithmetic expression from the input terminal, display that expression, and build the corresponding expression tree.

2.    Evaluate the expression from the tree.

3.    Display the expression tree in graph form.

4.    Print the expression in the three standard formats: infix, prefix and postfix.