-
Notifications
You must be signed in to change notification settings - Fork 0
Shunting Yard Algorithm
This Documentation is a Summary/Overview of the Shunting-Yard Algorithm.
Below is a link to view for further review/reference:
https://en.wikipedia.org/wiki/Shunting-yard_algorithm.
What is the Shunting-Yard Algorithm?
The Shunting-Yard Algorithm is a methodical procedure that is used commonly to parse mathematical/logical expressions in "Infix Notation" (i.e., where the operators are embedded within the expressions itself) and transform them into "Reverse Polish Notation" (i.e., where the operators follow strictly after all of the operands).
Essentially, at each iteration of the algorithm, the Shunting-Yard examines a single, current character in the expression and based on its value, appropriately handles it. In fact, to correctly form the expression in Reverse Polish Notation, the procedure maintains a Stack for all of the operators/parenthesis it encounters in the input expression as well as an Output Queue which will store the newly-created expression in Reverse Polish Notation. Below is a summary of the cases the Shunting-Yard Algorithm handles for each character:
Case 1: Current Character = Operand
- In this case, we simply push the character to the Output Queue.
- By Operand, we mean to say that we are dealing with a numerical value/atomic symbol.
Case 2: Current Character = Operator
- In this case, we cannot simply just push the character to the Current Stack.
- Specifically, we must account for the >= precedence operators that currently reside at the top of the Stack and accordingly push them to the Output Queue, prior to pushing the current character to the Current Stack.
- Further, it is important to realize that one must explicitly define the precedence of the operators depending on the specific application (i.e., mathematical operators v. logical operators, etc.).
Case 3: Current Character = "("
- In this case, we simply push the character to the Current Stack.
Case 4: Current Character = ")"
- In this case, we DO NOT simply push the character to the Current Stack.
- With the ")", we must pop off all characters from the Current Stack and push them onto the Output Queue until we reach a "(".
- If we reach a "(", we ought to now remove it from the Current Stack.
- Overall, this process signifies that we have dealt with a sub-expression (i.e., expression starting with "(" and ending with ")").
Here is an example to demonstrate the algorithm in action.
Example: (1 - (2 + 3)) * 4
Iteration #1: Add ( To The Current Stack
Current Stack: (
Output Queue:
Iteration #2: Add 1 To The Output Queue
Current Stack: (
Output Queue: 1
Iteration #3: Add - To The Current Stack
Current Stack: ( -
Output Queue: 1
Iteration #4: Add ( To The Current Stack
Current Stack: ( - (
Output Queue: 1
Iteration #5: Add 2 To The Output Queue
Current Stack: ( - (
Output Queue: 1 2
Iteration #6: Add + To The Current Stack
Current Stack: ( - ( +
Output Queue: 1 2
Iteration #7: Add 3 To Output Queue
Current Stack: ( - ( +
Output Queue: 1 2 3
Iteration #8: Remove (, + From Current Stack/Add + To Output Queue
Current Stack: ( -
Output Queue: 1 2 3 +
Iteration #9: Remove (, - From Current Stack/Add - To Output Queue
Current Stack:
Output Queue: 1 2 3 + -
Iteration #10: Add * To Current Stack
Current Stack: *
Output Queue: 1 2 3 + -
Iteration #11: Add 4 To Output Queue
Current Stack: 4
Output Queue: 1 2 3 + - 4
Iteration #12: Remove * From Current Stack/Add * To Output Queue
Current Stack:
Output Queue: 1 2 3 + - 4 *
Final Output Queue: 1 2 3 + - 4 *
All in all, with respect to the ALPACA Logic Engine Project and most situations dealing with Expression Parsing, the main motivation for the Shunting-Yard Algorithm is due to the fact that once an expression is in Reverse Polish Notation, it can easily be converted into a Expression Tree which is great for storing/evaluating/traversing expressions. On top of this, unlike our current recursive parsing implementation taking O(n log n) Time, the Shunting-Yard Algorithm examines each character only once, leading to an efficient, and most optimal O(n) Time.