**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 cthen we add a to the result:

+ / \ a * / \ b cFinally, we subtract d from the result:

- / \ + d / \ a * / \ b cFor 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 cThe - 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 cNow, 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