CS 2401 Assignment #13

Due Date: Thursday, May 7, 2009.

Objective: The goal of this assignment is to practice stacks and binary trees.

Assignment: Write a method that converts simple arithmetic expressions like a+b*c-d into their parse trees. A parse tree represents the way operations are actually performed. In the above example, we first compute b*c, which is represented as

   *
  / \
 b   c

then we add a to the result:

   +
  / \
 a   *
    / \
   b   c

Finally, we subtract d from the result:

     -
    / \
   +   d
  / \
 a   *
    / \
   b   c

For simplicity, assume that all the variables have one letter, there are no spaces and no parentheses.

Algorithm. The algorithm for producing a parse tree is as follows. We read the symbols forming an arithmetic expression one by one, and as we read these symbols, we form two stacks: one for the subtrees, one for operation symbols. Operation symbols have priority: * or / have higher priority than + or -.

If we encounter a variable symbol (i.e., a letter), we simply push this symbol (as the trivial tree) into the first stack.
If we encounter the operation symbol and there is nothing in the operations stack or the priority the current symbol is higher than the priority of the top symbol in the second stack, we simply push this operation symbol into the second stack.
If we are reading the operation symbol and its priority is not higher than the priority of the top symbol in the stack, then we pop the top operation symbol s from the second stack and replace the top two elements p, q in the first stack with a tree
```
   s
  / \
 p   q
```
We repeat this procedure until the priority of the top symbol in the second track become higher or the second stack is empty, at which point we push this operation symbol into the stack.
When we read the last variable symbol v, we pop the symbol s from the second stack, the tree t from the first stack, and return the tree
```
   s
  / \
 t   v
```

Example. Let us show, on the example of the above expression a+b*c-d, how this procedure works. First, we read the symbol a. According to Rule 1, we pop it into the first stack

S1: a                           S2:

The second stack is empty.

Then, we read the symbol +. Since the second stack is empty, we follow Rule 2 and push this symbol into the second stack:

S1: a                           S2: +

The symbol b is pushed into the first stack (Rule 1):

S1: a  b                        S2: +

The next symbol is *. It has higher priority than +, so, according to Rule 2, we push it into the second stack:

S1: a  b                        S2: + *

The symbol c is pushed into the first stack (Rule 1):

S1: a  b  c                     S2: + *

The next symbol - is not of higher priority than *. So, according to Rule 3, we pop *, and replace the top two symbols from the first stack with the corresponding tree:

S1: a    *                      S2: +
        / \
       b   c

The - symbol is still not of higher priority than the top symbol (+) in the second stack. So, according to Rule 3, we pop + and replace the two top elements from the first stack with the corresponding tree:

S1:   +                         S2:
     / \
    a   *
       / \
      b   c

Now, the second stack is empty. So, we follow Rule 2 and push the symbol - into this new stack.

S1:   +                         S2: -
     / \
    a   *
       / \
      b   c

The next symbol d is the last symbol of the string. So, we follow Rule 4 and return the desired tree:

     -
    / \
   +   d
  / \
 a   *
    / \
   b   c