AlgoScope

Stacks for Expressions

A stack remembers what is still pending in the order it must be resolved: the most recent thing first. That is exactly what nested brackets need, since the last opened bracket is the first one that must close. Postfix notation removes the need for brackets altogether, because every operator arrives right after the two values it applies to, so a value stack is all the evaluator needs. Converting infix to postfix, or evaluating infix directly, is the same idea with operators waiting on a stack until something of lower precedence arrives and forces them out.

The player

Bracket matching over 8 characters with an empty stack.instk{[()()]}

Read "{[()()]}" left to right. An opener waits on the stack. A closer must match the most recent opener, which is the top of the stack, and pops it. Balanced means every closer matched and nothing is left open at the end.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.

  1. Next is '{' and the top of the stack is nothing. What happens?

    • Push it
    • Pop the top
    • Unbalanced, stop

    Answer: Push it. Openers always push: the matching closer has not come yet.

  2. Next is '[' and the top of the stack is '{'. What happens?

    • Push it
    • Pop the top
    • Unbalanced, stop

    Answer: Push it. Openers always push: the matching closer has not come yet.

  3. Next is '(' and the top of the stack is '['. What happens?

    • Push it
    • Pop the top
    • Unbalanced, stop

    Answer: Push it. Openers always push: the matching closer has not come yet.

  4. Next is ')' and the top of the stack is '('. What happens?

    • Pop the top
    • Push it
    • Unbalanced, stop

    Answer: Pop the top. The most recent opener is exactly the one this closer needs.

  5. Next is '(' and the top of the stack is '['. What happens?

    • Push it
    • Pop the top
    • Unbalanced, stop

    Answer: Push it. Openers always push: the matching closer has not come yet.

  6. Next is ')' and the top of the stack is '('. What happens?

    • Pop the top
    • Push it
    • Unbalanced, stop

    Answer: Pop the top. The most recent opener is exactly the one this closer needs.

  7. Next is ']' and the top of the stack is '['. What happens?

    • Pop the top
    • Push it
    • Unbalanced, stop

    Answer: Pop the top. The most recent opener is exactly the one this closer needs.

  8. Next is '}' and the top of the stack is '{'. What happens?

    • Pop the top
    • Push it
    • Unbalanced, stop

    Answer: Pop the top. The most recent opener is exactly the one this closer needs.

How it runs, step by step

  1. Read "{[()()]}" left to right. An opener waits on the stack. A closer must match the most recent opener, which is the top of the stack, and pops it. Balanced means every closer matched and nothing is left open at the end.

    Bracket matching over 8 characters with an empty stack.

  2. '{' at 0. An opener: push it. The stack is now {.

    Push {.

  3. '[' at 1. An opener: push it. The stack is now {[.

    Push [.

  4. '(' at 2. An opener: push it. The stack is now {[(.

    Push (.

  5. ')' at 3. A closer, and the top is '(', its partner: pop it. The stack is now {[.

    Pop ( for ).

  6. '(' at 4. An opener: push it. The stack is now {[(.

    Push (.

  7. ')' at 5. A closer, and the top is '(', its partner: pop it. The stack is now {[.

    Pop ( for ).

  8. ']' at 6. A closer, and the top is '[', its partner: pop it. The stack is now {.

    Pop [ for ].

  9. '}' at 7. A closer, and the top is '{', its partner: pop it. The stack is now empty.

    Pop { for }.

  10. Every closer matched and the stack is empty: balanced. One pass, O(n), with at most n on the stack.

    Balanced.

The code

Stacks for Expressions, in Python

def balanced(s):
    stack = deque()
    for c in s:
        if c in "([{": stack.append(c)                            # opener waits
        elif not stack or stack.pop() != pair(c): return False    # wrong closer
    return not stack                                              # nothing left open

def eval_postfix(tokens):
    stack = deque()
    for t in tokens:
        if t.isdigit(): stack.append(int(t))
        else:
            b = stack.pop(); a = stack.pop(); stack.append(apply(t, a, b))
    return stack[-1]

def to_postfix(infix):
    out = []; ops = deque()
    for c in infix:
        if c.isdigit(): out.append(c)                             # operands go straight out
        elif c == '(': ops.append(c)
        elif c == ')':
            while ops[-1] != '(': out.append(ops.pop())
            ops.pop()
        else:                                                     # operator
            while ops and ops[-1] != '(' and prec(ops[-1]) >= prec(c):
                out.append(ops.pop())                             # flush by precedence
            ops.append(c)
    while ops: out.append(ops.pop())
    return "".join(out)

def eval_infix(s):
    vals = deque(); ops = deque()
    def reduce():                                                 # apply the top operator
        b = vals.pop(); a = vals.pop(); vals.append(apply(ops.pop(), a, b))
    for c in s:
        if c.isdigit(): vals.append(int(c))
        elif c == '(': ops.append(c)
        elif c == ')':
            while ops[-1] != '(': reduce()
            ops.pop()
        else:
            while ops and ops[-1] != '(' and prec(ops[-1]) >= prec(c): reduce()
            ops.append(c)
    while ops: reduce()
    return vals[-1]

Stacks for Expressions, in JavaScript

function balanced(s) {
  const stack = [];
  for (const c of s) {
    if ("([{".includes(c)) {
      stack.push(c);                                                  // opener waits
    } else if (stack.length === 0 || stack.pop() !== pair(c)) {
      return false;                                                   // wrong closer
    }
  }
  return stack.length === 0;                                          // nothing left open
}

function evalPostfix(tokens) {
  const stack = [];
  for (const t of tokens) {
    if (t >= "0" && t <= "9") {
      stack.push(Number(t));
    } else {
      const b = stack.pop(), a = stack.pop();
      stack.push(apply(t, a, b));
    }
  }
  return stack.at(-1);
}

function toPostfix(infix) {
  const out = []; const ops = [];
  for (const c of infix) {
    if (c >= "0" && c <= "9") {
      out.push(c);                                                    // operands go straight out
    } else if (c === "(") {
      ops.push(c);
    } else if (c === ")") {
      while (ops.at(-1) !== "(") out.push(ops.pop());
      ops.pop();
    } else {                                                          // operator
      while (ops.length > 0 && ops.at(-1) !== "(" && prec(ops.at(-1)) >= prec(c)) {
        out.push(ops.pop());                                          // flush by precedence
      }
      ops.push(c);
    }
  }
  while (ops.length > 0) out.push(ops.pop());
  return out.join("");
}

function evalInfix(s) {
  const vals = []; const ops = [];
  const reduce = () => {                                              // apply the top operator
    const b = vals.pop(), a = vals.pop();
    vals.push(apply(ops.pop(), a, b));
  };
  for (const c of s) {
    if (c >= "0" && c <= "9") {
      vals.push(Number(c));
    } else if (c === "(") {
      ops.push(c);
    } else if (c === ")") {
      while (ops.at(-1) !== "(") reduce();
      ops.pop();
    } else {
      while (ops.length > 0 && ops.at(-1) !== "(" && prec(ops.at(-1)) >= prec(c)) reduce();
      ops.push(c);
    }
  }
  while (ops.length > 0) reduce();
  return vals.at(-1);
}

Stacks for Expressions, in Kotlin

fun balanced(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    for (c in s) {
        if (c in "([{") stack.addLast(c)                                  // opener waits
        else if (stack.isEmpty() || stack.removeLast() != pair(c)) return false   // wrong closer
    }
    return stack.isEmpty()                                            // nothing left open
}

fun evalPostfix(tokens: List<Char>): Int {
    val stack = ArrayDeque<Int>()
    for (t in tokens) {
        if (t.isDigit()) stack.addLast(t.digitToInt())
        else { val b = stack.removeLast(); val a = stack.removeLast(); stack.addLast(apply(t, a, b)) }
    }
    return stack.last()
}

fun toPostfix(infix: String): String {
    val out = StringBuilder(); val ops = ArrayDeque<Char>()
    for (c in infix) when {
        c.isDigit() -> out.append(c)                                     // operands go straight out
        c == '(' -> ops.addLast(c)
        c == ')' -> { while (ops.last() != '(') out.append(ops.removeLast()); ops.removeLast() }
        else -> {                                                        // operator
            while (ops.isNotEmpty() && ops.last() != '(' && prec(ops.last()) >= prec(c)) {
                out.append(ops.removeLast())                                 // flush by precedence
            }
            ops.addLast(c)
        }
    }
    while (ops.isNotEmpty()) out.append(ops.removeLast())
    return out.toString()
}

fun evalInfix(s: String): Int {
    val vals = ArrayDeque<Int>(); val ops = ArrayDeque<Char>()
    fun reduce() {                                                    // apply the top operator
        val b = vals.removeLast(); val a = vals.removeLast(); vals.addLast(apply(ops.removeLast(), a, b))
    }
    for (c in s) when {
        c.isDigit() -> vals.addLast(c.digitToInt())
        c == '(' -> ops.addLast(c)
        c == ')' -> { while (ops.last() != '(') reduce(); ops.removeLast() }
        else -> {
            while (ops.isNotEmpty() && ops.last() != '(' && prec(ops.last()) >= prec(c)) reduce()
            ops.addLast(c)
        }
    }
    while (ops.isNotEmpty()) reduce()
    return vals.last()
}

Write it yourself

Define isBalanced(expression) and return true when every bracket closes in the right order. It runs in your browser against this lesson's own 2 examples.

// Push an opening bracket, and a closing one must match what comes off the top. Anything left over at the end is unclosed.function isBalanced(expression) { return false;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Brackets: push openers, and a closer must match the top of the stack. Balanced means the stack ends empty.
    • Postfix: push numbers. An operator pops two (the lower one is the left operand) and pushes the result.
    • Infix: an operator flushes everything on the stack with precedence at least its own, then waits. Brackets fence the stack.

    Where this is used

    PDF page content and PostScriptDocument formats

    A PDF page is drawn by a stream of postfix operators, so 1 0 0 1 72 720 cm pushes six numbers and then names the operator that consumes them. Every operator takes a fixed count of operands that are already on the stack, so the renderer needs no precedence table and no lookahead, and it can draw while the stream is still arriving. PostScript, the older format PDF's drawing model grew out of, takes the same design all the way to a programming language, with the operand stack exposed to the program itself.

    JVM bytecode and WebAssemblyRuntimes

    Both are stack machines, so a + b compiles to iload_1, iload_2, iadd, which is postfix. The compiler produces that order by walking the expression tree in post-order, the same rearrangement the infix-to-postfix pass does here, and a stack interpreter can then run it with exactly the postfix loop above, though production engines compile it down to registers instead. Both formats are checked before they run: the JVM verifier and the WebAssembly validator work out the stack's types at every instruction, so each pop is proved in advance to find the operand types it expects.

    Bracket errors in the CPython tokenizerCompilers

    CPython's tokenizer keeps a stack of open brackets together with the line and column where each was opened. That is what lets Python 3.10 and later say which opener a mismatched closer belongs to, instead of pointing vaguely at the end of the file. The same stack decides whether a newline ends a statement: while it is non-empty you are inside brackets, so the line just continues, which is why a list literal can span many lines with no backslashes.

    RPN calculators and ForthHardware

    The HP-35 and the HP-12C have no equals key and no brackets: you push operands with ENTER and each operator pops what it needs. On a machine with a few hundred bytes of memory, a value stack plus a pop-per-operator rule is far less hardware than an infix parser carrying a precedence table and a bracket stack. Forth, and the Open Firmware boot environments built on it, made the same trade to stay small enough to live in ROM.

    Why it works this way

    Why a stack and not a counter

    With one kind of bracket a counter is enough: add one for an opener, subtract one for a closer, and it goes negative exactly when a closer arrives too early. With three kinds it fails, because ([)] and ([]) keep the same count at every step and both end at zero. What has to be remembered is not how many brackets are open but which one is innermost, and only the stack holds that.

    Why the flush test is >= and not >

    That comparison is where associativity lives. In 8/4/2 the second slash arrives while the first is still on the stack at equal precedence, so >= flushes it and you get (8/4)/2 = 1, which is what left-associative division means. Change it to > and the first slash waits its turn, producing 8/(4/2) = 4, while every expression with a single operator still comes out right. Right-associative operators such as exponentiation are the exception and need > for exactly this reason.

    The two pops come off in reverse

    Taking b before a is not a stylistic choice: the stack hands back the right operand first, because it was pushed last. Swap those two lines and + and * keep giving correct answers while - and / quietly stop, so 5 3 - evaluates to -2 instead of 2. It is a bug that passes half of any test set you throw at it.

    Postfix only drops brackets if every operator has a fixed arity

    Postfix reads unambiguously because seeing an operator tells you exactly how many values to pop. Unary minus breaks that rule: in 3 - -4 the same character means two different things, and once both are written as a bare - in the output nothing can tell them apart. Real converters give unary minus its own token and decide which one it is from position: a minus that follows another operator or an opening bracket, or that starts the expression, is the unary one.

    Read more

    Next up

    Matrix

    Row-major order

    Next lesson: Matrix