Stacks: Push and Pop Operations

A postfix expression places each operator after the operands it works on. Because of this placement, an expression can be evaluated from left to right using a stack, with no parentheses needed. The same structure also makes certain mistakes easy to catch. A stack-based evaluation algorithm can reject a malformed expression on its own, without a person reading it.

Two kinds of malformed input are worth studying. In the first, an operator appears with too few operands before it. In the second, operands are left over with too few operators after them. Both expressions look close to valid input, and both are caught by the same algorithm. The question this article answers is when the algorithm knows something is wrong, and which kind of error it has found at that moment.

The algorithm reads the expression one token at a time. Each number is pushed onto the stack. Each operator takes its operands from the top of the stack: it pops two values, combines them, and pushes the result back. The stack is the only place where values wait, so its contents at each step show whether the expression is still consistent.

An insufficient operands error is detected when an operator tries to pop its second operand from an empty stack. Each operator needs two values, so before it acts, the algorithm checks that the stack can supply them. The check happens while the operator is being processed, which is why this error is found earlier than the other kind.

The diagram shows the decision that matters. For a number, the algorithm pushes it and moves on. For an operator, it checks whether the stack holds two values. If it does, the operator pops both, combines them, and pushes the result. If it does not, the algorithm stops with an insufficient operands error. In the faulty expression 2 3 + *, the operator that fails is the multiplication, because the plus has already reduced the stack to a single value.

An insufficient operators error is detected when values remain on the stack at the end of the algorithm. A valid expression reduces to exactly one value once every token has been read. If more than one value is still on the stack, there were not enough operators to combine all the operands, and the error is found only at this final checkpoint.

Consider 2 3 4 +. Every token is legal on its own: three numbers and one operator. The plus pops only the two numbers on top, 4 and 3, and pushes 7. The number 2 at the bottom is left over, so the stack ends with two values. No operator ever failed, so the algorithm cannot catch this mistake until all tokens have been read.

The same algorithm handles valid and faulty input. The only difference is what the stack looks like at the moment of the operator check or at the end of reading. The table below places the three expressions side by side. The first two come from the source, and the valid expression 2 3 + 4 * is a generated contrast example.