Common Stack Patterns - Learning Module

Loading content...

0/276

Expression Evaluation Intuition

The Engine Behind Every Calculator

When you type 2 + 3 * 4 into a calculator, how does it know to multiply before adding? When a compiler sees (a + b) * (c - d), how does it generate the correct machine code? The answer is stacks—specifically, stack-based expression evaluation algorithms that have powered computing since the 1950s.

Expression evaluation is where all the stack patterns we've learned converge:

Reversal — Converting between expression notations
State tracking — Managing operator precedence and parentheses
Function simulation — Evaluating nested expressions like recursive calls

In this page, we'll develop intuition for how expressions are parsed and evaluated, focusing on the concepts rather than memorizing algorithms. You'll understand why stacks are essential for this domain.

What You Will Master

By the end of this page, you will understand the three expression notations (infix, prefix, postfix), why postfix is ideal for stack-based evaluation, the intuition behind postfix evaluation, operator precedence handling, and how these concepts underpin compilers and calculators.

The Three Expression Notations

Before diving into evaluation, we need to understand that the same mathematical expression can be written in three different notations:

1. Infix Notation (Human-Friendly)

This is what we use naturally: A + B, 3 * (4 + 5). The operator sits between its operands.

2. Prefix Notation (Polish Notation)

The operator comes before its operands: + A B, * 3 + 4 5. Named after Polish logician Jan Łukasiewicz.

3. Postfix Notation (Reverse Polish Notation - RPN)

The operator comes after its operands: A B +, 3 4 5 + *. This is what many calculators use internally.

The Same Expression in Three Notations
Infix (Human)	Prefix (Polish)	Postfix (RPN)
A + B	A B	A B +
A + B * C	A * B C	A B C * +
(A + B) * C	A B C	A B + C *
A * (B + C)	A + B C	A B C + *
(A + B) * (C - D)	A B - C D	A B + C D - *

The Key Insight

Infix notation requires parentheses and operator precedence rules to be unambiguous. Prefix and postfix notations are inherently unambiguous—no parentheses needed! This makes them ideal for machine processing.

Why Does Postfix Matter?

Postfix notation has a remarkable property: it can be evaluated left-to-right with a single stack, with no need to look ahead or manage precedence. When you encounter:

A number → Push it
An operator → Pop operands, compute, push result

This simplicity is why RPN calculators (like HP scientific calculators) and stack-based virtual machines (like the JVM) use postfix internally.

Why Infix Is Hard for Computers

Infix notation presents several challenges for automated evaluation:

Challenge 1: Operator Precedence

In 2 + 3 * 4, we must know that * has higher precedence than +, so we compute 3 * 4 = 12 first, then 2 + 12 = 14.

Challenge 2: Associativity

What is 8 - 3 - 2? Is it (8 - 3) - 2 = 3 or 8 - (3 - 2) = 7? Associativity rules (left-to-right for subtraction) resolve this.

Challenge 3: Parentheses

Parentheses override precedence: (2 + 3) * 4 = 20, not 14. We must track open parentheses and match them correctly.

Challenge 4: Look-Ahead Requirement

When we see 2 +, we can't immediately compute—we need to see what comes next to know if a higher-precedence operator follows.

infix-ambiguity.txt

Example

Expression: 2 + 3 * 4
 
Reading left-to-right:
  See '2' → operand
  See '+' → operator, but wait...
  See '3' → operand, but wait...
  See '*' → operator with HIGHER precedence than '+'!
  See '4' → operand
  
Must compute 3 * 4 = 12 FIRST
Then compute 2 + 12 = 14
 
Without look-ahead and precedence tracking,
a left-to-right pass would incorrectly compute:
  (2 + 3) * 4 = 20  ← WRONG!
 
Solution: Convert to postfix first, then evaluate
  Postfix: 2 3 4 * +
  Evaluation:
    Push 2 → [2]
    Push 3 → [2, 3]
    Push 4 → [2, 3, 4]
    See * → pop 4, 3; push 12 → [2, 12]
    See + → pop 12, 2; push 14 → [14]
  Result: 14 ✓

The Two-Stack Strategy

Many compilers use a two-step approach: (1) Convert infix to postfix using precedence rules, (2) Evaluate the postfix expression with a simple stack algorithm. Both steps use stacks—one for operators during conversion, one for operands during evaluation.

Postfix Evaluation: The Simple Algorithm

Evaluating a postfix expression is beautifully simple:

Algorithm:

for each token in expression:
    if token is a number:
        push it onto the stack
    if token is an operator:
        pop the required operands
        apply the operator
        push the result

final result = pop from stack

That's it! No precedence tracking, no parentheses handling, no look-ahead. The postfix format encodes all that information in the ordering.

postfix-eval.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def evaluate_postfix(expression: str) -> float:
    """
    Evaluate a postfix (RPN) expression.
    
    Tokens are space-separated for simplicity.
    Supports: +, -, *, /
    
    Time: O(n) - single pass
    Space: O(n) - stack holds operands
    """
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
    }
    
    for token in expression.split():
        if token in operators:
            # Operator: pop two operands (note order!)
            b = stack.pop()  # Second operand (top of stack)
            a = stack.pop()  # First operand
            result = operators[token](a, b)
            stack.append(result)
        else:
            # Number: push onto stack
            stack.append(float(token))
    
    return stack.pop()
 
 
# Test cases
print(evaluate_postfix("2 3 +"))           # 5.0 (2 + 3)
print(evaluate_postfix("2 3 4 * +"))       # 14.0 (2 + 3*4)
print(evaluate_postfix("2 3 + 4 *"))       # 20.0 ((2+3) * 4)
print(evaluate_postfix("5 1 2 + 4 * + 3 -"))  # 14.0 (5 + (1+2)*4 - 3)

Trace Through: "2 3 4 * +" (equivalent to 2 + 3 * 4)

Postfix Evaluation Step-by-Step
Token	Action	Stack After
2	Push number	[2]
3	Push number	[2, 3]
4	Push number	[2, 3, 4]
	Pop 4, 3; Push 3*4=12	[2, 12]
	Pop 12, 2; Push 2+12=14	[14]

Operand Order Matters!

For non-commutative operators (- and /), the order matters. In postfix 'A B -', the result is A - B, not B - A. The first operand pushed is on the bottom, so after popping, the bottom value (A) is the left operand and the top value (B) is the right operand.

Infix to Postfix: The Shunting-Yard Intuition

Edsger Dijkstra invented the Shunting-yard algorithm in 1961 to convert infix to postfix. The name comes from railroad shunting yards where train cars are reorganized.

Core Intuition:

Numbers go directly to output. Operators go to a holding stack, but they're released to output based on precedence:

When you see an operator, pop any operators on the stack with higher or equal precedence to output first
Parentheses create temporary precedence boundaries

The Mental Model:

Imagine operators are train cars waiting on a siding. A new operator arrives:

If the new operator is "weaker" (lower precedence), let the stronger operators go to the output first
If the new operator is "stronger," it gets to wait on the siding
When parentheses close, everything inside must be flushed to output

shunting-yard-simplified.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def infix_to_postfix(expression: str) -> str:
    """
    Convert infix expression to postfix using Shunting-yard algorithm.
    
    Simplified version: single-char tokens, basic operators.
    """
    output = []
    operator_stack = []
    
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    
    for char in expression:
        if char.isspace():
            continue
        elif char.isalnum():
            # Operand goes directly to output
            output.append(char)
        elif char == '(':
            # Push opening parenthesis onto operator stack
            operator_stack.append(char)
        elif char == ')':
            # Pop until matching '('
            while operator_stack and operator_stack[-1] != '(':
                output.append(operator_stack.pop())
            operator_stack.pop()  # Remove the '('
        elif char in precedence:
            # Pop operators with >= precedence
            while (operator_stack and 
                   operator_stack[-1] != '(' and
                   operator_stack[-1] in precedence and
                   precedence[operator_stack[-1]] >= precedence[char]):
                output.append(operator_stack.pop())
            operator_stack.append(char)
    
    # Pop remaining operators
    while operator_stack:
        output.append(operator_stack.pop())
    
    return ' '.join(output)
 
 
# Test cases
print(infix_to_postfix("2 + 3 * 4"))      # 2 3 4 * +
print(infix_to_postfix("(2 + 3) * 4"))    # 2 3 + 4 *
print(infix_to_postfix("a + b * c - d"))  # a b c * + d -
print(infix_to_postfix("(a + b) * (c - d)"))  # a b + c d - *

Trace Through: "2 + 3 * 4"

Shunting-Yard Trace
Token	Action	Operator Stack	Output
2	Output directly	[]	2
	Push (stack empty)	[+]	2
3	Output directly	[+]	2 3
	Push (* > +)	[+, *]	2 3
4	Output directly	[+, *]	2 3 4
END	Pop remaining	[]	2 3 4 * +

Trace Through: "(2 + 3) * 4"

Shunting-Yard with Parentheses
Token	Action	Operator Stack	Output
(	Push	[(]
2	Output directly	[(]	2
	Push	[(, +]	2
3	Output directly	[(, +]	2 3
)	Pop until (	[]	2 3 +
	Push	[*]	2 3 +
4	Output directly	[*]	2 3 + 4
END	Pop remaining	[]	2 3 + 4 *

Parentheses Create Precedence Bubbles

The '(' acts as a barrier on the stack. Operators inside the parentheses can't escape until ')' is seen. This ensures that (2 + 3) is fully computed before * can operate on it.

Why This Works: The Underlying Logic

The brilliance of these algorithms lies in their use of the stack's LIFO property:

In Postfix Evaluation:

When an operator appears, its operands are the most recently pushed values. This is exactly what we want because:

Operators apply to their nearest operands
Inner expressions are evaluated before outer expressions
The stack naturally accumulates partial results

In Infix-to-Postfix Conversion:

The operator stack holds operators that are "waiting" for their right operands. Higher-precedence operators stay on the stack because they'll operate on whatever follows. Lower-precedence operators trigger flushing because theymust wait for the higher-precedence operations to complete.

The Key Invariant:

At any point during conversion, the operator stack is monotonically increasing in precedence from bottom to top. A new operator either:

Maintains this invariant (push if higher precedence)
Restores it (pop lower-precedence operators first)

Connection to Monotonic Stacks

The Shunting-yard algorithm is actually a monotonic stack algorithm! The operator stack maintains increasing precedence. When you see a lower-precedence operator, you pop until the invariant is restored. This connects expression parsing to the broader monotonic stack pattern covered in later modules.

Direct Infix Evaluation with Two Stacks

Instead of converting to postfix first, we can evaluate infix directly using two stacks:

Operand stack — holds numbers/values
Operator stack — holds operators (like in Shunting-yard)

When we would output to postfix, we instead evaluate immediately using values from the operand stack.

The Core Idea:

Combine Shunting-yard with postfix evaluation into one pass:

Numbers push to operand stack
Operators may trigger computation before pushing
At end, compute remaining stack

infix-eval-two-stack.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
def evaluate_infix(expression: str) -> float:
    """
    Evaluate infix expression directly using two stacks.
    
    Combines conversion and evaluation in one pass.
    """
    def apply_operator(operators, values):
        """Pop one operator and two values, compute, push result."""
        op = operators.pop()
        b = values.pop()
        a = values.pop()
        if op == '+': values.append(a + b)
        elif op == '-': values.append(a - b)
        elif op == '*': values.append(a * b)
        elif op == '/': values.append(a / b)
    
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    values = []
    operators = []
    
    i = 0
    while i < len(expression):
        char = expression[i]
        
        if char.isspace():
            i += 1
            continue
        
        if char.isdigit():
            # Parse full number (could be multi-digit)
            j = i
            while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                j += 1
            values.append(float(expression[i:j]))
            i = j
            continue
        
        if char == '(':
            operators.append(char)
        
        elif char == ')':
            # Evaluate until '('
            while operators[-1] != '(':
                apply_operator(operators, values)
            operators.pop()  # Remove '('
        
        elif char in precedence:
            # Evaluate higher/equal precedence operators first
            while (operators and 
                   operators[-1] != '(' and
                   operators[-1] in precedence and
                   precedence[operators[-1]] >= precedence[char]):
                apply_operator(operators, values)
            operators.append(char)
        
        i += 1
    
    # Evaluate remaining operators
    while operators:
        apply_operator(operators, values)
    
    return values[0]
 
 
# Test cases
print(evaluate_infix("2 + 3 * 4"))        # 14.0
print(evaluate_infix("(2 + 3) * 4"))      # 20.0
print(evaluate_infix("10 + 2 * 6"))       # 22.0
print(evaluate_infix("100 * 2 + 12"))     # 212.0
print(evaluate_infix("100 * ( 2 + 12 )")) # 1400.0

One Pass, Same Result

This single-pass approach is more efficient than converting to postfix and then evaluating. It's what most practical expression evaluators use. The logic is identical—we're just computing results instead of building a string.

Real-World Applications

Expression evaluation is everywhere in computing:

Where Expression Evaluation Appears

•Calculators — From simple desk calculators to scientific ones, all use stack-based evaluation
•Compilers & Interpreters — Parsing arithmetic expressions in source code uses these exact algorithms
•Spreadsheets — Excel/Sheets formula evaluation: =A1+B2*C3 uses Shunting-yard internally
•Query Languages — SQL WHERE clauses, MongoDB queries with operators
•Configuration Files — Expression evaluation in config: timeout: $(base_timeout * 2)
•Stack-Based VMs — Java Virtual Machine (JVM), Python bytecode, WebAssembly all use postfix-style execution
•Reverse Polish Calculators — HP calculators that require RPN input are famous among engineers

Expression Evaluation in Different Domains
Domain	Input Format	Evaluation Method
Scientific calculators	Infix (with display)	Shunting-yard + eval
HP RPN calculators	Postfix (native)	Direct stack eval
Forth language	Postfix (stack-based)	Direct interpretation
Lisp/Scheme	Prefix (S-expressions)	Recursive evaluation
Java bytecode	Postfix (operand stack)	JVM stack machine
SQL expressions	Infix	Parse tree evaluation

Extensions and Variations

The basic stack-based expression algorithms extend to handle more complex scenarios:

1. Unary Operators

Unary minus (-5), factorial (5!), logical NOT (!x). These require modified parsing to distinguish from binary operators.

2. Function Calls

sin(45), max(a, b). Functions push onto the operator stack; arguments are parsed recursively; when ) is seen, function is applied.

3. Right-Associative Operators

Exponentiation (2^3^4 = 2^81, not 8^4). Requires > instead of >= in precedence comparison.

4. Ternary Operators

Conditional: a ? b : c. More complex stack management with special handling.

5. Custom Operators

User-defined operators with any precedence. Table-driven Shunting-yard is easily extensible.

extended-operators.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Extended precedence table with right-associativity
OPERATORS = {
    '+': (1, 'L'),   # precedence, associativity
    '-': (1, 'L'),
    '*': (2, 'L'),
    '/': (2, 'L'),
    '^': (3, 'R'),   # Right-associative exponentiation
    '%': (2, 'L'),   # Modulo
}
 
def should_pop(stack_op, new_op):
    """
    Determine if we should pop stack_op before pushing new_op.
    
    For left-associative: pop if stack_op precedence >= new_op
    For right-associative: pop if stack_op precedence > new_op
    """
    if stack_op not in OPERATORS:
        return False
    
    stack_prec, _ = OPERATORS[stack_op]
    new_prec, new_assoc = OPERATORS[new_op]
    
    if new_assoc == 'L':
        return stack_prec >= new_prec
    else:  # Right associative
        return stack_prec > new_prec
 
 
# With this rule:
# 2^3^4 → 2 3 4 ^ ^ (evaluates as 2^(3^4))
# 2-3-4 → 2 3 - 4 - (evaluates as (2-3)-4)

Summary: Expression Evaluation Mastery

Expression evaluation demonstrates stacks at their most elegant. The seemingly complex problem of parsing mathematical expressions with precedence and parentheses reduces to simple stack operations.

Key Takeaways

•Three notations — Infix (human), prefix, postfix (machine-friendly). Same expression, different orderings.
•Postfix is inherently unambiguous — No parentheses or precedence rules needed; order encodes precedence.
•Postfix evaluation is trivial — Push numbers, pop-compute-push on operators. Linear time, single pass.
•Shunting-yard converts infix to postfix — Operator stack maintains precedence; parentheses create barriers.
•Two-stack evaluation combines both — Evaluate on-the-fly instead of outputting postfix first.
•Applications are ubiquitous — Calculators, compilers, VMs, spreadsheets all use these algorithms.

Module Complete!

Congratulations! You've mastered the core stack patterns: reversal, state tracking, function call simulation, and expression evaluation. These patterns appear throughout computer science and form the foundation for understanding compilers, interpreters, and countless algorithms. When you encounter a problem involving reversal, nesting, backtracking, or operator precedence—reach for a stack.

What's Next:

With these fundamental patterns understood, you're ready to explore more advanced stack applications in the next module: Parentheses Matching & Expression Problems—where we'll dive deeper into practical applications of these patterns with challenging coding problems.