Understanding Infix, Prefix, and Postfix Notation
Arithmetic expressions require three core elements: operands (numbers like 5 or 137), operators (symbols like +, −, ×, ÷), and rules for evaluation. In everyday mathematics, we write infix notation, where operators sit between operands: 4 + 1. This familiar format requires us to follow precedence rules (multiplication before addition) and often demands parentheses to override default ordering.
Prefix notation (Polish notation) places operators before their operands, eliminating ambiguity. The expression + 4 1 means "add 4 and 1." More complex operations like × + 3 4 5 read as "multiply (3 + 4) by 5."
Postfix notation (reverse Polish notation) reverses this: operators follow operands. The same expression becomes 3 4 + 5 ×. Both alternatives remove the need for parentheses because the operator order is unambiguous from the notation structure itself.
The History and Motivation for Polish Notation
In 1924, Polish logician Jan Łukasiewicz developed prefix notation to simplify logical expressions and reduce notational ambiguity in formal systems. During the 1950s, as computers became widespread, postfix notation gained traction because it aligns naturally with stack-based evaluation in programming languages.
Early calculators, particularly Hewlett-Packard's scientific models, used reverse Polish notation to streamline calculation workflows. Users could enter operands, press operators, and the calculator would maintain an internal stack for evaluation. This approach:
- Eliminates parentheses entirely
- Requires no precedence table lookups
- Processes expressions left-to-right in a single pass
- Reduces parsing complexity in compiler design
While modern infix notation dominates everyday use, Polish notations remain important in theoretical computer science, formal logic, and specialized programming languages like Lisp and Forth.
Converting Between Notations
Conversion between infix and postfix uses the shunting-yard algorithm, developed by Edsger Dijkstra in 1961. This algorithm reads an infix expression left-to-right, maintains an operator stack, and builds an output queue.
Example: Convert (3 + 4) × (7 − 2) to postfix:
- Read
(: push to stack - Read
3: add to output - Read
+: push to stack - Read
4: add to output - Read
): pop+from stack to output - Read
×: push to stack (higher precedence pending) - Continue similarly for the second group
- Result:
3 4 + 7 2 − ×
Converting from prefix to infix or postfix involves reading the expression in reverse and using a recursive parsing approach that respects operator arity (binary operators require two operands).
Infix: A + B × C
Prefix: + A × B C
Postfix: A B C × +
A, B, C— Operands (numbers or variables)+, ×— Binary operators applied in sequence
Evaluating Polish Notation Expressions
To evaluate a prefix expression, scan from right to left, using a stack to store intermediate results:
- If you encounter an operand, push it onto the stack
- If you encounter an operator, pop two operands, apply the operation, and push the result back
For postfix, scan left to right using the same stack mechanism. Consider − + 3 × 4 5 6 in prefix:
- Reading right-to-left: 6, 5, 4, ×, 3, +, −
- Process: 4 × 5 = 20, then 3 + 20 = 23, then 23 − 6 = 17
Postfix evaluation of the same result, 3 4 5 × + 6 −, processes left-to-right:
- Push 3, 4, 5 → see ×, pop 5 and 4, push 20
- See +, pop 20 and 3, push 23
- Push 6 → see −, pop 6 and 23, push 17
Both methods are equivalent; the choice depends on the scanning direction and whether you're reading human-friendly or machine-optimized notation.
Common Pitfalls and Practical Considerations
Understanding Polish notation requires careful attention to operator precedence, operand counting, and the fundamental differences in evaluation order.
- Operator arity and operand count — Every operator in Polish notation consumes a fixed number of operands. Binary operators (+, −, ×, ÷) require exactly two operands. If your expression has mismatched operators and operands (e.g., <code>+ 3 4 5</code>), evaluation will fail. Always ensure the total count of operators and operands obeys the rule: #operands = #operators + 1 for a valid expression.
- Parentheses are not allowed in Polish notation — Once you convert to prefix or postfix, parentheses serve no purpose and must be removed. The notation itself encodes precedence. Attempting to include brackets in a Polish notation expression will either be ignored or cause a parsing error. Plan your conversion carefully to preserve the correct operation order.
- Direction of evaluation matters for non-commutative operations — Subtraction and division are sensitive to operand order. In infix, <code>10 − 3 = 7</code>, but <code>3 − 10 = −7</code>. When converting to Polish notation, preserve the original operand sequence. Prefix: <code>− 10 3</code> means 10 − 3. Postfix: <code>10 3 −</code> also means 10 − 3. Reversing operands will invert your result.
- Stack-based evaluation can be error-prone by hand — While computers execute postfix evaluation instantly, manual calculation requires careful stack bookkeeping. Write down each intermediate result and maintain a clear list of stack contents at each step. For complex expressions with many operators, break the problem into smaller sub-expressions and verify intermediate results before proceeding.