Shunting Yard Algorithm

Concept Overview

The Shunting Yard Algorithm parses standard mathematical notation (infix) into Reverse Polish Notation (postfix), where operators follow their operands. Consider the expression 3+4*2. Since multiplication has a higher precedence than addition, it must be evaluated first.

Worked Example: Converting Infix to Postfix

For the concrete input 3+4*2, multiplication must precede addition in the resulting postfix sequence. Here is the complete stack trace:

Token	Action	Stack	Output
3	Operand, push to output.	[]	3
+	Operator, push to stack.	[+]	3
4	Operand, push to output.	[+]	3 4
*	Operator. Precedence of * is > +. Push to stack.	[+, *]	3 4
2	Operand, push to output.	[+, *]	3 4 2
End	Drain stack to output.	[]	3 4 2 * +

Notice how the stack temporarily holds operators until we know whether a higher precedence operator appears next. The resulting postfix expression 3 4 2 * + correctly reflects that 4 * 2 should occur before the addition.

Experiment with Precedence and Parentheses

You can interactively trace the Shunting Yard Algorithm in the module by stepping through the tokens.

Open the Shunting Yard Algorithm module.
Set the Expression input to (1+2)*3. Notice how this changes the order compared to the default expression.
Click the Step button. The ( is pushed to the stack to act as a barrier.
Continue clicking Step. The + is pushed above the parenthesis, and operands go to the output.
When the ) is encountered, the stack pops everything until the matching parenthesis is found, flushing the + to the output.
Finally, the * is processed. Click Finish to see the complete postfix notation 1 2 + 3 *.

Limitations of this Implementation

This module strictly implements the core mechanism of the Shunting Yard algorithm on a simplified grammar, and has a few bounds:

Operands: Only single-digit integers (0-9) are supported. Multi-digit numbers or decimals are not parsed.
Unary Operators: The negative sign indicating negative numbers (e.g., -5) is rejected, as this implementation only handles binary subtraction.
Implicit Multiplication: Writing 2(3) is rejected. All operations require explicit binary operators like *.
Evaluation: This visualization produces a postfix token sequence, but it does not perform mathematical evaluation or arithmetic.

References

The core logic implemented here aligns with traditional computer science parsing techniques, as discussed in detail by established data structure literature.

Infix, Prefix and Postfix Expressions - Problem Solving with Algorithms and Data Structures using Python. This reference discusses the conversion process from fully parenthesized infix expressions to postfix expressions using stacks, explaining precedence handling which mirrors our implementation.

Shunting Yard Algorithm