Dijkstra’s Two-Stack Algorithm, In Plain English Language Words:
You need two stacks, a value stack (operands), and an operator stack. Numbers will be double values, operators will be char values. The whole of the expression is made up of items - the “stuff”, ignoring whitespace.
- While there are still items to read
- Get the next item
- If the item is:
- A number: push it onto the value stack.
- A left parenthesis: push it onto the operator stack.
- A right parenthesis:
- While the top of the operator stack is not a left parenthesis
- Pop the operator from the operator stack.
- Pop the value stack twice, getting two operands.
- Apply the operator to the operands, in the correct order.
- Push the result onto the value stack.
- Pop the left parenthesis from the operator stack
- An operator op:
- While the operator stack is not empty, and the top of the operator stack has the same or greater precedence as op,
- Pop the operator from the operator stack.
- Pop the value stack twice, getting two operands.
- Apply the operator to the operands, in the correct order.
- Push the result onto the value stack.
- Push op onto the operator stack.
- While the operator stack is not empty,
- Pop the operator from the operator stack.
- Pop the value stack twice, getting two operands.
- Apply the operator to the operands, in the correct order.
- Push the result onto the value stack.
- At this point the operator stack should be empty, and the value stack should have only one value in it, which is the final result.
You can see a lot of opportunity here for helper methods and for more efficiency, but the logic is clean and intuitive. In any case, once I got over myself and learned a bit, I re-implemented the puzzle solution. Here is a part of what I ended up with, that represents the algorithm above:
It’s not fancy but it really helped me understand stacks and arithmetic expressions. It was also pointed out to me that this algorithm could be expressed recursively, by using the stack frames as a way to express “stack”…so perhaps a project for the future. My original puzzle solution was recursive, but not nearly so elegant.
Worked out Example:
Convert the expression X-Y+Z*P-Q+X+Y to postfix notation using Dijkstra’s algorithm. Show the steps involved. Is the result equivalent to(X-Y)+Z(P-Q)+X+Y or X-(Y+Z)P-(Q+X)+Y? Does it matter?
Dijkstras algorithm for converting to postfix :
We use an empty stack initially for this method and the symbols are read one by one
The golden rule in this algorithm is
If the token is an operator, *, /, +, or -, push it on the stack. However, first remove any operators already on the opstack that have higher or equal precedence and append them to the output list.
If the token is a left parenthesis, push it on the stack.
If the token is a right parenthesis, pop the stack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
Given expression is: X-Y+Z*P-Q+X+Y. The action for each symbol is shown below
--------------------------------------------------------------------------------------------------------------------
X its an operand so just print it out or write it down
- its an operator and the stack is empty initially so push it into the stack
Y its an operand so just print it out or write it down
+ its an operator and has equal precedence to minus so pop the minus first and push to stack
Z its an operand so just print it out or write it down
* its an operator and has no higher or equal to prcedence operator in stack hence push it into stack
P its an operand so just print it out or write it down
- its an operator and * has higher precdence so pop * ; equal to + so pop + as well then push -
Q its an operand so just print it out or write it down
+ its an operator and has equal precedence to minus so pop the minus first and push to stack
X its an operand so just print it out or write it down
+ its an operator and has equal precedence to plus so pop the plus first and push to stack
Y its an operand so just print it out or write it down
+ is still remaining in the stack hence pop it out
---------------------------------------------------------------------------------------------------------------------------------
After converting to postfix: X Y - Z P * + Q - X + Y +
Similarly by converting the given other two expressions to postfix,we find that none of them are equivalent to other
First Alternative: (X-Y)+Z*(P-Q)+X+Y
Postfix Expression: X Y - Z P Q - * + X + Y +
Second Alternative: X-(Y+Z)*P-(Q+X)+Y
Postfix Expression: X Y Z + P * - Q X + - Y +
Yes the paranthesis matter in most of the scenarios especially when there are lots of additive/subractive and multiplicative/division operators in the expression.
First Alternative Sample for paranthesis example:
( push into stack
X its an operand so just print it out or write it down
- its an operator ,push into stack
Y its an operand so just print it out or write it down
) pop the only operator minus untill the left paranthesis
+ push into the stack
Z its an operand so just print it out or write it down
* no other higher operator in stack, push into the stack
( push to the stack
P its an operand so just print it out or write it down
- push into the stack
Q its an operand so just print it out or write it down
) pop the only operator minus untill the left paranthesis
+ since * operator is higher precedence pop it and then push +
X its an operand so just print it out or write it down
+ pop the previous + and then push the current plus into stack
Y its an operand so just print it out or write it down
since the last plus is still remaining pop it out to complete the expression