Back
+20 XP
Concept

Operator Precedence & The Shunting-Yard Algorithm

Dijkstra's Shunting-Yard algorithm converts infix math expressions (`3 + 4 * 2`) into Postfix / Reverse Polish Notation (`3 4 2 * +`) using an operator stack, resolving operator precedence in $O(N)$ linear time 🚂.

python
def shunting_yard(tokens):
    prec = {'+': 1, '-': 1, '*': 2, '/': 2}
    out, ops = [], []
    for t in tokens:
        if t.isdigit():
            out.append(t)
        elif t in prec:
            while ops and ops[-1] in prec and prec[ops[-1]] >= prec[t]:
                out.append(ops.pop())
            ops.append(t)
    while ops:
        out.append(ops.pop())
    return out

tokens = ['3', '+', '4', '*', '2']
print(f"Postfix: {' '.join(shunting_yard(tokens))} 🚂")

# 74. Operator Precedence & The Shunting-Yard Algorithm Dijkstra's Shunting-Yard algorithm converts infix math expressions (`3 + 4 * 2`) into Postfix / Reverse Polish Notation (`3 4 2 * +`) using an operator stack, resolving operator precedence in $O(N)$ linear time 🚂. ```python def shunting_yard(tokens): prec = {'+': 1, '-': 1, '*': 2, '/': 2} out, ops = [], [] for t in tokens: if t.isdigit(): out.append(t) elif t in prec: while ops and ops[-1] in prec and prec[ops[-1]] >= prec[t]: out.append(ops.pop()) ops.append(t) while ops: out.append(ops.pop()) return out tokens = ['3', '+', '4', '*', '2'] print(f"Postfix: {' '.join(shunting_yard(tokens))} 🚂") ``` Once converted to postfix notation, evaluating the expression is trivial: push numbers onto a stack, pop operands when an operator appears, and push the result back ⚡! --- ### Question What makes Postfix (Reverse Polish Notation) expressions easier for stack-based execution than Infix notation? 🧠 - [ ] a. Postfix completely removes parentheses and precedence rules; evaluation is a single linear stack pass 🚂 - [ ] b. Postfix expressions consume 50% fewer bytes of RAM - [ ] c. Postfix strings execute natively on GPU shaders without parsing - [ ] d. Postfix notation mathematically prevents division by zero --- ### Challenge Implement `shunting_yard(tokens)` for `+` and `*`. Convert `['3', '+', '4', '*', '2']` into postfix tokens. Print the list. 🎯 <details> <summary>Solution</summary> ```python def shunting_yard(tokens): prec = {'+': 1, '*': 2} out, ops = [], [] for t in tokens: if t.isdigit(): out.append(t) elif t in prec: while ops and ops[-1] in prec and prec[ops[-1]] >= prec[t]: out.append(ops.pop()) ops.append(t) while ops: out.append(ops.pop()) return out print(shunting_yard(['3', '+', '4', '*', '2'])) ``` </details>

Checkpoint

What makes Postfix (Reverse Polish Notation) expressions easier for stack-based execution than Infix notation? 🧠

Practice

Implement `shunting_yard(tokens)` for `+` and `*`. Convert `['3', '+', '4', '*', '2']` into postfix tokens. Print the list. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks