Expression Evaluation: Infix, Prefix, Postfix
You'll learn how stacks make it possible to evaluate arithmetic expressions written in different notations.
The Three Notations
When we write math expressions like 3 + 4, we're using infix notation — the operator (+) sits between its operands. But computers can also work with two other formats:
- Prefix (Polish notation): operator comes before operands →
+ 3 4 - Postfix (Reverse Polish notation): operator comes after operands →
3 4 +
Why do these matter? Postfix and prefix eliminate the need for parentheses and operator precedence rules, making evaluation simpler and faster.
How Stacks Enable Evaluation
Postfix evaluation is beautifully suited for stacks:
- Scan the expression left to right
- If you see a number, push it onto the stack
- If you see an operator, pop two operands, apply the operator, and push the result back
Example: 5 3 + 2 *
- Push 5, push 3
- See
+: pop 3 and 5, compute 5+3=8, push 8 - Push 2
- See
*: pop 2 and 8, compute 8*2=16, push 16 - Final answer: 16
Infix evaluation is trickier because of precedence (multiplication before addition) and parentheses. Stacks handle this by maintaining both an operand stack and an operator stack, processing operators based on their priority.
Prefix evaluation works similarly to postfix, but you scan right-to-left instead.
Why This Matters
Many compilers and calculators convert infix expressions to postfix internally because stack-based postfix evaluation is straightforward and efficient — no complex precedence logic needed during evaluation.
Key Takeaway: Stacks naturally support expression evaluation, especially in postfix notation where operands are pushed and operators trigger pop-compute-push cycles, making arithmetic parsing mechanical and elegant.