Data Structures & AlgorithmsParentheses Matching & Expression Problems

Parentheses Matching & Expression Problems

LevelIntermediate

Duration60 mins

TopicParentheses Matching & Expression Problems

3 / 4

Evaluating Postfix Expressions

The Elegance of Parentheses-Free Notation

Consider the expression 3 + 4 * 2. What's the answer? If you follow standard mathematical conventions, you'd compute 4 * 2 = 8 first (multiplication before addition), then 3 + 8 = 11. But the order of evaluation isn't explicit in the notation—you need to know the rules of operator precedence.

Now consider: 3 4 2 * +. This is the same expression in postfix notation (also called Reverse Polish Notation or RPN). Here, the order of operations is explicit in the structure: when you see an operator, you know exactly which operands it applies to. No parentheses needed. No precedence rules needed.

This seemingly obscure notation is the foundation of:

Stack-based calculators (HP calculators famously used RPN)
Virtual machine bytecode (JVM, Python bytecode, WASM)
Compiler intermediate representations
Expression evaluation in many programming languages

In this page, we'll master the elegant algorithm that evaluates postfix expressions using a stack—and understand why this notation is so powerful.

What You Will Learn

By the end of this page, you will understand what postfix notation is and why it exists, master the stack-based algorithm for evaluating postfix expressions, trace through complex examples step-by-step, handle edge cases correctly, and see how this relates to compiler design and virtual machines.

Understanding Expression Notations

There are three main ways to write mathematical expressions, differing in where the operator appears relative to its operands:

1. Infix Notation (Standard mathematical notation)

Operator appears between operands: 3 + 4
Requires parentheses and precedence rules: 3 + 4 * 2
Human-readable but ambiguous without conventions

2. Prefix Notation (Polish Notation)

Operator appears before operands: + 3 4
No parentheses needed: + 3 * 4 2
Named after Polish logician Jan Łukasiewicz

3. Postfix Notation (Reverse Polish Notation - RPN)

Operator appears after operands: 3 4 +
No parentheses needed: 3 4 2 * +
Most naturally evaluated with a stack

Expression Notation Comparison
Infix (Standard)	Prefix	Postfix	Result
3 + 4	3 4	3 4 +	7
3 + 4 * 2	3 * 4 2	3 4 2 * +	11
(3 + 4) * 2	3 4 2	3 4 + 2 *	14
3 * (4 + 2)	3 + 4 2	3 4 2 + *	18
(1 + 2) * (3 + 4)	1 2 + 3 4	1 2 + 3 4 + *	21

Notice the Pattern

In postfix notation, parentheses disappear! The expression (3 + 4) * 2 becomes 3 4 + 2 *. Reading left to right, we first compute 3 4 + (= 7), then 7 2 * (= 14). The structure encodes the order of operations implicitly.

Why Postfix for Computers?

Computers love postfix for several reasons:

No precedence handling — Operators are applied in the order they appear
No parentheses parsing — Structure is encoded in order, not delimiters
Stack-based evaluation — Simple, efficient, no tree construction needed
Perfect for bytecode — VM instructions often follow postfix conventions

While humans find infix natural (we're taught 3 + 4 from childhood), computers find postfix easier to process. Most compilers convert infix to postfix (or a tree representation) before evaluation.

The Postfix Evaluation Algorithm

The algorithm for evaluating postfix expressions is beautifully simple:

Algorithm: Evaluate Postfix Expression

Initialize an empty stack
Scan the expression from left to right, for each token:
- If the token is an operand (number): push it onto the stack
- If the token is an operator:
  - Pop the required operands from the stack (2 for binary operators)
  - Apply the operator
  - Push the result back onto the stack
After processing all tokens:
- The stack should contain exactly one element: the final result
- If not, the expression was malformed

Key Insight: When we encounter an operator, its operands are the most recently pushed values. This is exactly what a stack provides! The LIFO property ensures we get the right operands in the right order.

Detailed Walkthrough: 3 4 2 * +

Let's trace through the expression that represents 3 + (4 * 2):

Trace of 3 4 2 * +
Token	Action	Stack After	Explanation
3	Push operand	[3]	First operand
4	Push operand	[3, 4]	Second operand
2	Push operand	[3, 4, 2]	Third operand
	Pop 2, 4; push 4*2=8	[3, 8]	Multiply top two
	Pop 8, 3; push 3+8=11	[11]	Add remaining two
END	Return top of stack	11	Final result

Operand Order Matters!

For non-commutative operators (subtraction, division), the order matters. If the stack is [a, b] with b on top, and we see -, we compute a - b, NOT b - a. The first popped value is the second operand, the second popped value is the first operand.

Implementation

Let's implement the postfix evaluation algorithm in multiple languages. We'll handle the basic arithmetic operators: +, -, *, /.

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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from typing import List, Union
 
def evaluate_postfix(expression: str) -> float:
    """
    Evaluate a postfix (RPN) expression.
    
    Tokens are space-separated. Supports: +, -, *, /
    
    Time Complexity: O(n) where n is the number of tokens
    Space Complexity: O(n) for the stack in worst case
    
    Args:
        expression: Space-separated postfix expression
        
    Returns:
        The result of evaluating the expression
        
    Raises:
        ValueError: If the expression is malformed
        ZeroDivisionError: If division by zero occurs
    """
    # Handle empty input
    if not expression or not expression.strip():
        raise ValueError("Empty expression")
    
    tokens = expression.split()
    stack: List[float] = []
    
    # Define supported operators
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,  # Raises ZeroDivisionError if b=0
    }
    
    for token in tokens:
        if token in operators:
            # Operator: pop two operands, compute, push result
            if len(stack) < 2:
                raise ValueError(
                    f"Insufficient operands for operator '{token}'. "
                    f"Stack has {len(stack)} values, need 2."
                )
            
            # IMPORTANT: Pop order matters for non-commutative operators!
            # Second popped value is the first operand
            b = stack.pop()  # Second operand (right of operator in infix)
            a = stack.pop()  # First operand (left of operator in infix)
            
            result = operators[token](a, b)
            stack.append(result)
        else:
            # Operand: try to parse as number and push
            try:
                value = float(token)
                stack.append(value)
            except ValueError:
                raise ValueError(f"Invalid token: '{token}'")
    
    # Final validation
    if len(stack) != 1:
        raise ValueError(
            f"Malformed expression: expected 1 result, got {len(stack)}. "
            f"Remaining stack: {stack}"
        )
    
    return stack[0]
 
 
# Test cases
test_cases = [
    ("3 4 +", 7),                    # Simple addition
    ("3 4 *", 12),                   # Simple multiplication
    ("3 4 2 * +", 11),               # 3 + (4 * 2) = 11
    ("3 4 + 2 *", 14),               # (3 + 4) * 2 = 14
    ("5 1 2 + 4 * + 3 -", 14),       # 5 + ((1 + 2) * 4) - 3 = 14
    ("10 2 /", 5),                   # Division
    ("10 3 -", 7),                   # Subtraction (order matters!)
    ("2 3 4 * +", 14),               # 2 + (3 * 4) = 14
]
 
print("Postfix Expression Evaluation Tests:")
print("-" * 50)
for expr, expected in test_cases:
    result = evaluate_postfix(expr)
    status = "✓" if result == expected else "✗"
    print(f"{status} '{expr}' = {result} (expected {expected})")

Complex Expression Walkthroughs

Let's trace through some more complex expressions to build deeper intuition.

Example 1: 5 1 2 + 4 * + 3 -

This represents the infix expression: 5 + ((1 + 2) * 4) - 3 = 5 + 12 - 3 = 14

Trace of 5 1 2 + 4 * + 3 -
Token	Stack Before	Action	Stack After
5	[]	Push 5	[5]
1	[5]	Push 1	[5, 1]
2	[5, 1]	Push 2	[5, 1, 2]
	[5, 1, 2]	Pop 2,1; push 1+2=3	[5, 3]
4	[5, 3]	Push 4	[5, 3, 4]
	[5, 3, 4]	Pop 4,3; push 3*4=12	[5, 12]
	[5, 12]	Pop 12,5; push 5+12=17	[17]
3	[17]	Push 3	[17, 3]
	[17, 3]	Pop 3,17; push 17-3=14	[14]

Example 2: 2 3 + 4 5 * *

This represents: (2 + 3) * (4 * 5) = 5 * 20 = 100

Trace of 2 3 + 4 5 * *
Token	Stack Before	Action	Stack After
2	[]	Push 2	[2]
3	[2]	Push 3	[2, 3]
	[2, 3]	Pop 3,2; push 2+3=5	[5]
4	[5]	Push 4	[5, 4]
5	[5, 4]	Push 5	[5, 4, 5]
	[5, 4, 5]	Pop 5,4; push 4*5=20	[5, 20]
	[5, 20]	Pop 20,5; push 5*20=100	[100]

Observation: Stack Depth

Notice that the stack depth corresponds to the 'pending' operands waiting for their operator. After an operator consumes two operands and produces one result, the stack depth decreases by 1. The expression is well-formed if we end with exactly 1 value and never go below 1 when trying to pop for an operator.

Edge Cases and Expression Validation

Real implementations must handle various edge cases. Here's how to validate and gracefully handle them:

Common Edge Cases

•Too few operands — 3 + → Error when popping for +
•Too many operands — 3 4 5 + → Stack has 2 values at end
•Division by zero — 5 0 / → Runtime error
•Invalid tokens — 3 abc + → Can't parse 'abc'
•Empty expression — `` → Error, nothing to evaluate
•Single number — 42 → Valid! Result is 42
•Negative numbers — -3 4 + → Must handle negative sign correctly
•Floating point — 3.5 2.1 + → Result is 5.6

postfix_robust.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from typing import List, Optional, Tuple
from enum import Enum
 
class EvalError(Enum):
    EMPTY_EXPRESSION = "Empty expression"
    INSUFFICIENT_OPERANDS = "Insufficient operands for operator"
    TOO_MANY_OPERANDS = "Expression has unused operands"
    INVALID_TOKEN = "Invalid token"
    DIVISION_BY_ZERO = "Division by zero"
 
def evaluate_postfix_safe(
    expression: str
) -> Tuple[Optional[float], Optional[str]]:
    """
    Evaluate postfix expression with comprehensive error handling.
    
    Returns:
        (result, None) on success
        (None, error_message) on failure
    """
    if not expression or not expression.strip():
        return None, EvalError.EMPTY_EXPRESSION.value
    
    tokens = expression.split()
    stack: List[float] = []
    operators = {'+', '-', '*', '/'}
    
    for i, token in enumerate(tokens):
        if token in operators:
            if len(stack) < 2:
                return None, (
                    f"{EvalError.INSUFFICIENT_OPERANDS.value} "
                    f"'{token}' at position {i}"
                )
            
            b = stack.pop()
            a = stack.pop()
            
            if token == '/' and b == 0:
                return None, (
                    f"{EvalError.DIVISION_BY_ZERO.value} at position {i}"
                )
            
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)
        else:
            try:
                # Handle negative numbers like "-3"
                stack.append(float(token))
            except ValueError:
                return None, (
                    f"{EvalError.INVALID_TOKEN.value}: '{token}' "
                    f"at position {i}"
                )
    
    if len(stack) != 1:
        return None, (
            f"{EvalError.TOO_MANY_OPERANDS.value}: "
            f"{len(stack)} values remain in stack"
        )
    
    return stack[0], None
 
 
# Test error handling
error_cases = [
    ("", "Empty"),
    ("3 +", "Insufficient operands"),
    ("3 4 5 +", "Too many operands"),
    ("3 abc +", "Invalid token"),
    ("5 0 /", "Division by zero"),
]
 
print("Error Handling Tests:")
print("-" * 50)
for expr, description in error_cases:
    result, error = evaluate_postfix_safe(expr)
    print(f"'{expr}': {description}")
    print(f"  Result: {result}, Error: {error}")
    print()

Extending to More Operators

The basic algorithm easily extends to support more operators, including:

Unary operators — 3 ~ for negation (pops 1, pushes 1)
Comparison operators — 3 4 > → 0 or 1 (boolean)
Mathematical functions — 3 sqrt, 2 3 pow
Conditional operators — cond then else ? (ternary)

The key modification: operators can have different arities (number of operands). Binary operators pop 2, unary operators pop 1, ternary operators pop 3.

postfix_extended.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import math
from typing import Callable, List
 
def evaluate_extended_postfix(expression: str) -> float:
    """
    Evaluate postfix expression with extended operator set.
    
    Supports:
    - Binary: +, -, *, /, ^, %, max, min
    - Unary: neg (negation), sqrt, sin, cos, log
    - Constants: pi, e
    """
    tokens = expression.split()
    stack: List[float] = []
    
    # Binary operators (pop 2, push 1)
    binary_ops: dict[str, Callable[[float, float], float]] = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
        '^': lambda a, b: a ** b,
        '%': lambda a, b: a % b,
        'max': lambda a, b: max(a, b),
        'min': lambda a, b: min(a, b),
    }
    
    # Unary operators (pop 1, push 1)
    unary_ops: dict[str, Callable[[float], float]] = {
        'neg': lambda x: -x,
        'sqrt': lambda x: math.sqrt(x),
        'sin': lambda x: math.sin(x),
        'cos': lambda x: math.cos(x),
        'log': lambda x: math.log(x),
        'abs': lambda x: abs(x),
        'floor': lambda x: math.floor(x),
        'ceil': lambda x: math.ceil(x),
    }
    
    # Constants
    constants: dict[str, float] = {
        'pi': math.pi,
        'e': math.e,
    }
    
    for token in tokens:
        if token in binary_ops:
            if len(stack) < 2:
                raise ValueError(f"Need 2 operands for {token}")
            b, a = stack.pop(), stack.pop()
            stack.append(binary_ops[token](a, b))
            
        elif token in unary_ops:
            if len(stack) < 1:
                raise ValueError(f"Need 1 operand for {token}")
            x = stack.pop()
            stack.append(unary_ops[token](x))
            
        elif token in constants:
            stack.append(constants[token])
            
        else:
            try:
                stack.append(float(token))
            except ValueError:
                raise ValueError(f"Unknown token: {token}")
    
    if len(stack) != 1:
        raise ValueError(f"Malformed: {len(stack)} values remain")
    
    return stack[0]
 
 
# Examples with extended operators
examples = [
    ("2 3 ^", 8),           # 2^3 = 8
    ("16 sqrt", 4),         # √16 = 4
    ("3 4 max", 4),         # max(3,4) = 4
    ("5 neg", -5),          # -5
    ("pi 2 /", math.pi/2),  # π/2
    ("e 1 log", 1),         # ln(e) = 1
    ("2 3 4 + *", 14),      # 2 * (3+4) = 14
]
 
print("Extended Postfix Evaluation:")
for expr, expected in examples:
    result = evaluate_extended_postfix(expr)
    print(f"'{expr}' = {result:.4f} (expected {expected:.4f})")

Real-World Application: Stack Machines

The postfix evaluation algorithm isn't just a theoretical exercise—it's the foundation of stack-based virtual machines that power modern software:

Java Virtual Machine (JVM)

Java bytecode uses a stack-based evaluation model. When you write:

int x = 3 + 4 * 2;

The compiler generates bytecode roughly equivalent to:

iconst_3        // Push 3
iconst_4        // Push 4
iconst_2        // Push 2
imul            // Pop 4,2; push 4*2=8
iadd            // Pop 3,8; push 3+8=11
istore_1        // Pop 11, store in local variable 1

This is postfix evaluation in action!

Stack-Based Systems in Production

•JVM (Java Virtual Machine) — Java, Kotlin, Scala, and all JVM languages compile to stack-based bytecode
•CPython Bytecode — Python's default interpreter uses stack-based bytecode for expression evaluation
•WebAssembly (WASM) — The web's low-level compilation target is a stack machine
•PostScript — Adobe's page description language is stack-based (hence 'Post' from postfix)
•Forth — A programming language where everything is stack-based
•.NET CLR — Microsoft's Common Language Runtime for C#, F#, VB.NET
•HP Calculators — The legendary HP-35 and successors used RPN

Why Stack Machines?

Stack machines have elegant properties:

Simplicity — No register allocation needed; operands are implicit
Compactness — Instructions are short (no register operands)
Portability — Abstract machine, not tied to physical architecture
Verifiability — Stack depth is predictable; type safety is checkable

The trade-off is that real hardware uses registers, so stack machine bytecode must be translated to register-based native code (by the JIT compiler) for peak performance.

From Theory to Industry

When you learn postfix evaluation, you're learning the computational model behind billions of devices. Every Android phone evaluates Dalvik/ART bytecode. Every web browser runs WASM. Every JVM application uses this principle. This 'simple' algorithm scales from classroom exercise to planet-scale infrastructure.

Complexity Analysis

Time Complexity: O(n)

Where n is the number of tokens in the expression:

Each token is processed exactly once: O(1) per token
Each push operation: O(1)
Each pop operation: O(1)
Each arithmetic operation: O(1)

Total: O(n) time.

Space Complexity: O(n)

In the worst case, the expression could be all operands followed by operators: 1 2 3 4 5 + + + + (= 1 + 2 + 3 + 4 + 5 = 15)

Here, the stack grows to hold all operands before any operator is applied.

Practical Considerations:

Space Usage Patterns
Expression Type	Max Stack Size	Example
All operands then operators	n/2 + 1	1 2 3 4 + + +
Interleaved evenly	2	1 2 + 3 + 4 +
Deeply nested	(n/2)	(((a op b) op c) op d)
Single operand	1	42

Is O(n) optimal?

Yes! Any algorithm must read all tokens at least once, so Ω(n) is a lower bound. Our algorithm matches this lower bound.

Note on tokenization:

Our analysis assumes tokens are pre-split. If parsing a raw string with multi-digit numbers, tokenization adds O(n) work (scanning the input), which doesn't change the overall O(n) complexity.

Summary: Stack-Powered Expression Evaluation

Key Takeaways

•Postfix notation eliminates ambiguity — No parentheses or precedence rules needed; the order of operations is encoded in token order.
•The evaluation algorithm is elegant — Push operands; when you see an operator, pop operands, compute, push result.
•Order matters for non-commutative operators — The second popped value is the first operand (left side of operator).
•Stack machines power the software industry — JVM, Python bytecode, and WASM all use this principle.
•O(n) time, O(n) space — Linear in the number of tokens, optimal for any evaluation approach.
•Extensible to any operators — Easily add unary, ternary, or custom operators by adjusting the arity.

What's Next:

We've learned to evaluate postfix expressions. But how do we create them? In the next page, we'll master the Shunting-Yard Algorithm—the elegant method for converting familiar infix expressions into postfix form, bridging human-readable notation and computer-friendly representation.

Page Complete

You now understand postfix expression evaluation—a fundamental algorithm that powers virtual machines, calculators, and compilers worldwide. The simplicity of the stack-based approach masks its profound importance in computing infrastructure.

3 / 4

Loading learning content...

Data Structures & AlgorithmsParentheses Matching & Expression Problems

Parentheses Matching & Expression Problems

LevelIntermediate

Duration60 mins

TopicParentheses Matching & Expression Problems

3 / 4

Evaluating Postfix Expressions

The Elegance of Parentheses-Free Notation

This seemingly obscure notation is the foundation of:

Stack-based calculators (HP calculators famously used RPN)
Virtual machine bytecode (JVM, Python bytecode, WASM)
Compiler intermediate representations
Expression evaluation in many programming languages

In this page, we'll master the elegant algorithm that evaluates postfix expressions using a stack—and understand why this notation is so powerful.

What You Will Learn

Understanding Expression Notations

There are three main ways to write mathematical expressions, differing in where the operator appears relative to its operands:

1. Infix Notation (Standard mathematical notation)

Operator appears between operands: 3 + 4
Requires parentheses and precedence rules: 3 + 4 * 2
Human-readable but ambiguous without conventions

2. Prefix Notation (Polish Notation)

Operator appears before operands: + 3 4
No parentheses needed: + 3 * 4 2
Named after Polish logician Jan Łukasiewicz

3. Postfix Notation (Reverse Polish Notation - RPN)

Operator appears after operands: 3 4 +
No parentheses needed: 3 4 2 * +
Most naturally evaluated with a stack

Expression Notation Comparison
Infix (Standard)	Prefix	Postfix	Result
3 + 4	3 4	3 4 +	7
3 + 4 * 2	3 * 4 2	3 4 2 * +	11
(3 + 4) * 2	3 4 2	3 4 + 2 *	14
3 * (4 + 2)	3 + 4 2	3 4 2 + *	18
(1 + 2) * (3 + 4)	1 2 + 3 4	1 2 + 3 4 + *	21

Notice the Pattern

Why Postfix for Computers?

Computers love postfix for several reasons:

No precedence handling — Operators are applied in the order they appear
No parentheses parsing — Structure is encoded in order, not delimiters
Stack-based evaluation — Simple, efficient, no tree construction needed
Perfect for bytecode — VM instructions often follow postfix conventions

While humans find infix natural (we're taught 3 + 4 from childhood), computers find postfix easier to process. Most compilers convert infix to postfix (or a tree representation) before evaluation.

The Postfix Evaluation Algorithm

The algorithm for evaluating postfix expressions is beautifully simple:

Algorithm: Evaluate Postfix Expression

Initialize an empty stack
Scan the expression from left to right, for each token:
- If the token is an operand (number): push it onto the stack
- If the token is an operator:
  - Pop the required operands from the stack (2 for binary operators)
  - Apply the operator
  - Push the result back onto the stack
After processing all tokens:
- The stack should contain exactly one element: the final result
- If not, the expression was malformed

Detailed Walkthrough: 3 4 2 * +

Let's trace through the expression that represents 3 + (4 * 2):

Trace of 3 4 2 * +
Token	Action	Stack After	Explanation
3	Push operand	[3]	First operand
4	Push operand	[3, 4]	Second operand
2	Push operand	[3, 4, 2]	Third operand
	Pop 2, 4; push 4*2=8	[3, 8]	Multiply top two
	Pop 8, 3; push 3+8=11	[11]	Add remaining two
END	Return top of stack	11	Final result

Operand Order Matters!

Implementation

Let's implement the postfix evaluation algorithm in multiple languages. We'll handle the basic arithmetic operators: +, -, *, /.

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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from typing import List, Union
 
def evaluate_postfix(expression: str) -> float:
    """
    Evaluate a postfix (RPN) expression.
    
    Tokens are space-separated. Supports: +, -, *, /
    
    Time Complexity: O(n) where n is the number of tokens
    Space Complexity: O(n) for the stack in worst case
    
    Args:
        expression: Space-separated postfix expression
        
    Returns:
        The result of evaluating the expression
        
    Raises:
        ValueError: If the expression is malformed
        ZeroDivisionError: If division by zero occurs
    """
    # Handle empty input
    if not expression or not expression.strip():
        raise ValueError("Empty expression")
    
    tokens = expression.split()
    stack: List[float] = []
    
    # Define supported operators
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,  # Raises ZeroDivisionError if b=0
    }
    
    for token in tokens:
        if token in operators:
            # Operator: pop two operands, compute, push result
            if len(stack) < 2:
                raise ValueError(
                    f"Insufficient operands for operator '{token}'. "
                    f"Stack has {len(stack)} values, need 2."
                )
            
            # IMPORTANT: Pop order matters for non-commutative operators!
            # Second popped value is the first operand
            b = stack.pop()  # Second operand (right of operator in infix)
            a = stack.pop()  # First operand (left of operator in infix)
            
            result = operators[token](a, b)
            stack.append(result)
        else:
            # Operand: try to parse as number and push
            try:
                value = float(token)
                stack.append(value)
            except ValueError:
                raise ValueError(f"Invalid token: '{token}'")
    
    # Final validation
    if len(stack) != 1:
        raise ValueError(
            f"Malformed expression: expected 1 result, got {len(stack)}. "
            f"Remaining stack: {stack}"
        )
    
    return stack[0]
 
 
# Test cases
test_cases = [
    ("3 4 +", 7),                    # Simple addition
    ("3 4 *", 12),                   # Simple multiplication
    ("3 4 2 * +", 11),               # 3 + (4 * 2) = 11
    ("3 4 + 2 *", 14),               # (3 + 4) * 2 = 14
    ("5 1 2 + 4 * + 3 -", 14),       # 5 + ((1 + 2) * 4) - 3 = 14
    ("10 2 /", 5),                   # Division
    ("10 3 -", 7),                   # Subtraction (order matters!)
    ("2 3 4 * +", 14),               # 2 + (3 * 4) = 14
]
 
print("Postfix Expression Evaluation Tests:")
print("-" * 50)
for expr, expected in test_cases:
    result = evaluate_postfix(expr)
    status = "✓" if result == expected else "✗"
    print(f"{status} '{expr}' = {result} (expected {expected})")

Complex Expression Walkthroughs

Let's trace through some more complex expressions to build deeper intuition.

Example 1: 5 1 2 + 4 * + 3 -

This represents the infix expression: 5 + ((1 + 2) * 4) - 3 = 5 + 12 - 3 = 14

Trace of 5 1 2 + 4 * + 3 -
Token	Stack Before	Action	Stack After
5	[]	Push 5	[5]
1	[5]	Push 1	[5, 1]
2	[5, 1]	Push 2	[5, 1, 2]
	[5, 1, 2]	Pop 2,1; push 1+2=3	[5, 3]
4	[5, 3]	Push 4	[5, 3, 4]
	[5, 3, 4]	Pop 4,3; push 3*4=12	[5, 12]
	[5, 12]	Pop 12,5; push 5+12=17	[17]
3	[17]	Push 3	[17, 3]
	[17, 3]	Pop 3,17; push 17-3=14	[14]

Example 2: 2 3 + 4 5 * *

This represents: (2 + 3) * (4 * 5) = 5 * 20 = 100

Trace of 2 3 + 4 5 * *
Token	Stack Before	Action	Stack After
2	[]	Push 2	[2]
3	[2]	Push 3	[2, 3]
	[2, 3]	Pop 3,2; push 2+3=5	[5]
4	[5]	Push 4	[5, 4]
5	[5, 4]	Push 5	[5, 4, 5]
	[5, 4, 5]	Pop 5,4; push 4*5=20	[5, 20]
	[5, 20]	Pop 20,5; push 5*20=100	[100]

Observation: Stack Depth

Edge Cases and Expression Validation

Real implementations must handle various edge cases. Here's how to validate and gracefully handle them:

Common Edge Cases

•Too few operands — 3 + → Error when popping for +
•Too many operands — 3 4 5 + → Stack has 2 values at end
•Division by zero — 5 0 / → Runtime error
•Invalid tokens — 3 abc + → Can't parse 'abc'
•Empty expression — `` → Error, nothing to evaluate
•Single number — 42 → Valid! Result is 42
•Negative numbers — -3 4 + → Must handle negative sign correctly
•Floating point — 3.5 2.1 + → Result is 5.6

postfix_robust.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from typing import List, Optional, Tuple
from enum import Enum
 
class EvalError(Enum):
    EMPTY_EXPRESSION = "Empty expression"
    INSUFFICIENT_OPERANDS = "Insufficient operands for operator"
    TOO_MANY_OPERANDS = "Expression has unused operands"
    INVALID_TOKEN = "Invalid token"
    DIVISION_BY_ZERO = "Division by zero"
 
def evaluate_postfix_safe(
    expression: str
) -> Tuple[Optional[float], Optional[str]]:
    """
    Evaluate postfix expression with comprehensive error handling.
    
    Returns:
        (result, None) on success
        (None, error_message) on failure
    """
    if not expression or not expression.strip():
        return None, EvalError.EMPTY_EXPRESSION.value
    
    tokens = expression.split()
    stack: List[float] = []
    operators = {'+', '-', '*', '/'}
    
    for i, token in enumerate(tokens):
        if token in operators:
            if len(stack) < 2:
                return None, (
                    f"{EvalError.INSUFFICIENT_OPERANDS.value} "
                    f"'{token}' at position {i}"
                )
            
            b = stack.pop()
            a = stack.pop()
            
            if token == '/' and b == 0:
                return None, (
                    f"{EvalError.DIVISION_BY_ZERO.value} at position {i}"
                )
            
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)
        else:
            try:
                # Handle negative numbers like "-3"
                stack.append(float(token))
            except ValueError:
                return None, (
                    f"{EvalError.INVALID_TOKEN.value}: '{token}' "
                    f"at position {i}"
                )
    
    if len(stack) != 1:
        return None, (
            f"{EvalError.TOO_MANY_OPERANDS.value}: "
            f"{len(stack)} values remain in stack"
        )
    
    return stack[0], None
 
 
# Test error handling
error_cases = [
    ("", "Empty"),
    ("3 +", "Insufficient operands"),
    ("3 4 5 +", "Too many operands"),
    ("3 abc +", "Invalid token"),
    ("5 0 /", "Division by zero"),
]
 
print("Error Handling Tests:")
print("-" * 50)
for expr, description in error_cases:
    result, error = evaluate_postfix_safe(expr)
    print(f"'{expr}': {description}")
    print(f"  Result: {result}, Error: {error}")
    print()

Extending to More Operators

The basic algorithm easily extends to support more operators, including:

Unary operators — 3 ~ for negation (pops 1, pushes 1)
Comparison operators — 3 4 > → 0 or 1 (boolean)
Mathematical functions — 3 sqrt, 2 3 pow
Conditional operators — cond then else ? (ternary)

The key modification: operators can have different arities (number of operands). Binary operators pop 2, unary operators pop 1, ternary operators pop 3.

postfix_extended.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import math
from typing import Callable, List
 
def evaluate_extended_postfix(expression: str) -> float:
    """
    Evaluate postfix expression with extended operator set.
    
    Supports:
    - Binary: +, -, *, /, ^, %, max, min
    - Unary: neg (negation), sqrt, sin, cos, log
    - Constants: pi, e
    """
    tokens = expression.split()
    stack: List[float] = []
    
    # Binary operators (pop 2, push 1)
    binary_ops: dict[str, Callable[[float, float], float]] = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b,
        '^': lambda a, b: a ** b,
        '%': lambda a, b: a % b,
        'max': lambda a, b: max(a, b),
        'min': lambda a, b: min(a, b),
    }
    
    # Unary operators (pop 1, push 1)
    unary_ops: dict[str, Callable[[float], float]] = {
        'neg': lambda x: -x,
        'sqrt': lambda x: math.sqrt(x),
        'sin': lambda x: math.sin(x),
        'cos': lambda x: math.cos(x),
        'log': lambda x: math.log(x),
        'abs': lambda x: abs(x),
        'floor': lambda x: math.floor(x),
        'ceil': lambda x: math.ceil(x),
    }
    
    # Constants
    constants: dict[str, float] = {
        'pi': math.pi,
        'e': math.e,
    }
    
    for token in tokens:
        if token in binary_ops:
            if len(stack) < 2:
                raise ValueError(f"Need 2 operands for {token}")
            b, a = stack.pop(), stack.pop()
            stack.append(binary_ops[token](a, b))
            
        elif token in unary_ops:
            if len(stack) < 1:
                raise ValueError(f"Need 1 operand for {token}")
            x = stack.pop()
            stack.append(unary_ops[token](x))
            
        elif token in constants:
            stack.append(constants[token])
            
        else:
            try:
                stack.append(float(token))
            except ValueError:
                raise ValueError(f"Unknown token: {token}")
    
    if len(stack) != 1:
        raise ValueError(f"Malformed: {len(stack)} values remain")
    
    return stack[0]
 
 
# Examples with extended operators
examples = [
    ("2 3 ^", 8),           # 2^3 = 8
    ("16 sqrt", 4),         # √16 = 4
    ("3 4 max", 4),         # max(3,4) = 4
    ("5 neg", -5),          # -5
    ("pi 2 /", math.pi/2),  # π/2
    ("e 1 log", 1),         # ln(e) = 1
    ("2 3 4 + *", 14),      # 2 * (3+4) = 14
]
 
print("Extended Postfix Evaluation:")
for expr, expected in examples:
    result = evaluate_extended_postfix(expr)
    print(f"'{expr}' = {result:.4f} (expected {expected:.4f})")

Real-World Application: Stack Machines

The postfix evaluation algorithm isn't just a theoretical exercise—it's the foundation of stack-based virtual machines that power modern software:

Java Virtual Machine (JVM)

Java bytecode uses a stack-based evaluation model. When you write:

int x = 3 + 4 * 2;

The compiler generates bytecode roughly equivalent to:

iconst_3        // Push 3
iconst_4        // Push 4
iconst_2        // Push 2
imul            // Pop 4,2; push 4*2=8
iadd            // Pop 3,8; push 3+8=11
istore_1        // Pop 11, store in local variable 1

This is postfix evaluation in action!

Stack-Based Systems in Production

•JVM (Java Virtual Machine) — Java, Kotlin, Scala, and all JVM languages compile to stack-based bytecode
•CPython Bytecode — Python's default interpreter uses stack-based bytecode for expression evaluation
•WebAssembly (WASM) — The web's low-level compilation target is a stack machine
•PostScript — Adobe's page description language is stack-based (hence 'Post' from postfix)
•Forth — A programming language where everything is stack-based
•.NET CLR — Microsoft's Common Language Runtime for C#, F#, VB.NET
•HP Calculators — The legendary HP-35 and successors used RPN

Why Stack Machines?

Stack machines have elegant properties:

Simplicity — No register allocation needed; operands are implicit
Compactness — Instructions are short (no register operands)
Portability — Abstract machine, not tied to physical architecture
Verifiability — Stack depth is predictable; type safety is checkable

The trade-off is that real hardware uses registers, so stack machine bytecode must be translated to register-based native code (by the JIT compiler) for peak performance.

From Theory to Industry

Complexity Analysis

Time Complexity: O(n)

Where n is the number of tokens in the expression:

Each token is processed exactly once: O(1) per token
Each push operation: O(1)
Each pop operation: O(1)
Each arithmetic operation: O(1)

Total: O(n) time.

Space Complexity: O(n)

In the worst case, the expression could be all operands followed by operators: 1 2 3 4 5 + + + + (= 1 + 2 + 3 + 4 + 5 = 15)

Here, the stack grows to hold all operands before any operator is applied.

Practical Considerations:

Space Usage Patterns
Expression Type	Max Stack Size	Example
All operands then operators	n/2 + 1	1 2 3 4 + + +
Interleaved evenly	2	1 2 + 3 + 4 +
Deeply nested	(n/2)	(((a op b) op c) op d)
Single operand	1	42

Is O(n) optimal?

Yes! Any algorithm must read all tokens at least once, so Ω(n) is a lower bound. Our algorithm matches this lower bound.

Note on tokenization:

Our analysis assumes tokens are pre-split. If parsing a raw string with multi-digit numbers, tokenization adds O(n) work (scanning the input), which doesn't change the overall O(n) complexity.

Summary: Stack-Powered Expression Evaluation

Key Takeaways

•Postfix notation eliminates ambiguity — No parentheses or precedence rules needed; the order of operations is encoded in token order.
•The evaluation algorithm is elegant — Push operands; when you see an operator, pop operands, compute, push result.
•Order matters for non-commutative operators — The second popped value is the first operand (left side of operator).
•Stack machines power the software industry — JVM, Python bytecode, and WASM all use this principle.
•O(n) time, O(n) space — Linear in the number of tokens, optimal for any evaluation approach.
•Extensible to any operators — Easily add unary, ternary, or custom operators by adjusting the arity.

What's Next:

Page Complete

3 / 4