Stacks for Expressions

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.

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.

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.

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.