How to Learn the Shunting Yard Algorithm: Tokens, Operator Stacks, Precedence, Associativity and Expression Parsing

Wait, What?

A calculator does not naturally “see” 3 + 4 × 2 the way you do.

Humans read infix notation with a lifetime of convention behind us: multiplication before addition, parentheses override precedence, exponentiation is often right-associative, and a minus sign may mean subtraction or negation depending on context. A computer needs those rules made explicit.

The shunting yard algorithm, developed by Edsger W. Dijkstra, is one of the clearest ways to learn how syntax becomes structure. It reads tokens from left to right, sends operands toward the output, temporarily parks operators on a stack, and releases those operators according to precedence, associativity and parentheses.

At beginner level, it is a stack exercise. At professional level, it is a lesson in tokenisation, grammar boundaries, parser invariants, error handling and the difference between an educational expression parser and a production language frontend.

Quick Answer

Learn shunting yard in this order: infix notation → postfix notation → stack behaviour → tokens → precedence → associativity → parentheses → functions and commas → unary operators → AST construction → errors → correctness invariants → complexity → parser alternatives → production validation. Do not start by memorising pseudocode. First understand why an operator sometimes has to wait.

1. Begin with the ambiguity hidden inside familiar notation

Consider:

3 + 4 * 2

A human usually means:

3 + (4 * 2)

not:

(3 + 4) * 2

The symbols are in one order, but the operations must be executed in another. The parser therefore needs a mechanism for delaying some operators until it has enough information to place them correctly.

2. Postfix notation removes precedence ambiguity

The same expression can be written in Reverse Polish notation:

3 4 2 * +

Now evaluation is simple:

push 3;
push 4;
push 2;
apply * to the top two values;
apply + to the remaining two values.

No precedence table is needed during evaluation because the order has already been encoded.

3. The operator stack is a waiting room

When the algorithm reads an operand, that operand can usually go directly to the output. An operator may need to wait because a later operator could have higher precedence.

For:

3 + 4 * 2

the + waits. When * arrives, it also waits because it has higher precedence. At the end, * leaves before +.

The stack is not there merely because “the algorithm uses a stack.” It exists to preserve exactly the operators whose output position is not yet settled.

4. Tokenisation comes before parsing

A production parser should not usually scan one character and pretend every character is a complete token.

The expression:

12.5 + rate * sin(theta)

contains numbers, identifiers, operators, parentheses and a function call. A tokenizer should first turn the source into meaningful units such as:

NUMBER(12.5)
PLUS
IDENT(rate)
MULTIPLY
FUNC(sin)
LPAREN
IDENT(theta)
RPAREN

Shunting yard should operate on tokens, not guess lexical structure while also solving precedence.

5. Precedence answers “which operator binds tighter?”

A typical table might be:

operator   precedence
+ -        1
* /        2
^          3

When a new operator arrives, compare it with the operator on top of the stack. Higher-precedence operators already waiting on the stack may need to be emitted first.

The precise table is part of the language definition. Do not hard-code assumptions without documenting them.

6. Associativity answers a different question

Precedence is not enough when two adjacent operators have equal precedence.

Subtraction is normally left-associative:

a - b - c == (a - b) - c

Exponentiation in many mathematical systems is right-associative:

a ^ b ^ c == a ^ (b ^ c)

Therefore the pop condition differs:

for a left-associative incoming operator, pop equal-precedence operators;
for a right-associative incoming operator, do not pop merely because precedence is equal.

This is one of the most common implementation bugs.

7. Parentheses create a local barrier

When ( is read, push it onto the operator stack. Operators inside the parentheses cannot cross that boundary.

When ) is read, pop operators to the output until the matching ( is found. Then discard the parentheses themselves.

If no matching ( exists, the expression is malformed. Error handling is not optional production polish; it is part of parser correctness.

8. Core conversion pseudocode

output = []
ops = stack()

for token in tokens:
    if token is operand:
        output.append(token)

    else if token is function:
        ops.push(token)

    else if token is operator o1:
        while top of ops is operator o2 and
              (precedence(o2) > precedence(o1) or
               (precedence(o2) == precedence(o1) and
                o1 is left-associative)):
            output.append(ops.pop())
        ops.push(o1)

    else if token is '(':
        ops.push(token)

    else if token is ')':
        while top of ops is not '(':
            if ops empty: error mismatched parenthesis
            output.append(ops.pop())
        pop '('

        if top of ops is function:
            output.append(ops.pop())

while ops not empty:
    if top is parenthesis: error mismatched parenthesis
    output.append(ops.pop())

This is a conceptual skeleton. Real grammars need more detail.

9. Functions and commas add an argument boundary

For:

max(2, 3 + 4)

a comma typically means: finish operators belonging to the current function argument until the nearest left parenthesis is reached. Then continue parsing the next argument.

A production implementation may also track argument counts, empty arguments and function arity so malformed calls can be rejected clearly.

10. Unary minus is not the same operator as subtraction

Consider:

-3^2

Different languages and mathematical conventions can interpret this differently. The parser must decide whether - is unary negation or binary subtraction based on context and define its precedence relative to exponentiation.

One robust approach is for tokenisation or a small contextual pass to classify unary and binary operators separately. Treating every - token identically is a classic source of bugs.

11. You can build an AST instead of postfix output

Shunting yard is often taught as infix-to-postfix conversion, but the output can be an abstract syntax tree.

When an operator is ready, pop the required operand nodes, create a new operator node and push that node back onto an operand stack. At the end, the remaining node is the AST root.

That makes the algorithm relevant to interpreters, compilers, formula systems and query languages—not only calculators.

12. Evaluation is a separate stage

Converting infix to postfix is parsing. Evaluating the postfix result is another operation.

This separation matters because a parser may produce syntax without executing anything. A compiler may transform the AST, a symbolic algebra system may simplify it, and a query engine may compile it into another plan.

Do not merge “parse” and “execute” in your mental model unless the application deliberately uses a direct-evaluation variant.

13. A useful correctness invariant

At any point in the scan:

the output contains operands and operators whose relative order is already decided;
the operator stack contains operators that cannot yet be emitted safely;
parentheses partition regions whose internal operators must finish before outer operators can cross the boundary.

If a learner can explain that invariant, they understand more than someone who can reproduce the pseudocode from memory.

14. Complexity is linear under ordinary assumptions

Each token is read once. Each operator is pushed once and popped at most once. With constant-time stack operations and table lookups, the conversion is O(n) time and O(n) auxiliary space in the worst case.

Tokenisation costs and numeric parsing may add their own details, but the stack discipline itself is linear.

15. Error reporting separates toy parsers from useful parsers

Do not stop at “invalid expression.” Distinguish errors such as:

mismatched parentheses;
unexpected operator;
missing operand;
unexpected comma;
unknown token;
wrong function arity;
trailing tokens;
unsupported operator combination.

Track source positions in tokens so diagnostics can identify where the problem occurred.

16. How to teach shunting yard from beginner to professional

Use a staged progression based on reading, prediction and trace tables.

Predict: ask which operator should execute first in a short expression.
Run: step through a working parser on one expression.
Investigate: maintain columns for token, operator stack and output.
Modify: add exponentiation or a function and update the rules.
Make: implement a tokeniser plus parser, then validate with an independent evaluator.

Programming-education research supports worked examples, code tracing and faded scaffolding for novices before independent construction.

17. A trace table exposes reasoning

Trace:

3 + 4 * 2 / (1 - 5) ^ 2

with columns:

token | action | operator stack | output

Do not skip rows. The point is to make every precedence and parenthesis decision observable.

18. Validation should use two independent paths

For generated arithmetic expressions, compare:

your shunting-yard parser and postfix/AST evaluator;
a separate trusted expression engine or a deliberately simple reference parser.

Property-based tests can generate expressions with nested parentheses and operator combinations, then compare evaluated results where semantics are well-defined.

19. Edge cases worth forcing

single operand;
deeply nested parentheses;
right-associative exponentiation;
multiple unary operators;
function calls with zero, one and many arguments;
commas outside function calls;
empty parentheses;
very long operator chains;
numeric literals with exponents;
identifiers that resemble function names.

20. Shunting yard is not the only expression parser

Pratt parsing and precedence climbing are popular alternatives. Recursive-descent parsers can encode precedence through grammar levels. Parser generators can handle much larger grammars.

Shunting yard is especially valuable when the language is expression-heavy and operator precedence is the main structural challenge. It becomes less attractive when the grammar grows far beyond expressions.

21. Professional engineering questions

Who owns tokenisation?
Where are precedence and associativity declared?
How are unary and binary operators distinguished?
Does the parser output RPN, AST or direct evaluation?
How are source positions preserved?
How are numeric types and overflow handled?
Can user-defined operators change precedence?
What security rules apply if expressions invoke functions?

The parser should not silently take ownership of execution policy or application security.

22. Common failure states

Treating characters as tokens.
Using the same pop rule for left- and right-associative operators.
Forgetting to reject mismatched parentheses.
Confusing unary minus with subtraction.
Calling postfix evaluation part of the shunting-yard conversion without stating the extension.
Building an AST but losing source locations needed for diagnostics.
Hard-coding precedence rules that disagree with the language specification.
Using a calculator example as proof the parser can handle a real programming language.

23. Practice ladder

Beginner: convert three infix expressions to postfix by hand.
Foundation: trace the operator stack with precedence and parentheses.
Intermediate: implement conversion for numbers and five operators.
Advanced: add functions, commas, unary operators and AST output.
Professional: build a tokenised expression frontend with location-aware diagnostics, property tests, differential tests and a documented operator grammar.

24. Ownership boundary

This article owns Dijkstra’s shunting-yard approach to expression parsing: token flow, operator stacks, precedence, associativity, parentheses, postfix/AST output and parser validation. It does not replace general compiler design, full language grammars, runtime execution policy, security sandboxing, learner calibration or student-interface machinery.

Sources and further reading

Edsger W. Dijkstra, ALGOL 60 Translation: An ALGOL 60 Translator for the X1 and Making a Translator for ALGOL 60, Mathematisch Centrum report MR35, 1961: E. W. Dijkstra Archive.
Emory University Math/CS Center, “The Shunting Yard Algorithm”: teaching reference.
ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming pedagogy: SIGCSE 2019.
Yoonhee Shin et al., worked examples and metacognitive scaffolding in programming problem solving, 2023: Journal of Educational Computing Research.

Professional rule: you understand shunting yard when you can explain exactly why every operator waits or moves, define associativity without hand-waving, separate tokenisation from parsing, and reject malformed input with diagnostics precise enough for another programmer to fix the source.

Small Group Tutorials