CoreSource checked

Shunting Yard Algorithm

Converts infix expressions to postfix form using operator and output stacks.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Parsing
Difficulty: Intermediate
Family: Expression Parsing
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 2
Code example: Ready
Visualization: Ready

Overview

The Shunting Yard Algorithm handles precedence and associativity by moving operators from an operator stack to an output queue.

Core Concepts

operator stackprecedence ruleassociativity ruleoutput queueparse stateoperator precedencestack stateexpression parsing

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

When to Use

Use Shunting Yard Algorithm when you need to read tokens from an infix expression.
Use it for calculator parsers with inputs like expression tokens.
Use it when text or tokens must be turned into a reliable structured representation.
Use it when the Expression Parsing tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the grammar is ambiguous or left-recursive in ways the parser cannot handle.
Avoid it when the required output is not postfix expression.

What It Does

Reads tokens from an infix expression
Orders operators by precedence in postfix output

Use Cases

Calculator parsers
Expression evaluators
Teaching operator precedence

Inputs

Expression tokens
Operator precedence and associativity

Outputs

Postfix expression
Optional expression tree

Pseudocode

1.Send operands directly to output
2.Push operators onto the operator stack
3.Pop higher-precedence operators before pushing a lower one
4.Handle parentheses by pushing and popping markers
5.Drain remaining operators to output

Canonical Example

Input: tokens = ['2', '+', '3', '*', '4']
Output: structured expression tree or evaluated result
Explanation: Shunting Yard Algorithm: The parser uses grammar or precedence rules to recover structure from tokens.

Implementation Notes

Keep the input contract explicit: Expression tokens; Operator precedence and associativity.
Keep tokenization separate from parsing unless the algorithm explicitly combines them.
Keep lexical analysis separate from parsing unless the method explicitly combines them.

Common Pitfalls

The algorithm is named after railroad shunting yards.
Producing unclear errors that do not point to the token or rule that failed.
Handle empty, invalid, and boundary inputs before trusting postfix expression.
Mixing token positions, character offsets, and grammar states can produce misleading parse errors.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show tokens moving between an operator stack and output queue.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Send operands directly to output

operator-stack-output

Notes

Shunting Yard Algorithm operates in O(n) time and O(n) space within the Expression Parsing family. Often compared with Pratt Parsing and Dijkstra's Two-Stack Algorithm.