CS 2401 Extra Credit Assignment #13

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

Assignment:

• Main part: write a method that, given a parse tree, computes the value of the corresponding arithmetic expression.
• Auxiliary part: write a method that converts arithmetic expressions like 9+13*2-5 into their parse trees. For simplicity, assume that there are no parentheses.
• Extra part: extend your method to arithmetic expressions with parentheses.

Background: A parse tree represents the way operations are actually performed. In the above example, we first compute 13*2, which is represented as

   *
  / \
 13  2

   +
  / \
 9   *
    / \
   13  2

     -
    / \
   +   5
  / \
 9   *
    / \
   13  2

Algorithms. The algorithm for computing the value of an expression represented by a parse tree is straightforward.

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 -.

1. If we encounter a digit, this means we have an integer. We read it digit by digit until we encounter an operation symbol, and push the resulting integer into the first stack.

2. If we encounter the operation symbol and there is nothing in the operations stack or the priority of the current symbol is higher than the priority of the top symbol in the second stack, we push the new operation symbol into the second stack.

3. 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.

4. When we read the last integer 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 9+13*2-5, how this procedure works. First, we read the digit 9. According to Rule 1, we pop the corresponding integer 9 into the first stack

 S1: 9     S2:

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

S1: 9      S2: +

The integer 13 is pushed into the first stack (Rule 1):

S1: 9 13   S2: +

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

S1: 9 13    S2: + *

The integer 2 is pushed into the first stack (Rule 1):

S1: 9 13 2    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: 9    *         S2: +
        / \
       13  2

S1:   +             S2:
     / \
    9   *
       / \
      13  2

S1:   +             S2: -
     / \
    9   *
       / \
      13  2

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

     -
    / \
   +   5
  / \
 9   *
    / \
   13  2