Stack Expression Evaluation: Infix, Postfix & Calculator

Every calculator and compiler needs to evaluate mathematical expressions. The challenge is that the notation we write (infix) has complicated precedence rules and parentheses. Stacks solve this elegantly by converting to a simpler notation first.

Three Notations

The same expression can be written three ways:

Notation	Example	Operator Position
Infix	3 + 4 * 2	Between operands
Prefix (Polish)	+ 3 * 4 2	Before operands
Postfix (Reverse Polish)	3 4 2 * +	After operands

Why postfix?

Postfix notation has two critical advantages:

1. No parentheses needed — the order of operations is unambiguous
2. Trivial to evaluate with a stack — scan left to right, push numbers, apply operators

Compilers convert infix to postfix (or directly to machine code using similar logic) because machines process instructions sequentially.

Evaluating Postfix Expressions

Before learning conversion, let’s see how easy postfix evaluation is:

def evaluate_postfix(expression):
    """
    Evaluate a postfix expression.
    Time: O(n), Space: O(n)

    expression: list of tokens (numbers as strings, operators as strings)
    """
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in expression:
        if token not in operators:
            stack.append(float(token))
        else:
            # Pop two operands (right first, then left)
            right = stack.pop()
            left = stack.pop()

            if token == '+':
                stack.append(left + right)
            elif token == '-':
                stack.append(left - right)
            elif token == '*':
                stack.append(left * right)
            elif token == '/':
                stack.append(left / right)

    return stack[0]  # Final result


# Test
print(evaluate_postfix(['3', '4', '2', '*', '1', '5', '-', '/', '+']))
# 3 + (4*2) / (1-5) = 3 + 8/(-4) = 3 + (-2) = 1.0

Trace

Token | Stack        | Action
------|--------------|-------
3     | [3]          | Push number
4     | [3, 4]       | Push number
2     | [3, 4, 2]    | Push number
*     | [3, 8]       | Pop 2, 4 → 4*2=8, push
1     | [3, 8, 1]    | Push number
5     | [3, 8, 1, 5] | Push number
-     | [3, 8, -4]   | Pop 5, 1 → 1-5=-4, push
/     | [3, -2]      | Pop -4, 8 → 8/(-4)=-2, push
+     | [1]          | Pop -2, 3 → 3+(-2)=1, push

The Shunting Yard Algorithm

Dijkstra’s Shunting Yard algorithm converts infix to postfix. It uses an operator stack and an output queue.

Precedence and associativity

PRECEDENCE = {
    '+': 1, '-': 1,
    '*': 2, '/': 2,
    '^': 3,  # Exponentiation (right-associative)
}

RIGHT_ASSOCIATIVE = {'^'}

def has_higher_precedence(op1, op2):
    """Check if op1 should be applied before op2."""
    if op1 not in PRECEDENCE or op2 not in PRECEDENCE:
        return False
    if op1 in RIGHT_ASSOCIATIVE:
        return PRECEDENCE[op1] > PRECEDENCE[op2]
    return PRECEDENCE[op1] >= PRECEDENCE[op2]

The algorithm

def infix_to_postfix(tokens):
    """
    Convert infix expression to postfix using the Shunting Yard algorithm.
    Time: O(n), Space: O(n)

    tokens: list of strings — numbers, operators, parentheses
    """
    output = []
    operator_stack = []
    operators = set(PRECEDENCE.keys())

    for token in tokens:
        if token not in operators and token not in ('(', ')'):
            # It's a number — send to output
            output.append(token)

        elif token in operators:
            # Pop operators with higher/equal precedence
            while (operator_stack and
                   operator_stack[-1] != '(' and
                   operator_stack[-1] in operators and
                   has_higher_precedence(operator_stack[-1], token)):
                output.append(operator_stack.pop())
            operator_stack.append(token)

        elif token == '(':
            operator_stack.append(token)

        elif token == ')':
            # Pop until we find the matching (
            while operator_stack and operator_stack[-1] != '(':
                output.append(operator_stack.pop())
            if operator_stack:
                operator_stack.pop()  # Remove the (

    # Pop remaining operators
    while operator_stack:
        output.append(operator_stack.pop())

    return output


# Test
tokens = ['3', '+', '4', '*', '2', '/', '(', '1', '-', '5', ')']
postfix = infix_to_postfix(tokens)
print(' '.join(postfix))  # 3 4 2 * 1 5 - / +

Shunting Yard rules summary

1. Number: send directly to output
2. Operator: pop operators with higher/equal precedence to output, then push
3. Left parenthesis (: push onto stack
4. Right parenthesis ): pop and output until ( is found, then discard (
5. End: pop all remaining operators to output

Building a Complete Calculator

Let’s combine tokenization, conversion, and evaluation:

import re

def tokenize(expression):
    """
    Convert an expression string into tokens.
    Handles multi-digit numbers, decimals, and negative numbers.
    """
    tokens = []
    i = 0
    expr = expression.replace(' ', '')

    while i < len(expr):
        char = expr[i]

        # Handle negative numbers at start or after operator/(
        if char == '-' and (i == 0 or expr[i-1] in '(+-*/^'):
            # Negative number
            j = i + 1
            while j < len(expr) and (expr[j].isdigit() or expr[j] == '.'):
                j += 1
            tokens.append(expr[i:j])
            i = j
        elif char.isdigit() or char == '.':
            j = i
            while j < len(expr) and (expr[j].isdigit() or expr[j] == '.'):
                j += 1
            tokens.append(expr[i:j])
            i = j
        elif char in '+-*/^()':
            tokens.append(char)
            i += 1
        else:
            i += 1  # Skip unknown characters

    return tokens


def calculate(expression):
    """
    Evaluate an infix expression string.
    Supports: +, -, *, /, ^, parentheses, negative numbers, decimals.
    """
    tokens = tokenize(expression)
    postfix = infix_to_postfix(tokens)
    return evaluate_postfix(postfix)


# Test the calculator
print(calculate("3 + 4 * 2 / (1 - 5)"))          # 1.0
print(calculate("(2 + 3) * (4 - 1)"))             # 15.0
print(calculate("2 ^ 3 ^ 2"))                      # 512.0 (right-assoc)
print(calculate("10 + 20 * 30"))                    # 610.0
print(calculate("-5 + 3"))                          # -2.0
print(calculate("((1 + 2) * (3 + 4)) / 7"))        # 3.0

Evaluating Prefix Expressions

Prefix evaluation scans right to left (or uses a stack reading backwards):

def evaluate_prefix(expression):
    """
    Evaluate a prefix expression.
    Time: O(n), Space: O(n)
    """
    stack = []
    operators = {'+', '-', '*', '/'}

    # Process tokens from right to left
    for token in reversed(expression):
        if token not in operators:
            stack.append(float(token))
        else:
            # Pop two operands (left first, then right — reversed)
            left = stack.pop()
            right = stack.pop()

            if token == '+':
                stack.append(left + right)
            elif token == '-':
                stack.append(left - right)
            elif token == '*':
                stack.append(left * right)
            elif token == '/':
                stack.append(left / right)

    return stack[0]


# Test: + 3 * 4 2 = 3 + 4*2 = 11
print(evaluate_prefix(['+', '3', '*', '4', '2']))  # 11.0

Direct Infix Evaluation (Without Conversion)

You can evaluate infix directly using two stacks — one for numbers, one for operators:

def evaluate_infix_direct(expression):
    """
    Evaluate infix expression directly with two stacks.
    Time: O(n), Space: O(n)
    """
    tokens = tokenize(expression)
    values = []
    ops = []

    def apply_op():
        right = values.pop()
        left = values.pop()
        op = ops.pop()
        if op == '+': values.append(left + right)
        elif op == '-': values.append(left - right)
        elif op == '*': values.append(left * right)
        elif op == '/': values.append(left / right)

    operators = set(PRECEDENCE.keys())

    for token in tokens:
        if token not in operators and token not in ('(', ')'):
            values.append(float(token))
        elif token == '(':
            ops.append(token)
        elif token == ')':
            while ops and ops[-1] != '(':
                apply_op()
            ops.pop()  # Remove (
        elif token in operators:
            while (ops and ops[-1] != '(' and
                   ops[-1] in operators and
                   has_higher_precedence(ops[-1], token)):
                apply_op()
            ops.append(token)

    while ops:
        apply_op()

    return values[0]


print(evaluate_infix_direct("3 + 4 * 2 / (1 - 5)"))  # 1.0

Handling Edge Cases

Division by zero

def safe_evaluate_postfix(expression):
    """Postfix evaluation with error handling."""
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in expression:
        if token not in operators:
            stack.append(float(token))
        else:
            if len(stack) < 2:
                raise ValueError(f"Not enough operands for '{token}'")

            right = stack.pop()
            left = stack.pop()

            if token == '/' and right == 0:
                raise ZeroDivisionError("Division by zero")

            if token == '+': stack.append(left + right)
            elif token == '-': stack.append(left - right)
            elif token == '*': stack.append(left * right)
            elif token == '/': stack.append(left / right)

    if len(stack) != 1:
        raise ValueError("Invalid expression")

    return stack[0]

Unmatched parentheses

def validate_parentheses(tokens):
    """Check that parentheses are balanced before evaluation."""
    count = 0
    for token in tokens:
        if token == '(':
            count += 1
        elif token == ')':
            count -= 1
        if count < 0:
            return False
    return count == 0

Complexity Analysis

Operation	Time	Space
Tokenize	O(n)	O(n)
Infix to postfix	O(n)	O(n)
Evaluate postfix	O(n)	O(n)
Full calculate	O(n)	O(n)

Each token is processed exactly once. The stack holds at most O(n) elements.

Practice Problems

1. LeetCode 150 — Evaluate Reverse Polish Notation: Basic postfix evaluation (Medium)
2. LeetCode 224 — Basic Calculator: Infix with +, -, parentheses (Hard)
3. LeetCode 227 — Basic Calculator II: +, -, *, / without parentheses (Medium)
4. LeetCode 772 — Basic Calculator III: Full calculator with nested parentheses (Hard)
5. LeetCode 1006 — Clumsy Factorial: Postfix-style evaluation (Medium)

Key Takeaways

• Postfix notation eliminates the need for parentheses and precedence rules — making it trivial to evaluate with a single stack.
• The Shunting Yard algorithm converts infix to postfix in O(n) using an operator stack.
• Right-associative operators (like ^) need special handling — they don’t pop equal-precedence operators.
• A complete calculator combines tokenization, Shunting Yard, and postfix evaluation — each step is O(n).
• Always validate parentheses and handle division by zero before evaluation.