Transcript Shunting-yard algorithm

Shunting-yard algorithm
Infix to postfix conversion
Based on http://en.wikipedia.org/wiki/Shunting_yard_algorithm
2 + (3 * (8 - 4)) = ?
How to evaluate this (or similar) formula?
TODO:
• rules should be visible and highlighted when a rule is applied
• an example containing operator precedence rules
2 + (3 * (8 - 4)) = ?
Let’s play that the tokens are train cars and we are shunting the shunting yard.
2
+
(
3
*
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
The first car is a number, it goes straight through.
2
+
(
3
*
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
Next, the third track (the stack) is empty, we move the operator there.
2
+
(
3
*
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
Left parenthesis goes always down.
2
(
+
3
*
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
Again, there is a number. It moves always straight to the left.
2
3
(
+
*
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
Next there is an operator, it goes down because the topmost car there is an parenthesis.
2
3
*
(
+
(
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
Again a left parenthesis, they go always to the stack.
2
3
(
*
(
+
8
-
4
)
)
2 + (3 * (8 - 4)) = ?
A number, straight to the left.
2
3
8
(
*
(
+
-
4
)
)
2 + (3 * (8 - 4)) = ?
A number, straight to the left.
2
3
8
-
(
*
(
+
4
)
)
2 + (3 * (8 - 4)) = ?
An operator, move it down.
2
3
8
-
(
*
(
+
4
)
)
2 + (3 * (8 - 4)) = ?
A number, to the left, as always.
2
3
8
4
(
*
(
+
)
)
2 + (3 * (8 - 4)) = ?
A right parenthesis. Now we move the cars from the bottom until there is left parenthesis.
2
3
8
4
)
(
*
(
+
)
2 + (3 * (8 - 4)) = ?
The pair of the parenthesis just disappear.
2
3
8
4
-
)
(
*
(
+
)
2 + (3 * (8 - 4)) = ?
Again, we pop out the items until there is a left parenthesis.
2
3
8
4
-
)
*
(
+
2 + (3 * (8 - 4)) = ?
A pair of parenthesis disappear.
2
3
8
4
-
*
)
(
+
2 + (3 * (8 - 4)) = ?
No more cars on the right side, so we move the cars from the bottom to the left.
2
3
8
4
-
*
+
2 + (3 * (8 - 4)) = ?
Now the transformation is done, how to evaluate it?
2
3
8
4
-
*
+
2 + (3 * (8 - 4)) = ?
Move the cars back to the right side.
2
3
8
4
-
*
+
2 + (3 * (8 - 4)) = ?
Move the cars back to the right side.
2
3
8
4
-
*
+
2 + (3 * (8 - 4)) = ?
Move the numbers to the down until we find an operator.
2
3
8
4
-
*
+
2 + (3 * (8 - 4)) = ?
When operator is found, place it to the middle so that it is between two numbers.
-
4
8
3
2
*
+
2 + (3 * (8 - 4)) = ?
Do the calculation and put the result back to down.
8
-
4
3
2
*
+
2 + (3 * (8 - 4)) = ?
Do the calculation and put the result back to down.
4
*
3
2
+
2 + (3 * (8 - 4)) = ?
Again, operator to the middle, between the two upmost numbers.
*
4
3
2
+
2 + (3 * (8 - 4)) = ?
Calculate the expression and put the result back to the down.
3
*
4
2
+
2 + (3 * (8 - 4)) = ?
Calculate the expression and put the result back to the down.
12
+
2
2 + (3 * (8 - 4)) = ?
And the last operator, it is handled in the same way.
+
12
2
2 + (3 * (8 - 4)) = ?
Calculate the result and that’s it!
2
+
12
2 + (3 * (8 - 4)) = 14
Calculate the result and that’s it!
14