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

Infix to postfix conversion of 9 characters.inopsout3+4*(2-1)

Convert "3+4*(2-1)" to postfix. Operands go straight to the output. An operator first flushes any operator on the stack with precedence at least its own, then waits on the stack itself. A closing bracket flushes back to its opener.

Check your understanding

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

  1. Next is '3'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Straight to the output. Operands never wait.

  2. Next is '+'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.

  3. Next is '4', top of the operator stack is '+'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Straight to the output. Operands never wait.

  4. Next is '*', top of the operator stack is '+'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.

  5. Next is '(', top of the operator stack is '*'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.

  6. Next is '2', top of the operator stack is '('. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Straight to the output. Operands never wait.

  7. Next is '-', top of the operator stack is '('. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Onto the stack, nothing flushed. Nothing on the stack outranks it, so it just waits.

  8. Next is '1', top of the operator stack is '-'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Straight to the output. Operands never wait.

  9. Next is ')', top of the operator stack is '-'. What happens?

    • Straight to the output
    • Onto the stack, nothing flushed
    • Flush first, then act

    Answer: Flush first, then act. Higher or equal precedence operators must come out first to keep the order right.

How it runs, step by step

  1. Convert "3+4*(2-1)" to postfix. Operands go straight to the output. An operator first flushes any operator on the stack with precedence at least its own, then waits on the stack itself. A closing bracket flushes back to its opener.

    Infix to postfix conversion of 9 characters.

  2. '3'. An operand goes straight to the output.

    Character 3. Output 3, operators empty.

  3. '+'. Nothing to flush, so it waits on the stack.

    Character +. Output 3, operators +.

  4. '4'. An operand goes straight to the output.

    Character 4. Output 34, operators +.

  5. '*'. '+' on the stack binds looser, so it stays and '*' goes on top.

    Character *. Output 34, operators +*.

  6. '('. An opening bracket goes on the stack as a fence: nothing below it can be flushed until it closes.

    Character (. Output 34, operators +*(.

  7. '2'. An operand goes straight to the output.

    Character 2. Output 342, operators +*(.

  8. '-'. Nothing to flush, so it waits on the stack.

    Character -. Output 342, operators +*(-.

  9. '1'. An operand goes straight to the output.

    Character 1. Output 3421, operators +*(-.

  10. ')'. A closing bracket: - moves to the output. The '(' is discarded.

    Character ). Output 3421-, operators +*.

  11. The end of input flushes the remaining operators, *+. Postfix: 3421-*+. Each character is pushed and popped at most once, so the conversion is O(n).

    Postfix 3421-*+.

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