Expression Evaluation (Stacks & Queues)

Reading 3 + 2 * (1 + 5) left to right and computing as you go gives the wrong answer, and every human knows why: the multiplication binds tighter than the addition, and the parentheses override both. We learned those rules so young they feel like instinct. Teaching a machine to respect them is the heart of this pattern, and the tool that makes it clean is the humble stack. An expression has structure that is not linear, precedence and nesting, and a stack is exactly the device for remembering "hold this thought, I have to deal with something more urgent first, then come back."

The insight is that you keep two stacks: one for numbers and one for operators, and you let precedence decide when an operator is finally allowed to run. When a new operator arrives, any operator already waiting that binds at least as tightly should fire first, so you pop and apply it before pushing the newcomer. A parenthesis is the same idea taken to the extreme: an opening paren is a wall that says "everything inside me resolves before anything outside," and a closing paren tells you to drain operators back to that wall. It is the exact mental process you use by hand, made mechanical.

Two stacks and a precedence rule

Walk the tokens once. Numbers go on the number stack. Operators wait on the operator stack, but before one joins, any higher-or-equal precedence operator already there gets applied. Parentheses gate their contents.

def evaluate(expr):
    def apply(op, b, a):                                  # note: b popped first, so a op b
        return {'+': a + b, '-': a - b, '*': a * b, '/': a // b}[op]
    prec = {'+': 1, '-': 1, '*': 2, '/': 2}
    nums, ops, i = [], [], 0
    while i < len(expr):
        ch = expr[i]
        if ch.isdigit():
            val = 0
            while i < len(expr) and expr[i].isdigit():   # multi-digit numbers
                val = val * 10 + int(expr[i]); i += 1
            nums.append(val); continue
        if ch in prec:
            while ops and ops[-1] in prec and prec[ops[-1]] >= prec[ch]:
                nums.append(apply(ops.pop(), nums.pop(), nums.pop()))   # fire waiting op first
            ops.append(ch)
        elif ch == '(':
            ops.append(ch)
        elif ch == ')':
            while ops[-1] != '(':                        # drain back to the wall
                nums.append(apply(ops.pop(), nums.pop(), nums.pop()))
            ops.pop()                                     # discard the '('
        i += 1
    while ops:                                            # apply whatever is left
        nums.append(apply(ops.pop(), nums.pop(), nums.pop()))
    return nums[0]

print(evaluate("3 + 2 * (1 + 5)"))                        # 15

Trace the hard part: at the *, the waiting + has lower precedence, so + stays put and * is pushed on top, which is exactly what guarantees the multiplication happens before the addition. Inside the parentheses, 1 + 5 resolves against the ( wall before the outer * ever sees its second operand. One linear pass, O(n), correct precedence, and no recursion. The order of the two nums.pop() calls matters for - and /, since the second operand comes off the stack first.

The expression 3 + 2 * (1 + 5) drawn as a tree; the parentheses and the higher precedence of multiplication push 1 + 5 and the multiply deeper, so they evaluate first: 1 + 5 is 6, times 2 is 12, plus 3 is 15.

In the wild: the search bar that understands AND, OR, and parentheses

Type is:open AND (label:bug OR label:urgent) into an issue tracker, or a WHERE clause into a database, and something has to evaluate that boolean expression correctly, honoring that AND binds tighter than OR and that the parentheses regroup them. That evaluator is the arithmetic one with the operator set swapped: AND and OR in place of * and +, truth values in place of numbers, the identical two-stack, precedence-driven machinery underneath.

This is the payoff of seeing the pattern rather than memorizing a calculator. A query language, a spreadsheet formula engine, a feature-flag rule like country == "US" AND (tier == "pro" OR trial_days < 14), a template conditional: all of them are expression evaluation. The tokens and the precedence table change, the algorithm does not. And the same stack that evaluates directly can instead build the parse tree (push operands and subtrees rather than numbers), which is precisely how a compiler turns your source into the expression tree it later walks, connecting this pattern straight to tree traversal.

The trigger

You are parsing or computing something with operators, precedence, and nesting: arithmetic, boolean filters, query languages, formula engines, or validating balanced brackets. The tell is that left-to-right is wrong because some operators must wait for others, or because parentheses regroup the work. Anytime you need to "hold this until something more urgent finishes," a stack is knocking.

Where it shows up

  • Arithmetic and formulas: calculators, spreadsheet cells, interpreters evaluating numeric expressions.
  • Boolean and query evaluation: search filters, SQL WHERE clauses, feature-flag and rules-engine conditions.
  • Parsing and validation: infix-to-postfix conversion, balanced-parenthesis checking, building an expression tree for a compiler.

Where it bites

Precedence and associativity are where correctness lives or dies: get the comparison wrong (> versus >= when deciding whether a waiting operator fires) and left-associative operators like subtraction silently produce wrong results. Unary minus, multi-digit and floating-point numbers, and whitespace all need explicit handling that a naive tokenizer skips. Malformed input (unbalanced parentheses, a trailing operator) will pop an empty stack and crash unless you guard it, and division by zero needs its own check.

When it is the wrong tool

If the expression is already in postfix (Reverse Polish) form, you do not need the operator stack at all; a single value stack evaluates it in one clean pass. If your language of expressions is rich (functions, variable binding, custom precedence levels, error recovery), a hand-rolled two-stack evaluator gets fragile fast, and a real parser (recursive descent, or a generator like a Pratt parser) is the maintainable path. And if a safe, sandboxed evaluator already exists for your domain, reaching for it beats reimplementing operator precedence and inheriting its edge-case bugs.

Its neighbors

This pattern is the marquee application of Stacks and Queues, using the stack's last-in-first-out discipline to model precedence and nesting. It connects directly to Binary Tree Traversals, because an expression is a tree and postorder evaluation of that tree is the recursive twin of the stack method. And the recursive-descent alternative to the two stacks is close kin to Backtracking, another recursion over structured input.

References