Evaluating Postfix Expressions with a Stack
A stack-based evaluation algorithm can detect errors in a postfix expression without needing parentheses or a human reader.
A Plausible-Looking Broken Expression
Postfix notation places each operator after the operands it works on. The expression 2 3 + * looks almost like valid input: it has numbers, operators, and no parentheses to get wrong. A person reading it might not immediately see the problem. A stack-based evaluator can reject it without anyone reading it at all, because the same left-to-right algorithm that evaluates correct expressions also checks whether each operator has the values it needs.
What do you think happens?
Where does the stack-based algorithm first detect a problem in 2 3 + *?
Reveal answer
At the *, because the stack has only one value when it needs two
The + correctly combines 2 and 3 into 5, leaving one value on the stack. The * then tries to pop two values but finds only one, so the error is detected while processing the operator.
Tracing the Stack Token by Token
The algorithm reads the expression one token at a time. Each number is pushed onto the stack. Each operator pops two values from the top of the stack, combines them, and pushes the result back. The stack is the only place where values wait, so its contents after each token show whether the expression is still consistent. Follow the expression 2 3 + * through the stack.
Finding the Failing Operator in 2 3 + *
Evaluate the postfix expression 2 3 + * and state where the evaluation fails.
- 1Token 2
A number is pushed and waits. The stack is [2].
- 2Token 3
Another number is pushed. The stack is [2, 3].
- 3Token +
The operator needs two operands and the stack has two. It pops 3 first, which becomes the right operand, then pops 2 as the left operand. It computes 2 + 3 = 5 and pushes 5. The stack is [5].
- 4Token *
The operator needs two operands, but the stack holds only 5. The second pop has nothing to take. The algorithm reports an insufficient operands error at this token.
The evaluation fails at the * token during operator processing. The + was valid; the problem is the * with no second operand available.
Why the Pop Order Matters
Numbers are never consumed when they arrive. A value leaves the stack only when an operator asks for it, so numbers that are not yet claimed simply wait in the order they arrived. When an operator is processed, the evaluator pops twice. The first value popped came later in the input, so it becomes the right operand. The second pop supplies the left operand.
Addition gives the same result in either order, but subtraction does not. Reversing the operands of a minus sign changes the answer. The table below uses the valid expression 5 3 -, which corresponds to the infix expression 5 - 3.
| Pop order | Right operand | Left operand | Result |
|---|---|---|---|
| Correct: first pop is right | 3 | 5 | 5 - 3 = 2 |
| Swapped: first pop is left | 5 | 3 | 3 - 5 = -2 |
Both rows use the same tokens 5 3 -. Only the assignment of popped values to operands differs.
Detecting an Insufficient Operands Error
An insufficient operands error is detected when an operator tries to pop its second operand from an empty stack. The check happens during processing, at the moment the operator arrives. The evaluator never looks ahead in the input. When it reaches an operator, the only information it has is what it has already pushed, so the stack size at that operator determines whether the operator can run.
Detecting Leftover Operands at the End
The second kind of error cannot be seen until every token has been read. Consider 2 3 4 +. Each token is legal on its own: three numbers and one operator. The + consumes only the two numbers on top of the stack, 4 and 3, and pushes 7. The number 2 at the bottom is left over. The stack ends as [2, 7], holding more than one value.
A correct postfix expression ends with exactly one value on the stack, and that value is the result. Here the final stack holds two values, so the expression is missing an operator. The error is reported after the last token, because only then is it known that no further operator will consume the leftover 2.
Reading the Python Evaluator
The following short evaluator takes a postfix expression as a string, splits it into tokens, and applies the two checkpoints described above. Read it as a debugger would: for each token, ask what the stack holds and what the code is about to do to it. The code is an original teaching example written for this article, not a listing from the source.
def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token in "+-*/":
if len(stack) < 2:
raise ValueError("insufficient operands at token " + token)
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
stack.append(left / right)
else:
stack.append(float(token))
if len(stack) != 1:
raise ValueError("insufficient operators: " + str(len(stack)) + " values left")
return stack[0]- 1Line 2 creates an empty stack; this is the only place values wait.
- 2Line 3 processes tokens left to right, one at a time, with no look-ahead.
- 3Lines 4 to 14 handle operator tokens: they check for two operands, pop the right operand first, pop the left operand second, and push the result.
- 4Lines 15 to 16 handle numbers: each is converted to a float and pushed, where it waits until an operator claims it.
- 5Lines 17 to 18 run after every token has been read and check that exactly one value remains.
- Each token is either an operator or a number; there are only two branches per token.
- The size check before popping is the insufficient operands checkpoint.
- The size check after the loop is the insufficient operators checkpoint.
- The first pop is the right operand and the second pop is the left operand.
What do you think happens?
What does evaluate_postfix return for the string "5 3 -"?
Reveal answer
2.0
The tokens 5 and 3 are pushed. The - pops 3 as the right operand and 5 as the left operand, computes 5 - 3, and pushes 2.0. One value remains, so the final check passes and 2.0 is returned.
ValueError: insufficient operators: 2 values left- The loop finishes with the stack at [2.0, 7.0].
- The final check finds two values instead of one, so it raises the error.
Infix and Postfix Compared
Infix notation is the form people usually read and write, with operators placed between their operands. To decide which operation happens first, infix needs extra machinery: parentheses and precedence rules. Postfix notation removes that need. The order in which operators are applied is determined entirely by their position in the expression, so the evaluator does not need to decide anything about grouping. This is what keeps the evaluation algorithm short: each token is handled by one of two branches, a push or an operator application.
| Feature | Infix notation | Postfix notation |
|---|---|---|
| Operator position | Between its operands | After its operands |
| Grouping | Needs parentheses to override default order | No parentheses needed |
| Precedence rules | Needed to decide which operation happens first | Not needed; position fixes the order |
| Evaluation pass | Requires grouping decisions | One left-to-right pass with a stack |
Postfix notation trades visual familiarity for a simpler evaluation process.
Mistakes That Hide the Error Location
Common mistake Looking for the error only at the end of the expression
What it looks likeReading 2 3 + * and waiting until the last token to decide it is wrong.
Why it failsAn insufficient operands error is found while processing the operator, so the algorithm fails at the * as soon as it arrives.
Do this insteadCheck the stack size at each operator before popping.
Common mistake Assuming a valid-looking token sequence is a valid expression
What it looks like2 3 4 + contains only legal tokens, yet it is malformed.
Why it failsEach token is legal on its own. The problem appears only in how many values remain after all tokens are read.
Do this insteadAfter the last token, confirm that exactly one value remains on the stack.
Common mistake Swapping the pop order for subtraction
What it looks likeTreating the first popped value as the left operand, so 5 3 - gives -2 instead of 2.
Why it failsThe first popped value is the later input value, which is the right operand.
Do this insteadPop the right operand first, then the left operand.
Find the Checkpoint
Evaluate 1 2 + + by hand, one token at a time, keeping track of the stack. Decide whether the error is an insufficient operands error or an insufficient operators error, and name the token where the evaluation first fails.
Hints
- After the first + the stack holds one value.
- Ask how many values the second + needs before it pops.
- An operator that cannot pop two values is an insufficient operands error, found during processing.
Key Takeaways
- A stack-based postfix evaluator reads tokens left to right, pushes numbers, and lets each operator pop its operands, so the stack state shows whether the expression is consistent.
- An insufficient operands error is detected during processing, when an operator tries to pop a second operand from a stack that cannot supply it.
- An insufficient operators error is detected after the last token, when more than one value remains on the stack.
- Each operator pops the right operand first and the left operand second, which is essential for subtraction and division.
- Postfix notation needs no parentheses or precedence rules because operator order is fixed by position, which keeps the evaluator short.