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 -.
s / \ p qWe 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.
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