Introduction
Arithmetic expressions are usually written in infix form, a + b, with the operator between its operands. Infix needs precedence rules, associativity rules and parentheses to be unambiguous. Two parenthesis-free forms avoid all of that:
- Postfix (reverse Polish): operator after its operands,
a b +. - Prefix (Polish): operator before its operands,
+ a b.
A stack converts infix to postfix in one left-to-right scan, and a stack evaluates postfix in one scan. Compilers and calculators use exactly these ideas. This note covers the conversion algorithm, evaluation of postfix and prefix, the stack contents during each, and bracket matching.
Conventions: single-letter or single-digit operands; the operators are ^ (power), *, /, +, -. The precedence and associativity in the table below are the conventions of this note, not those of C (C has no ^ power operator; see Operators and Expressions). Integer division truncates. The algorithms use an abstract stack (push, pop, top); no array indexing is involved.
Prerequisites
- Stacks: push, pop, top.
Core concepts
Precedence and associativity used here
| Operator | Precedence | Associativity |
|---|---|---|
^ | 3 (highest) | right: a^b^c = a^(b^c) |
* / | 2 | left: a/b/c = (a/b)/c |
+ - | 1 | left: a-b-c = (a-b)-c |
When a question supplies a different table (for example, + above *, or - right-associative), the algorithms below work unchanged with that table.
The three notations for the same expression
| Infix | Postfix | Prefix |
|---|---|---|
a+b*c | abc*+ | +a*bc |
(a+b)*(c-d) | ab+cd-* | *+ab-cd |
a-b-c | ab-c- | --abc |
a^b^c | abc^^ | ^a^bc |
Postfix and prefix of an expression are the postorder and preorder traversals of its expression tree, and the infix form without parentheses is the inorder traversal (Binary Tree Traversals). Operands appear in the same left-to-right order in all three forms; only the operators move.
How it works
Infix to postfix (operator-stack algorithm)
Scan the infix string left to right, keeping a stack of operators and left parentheses:
INFIX-TO-POSTFIX(tokens)
for each token t:
operand -> append t to output
'(' -> push t
')' -> pop and append until '(' is on top; pop '(' (do not output it)
operator o -> while top is an operator p (not '(') and
prec(p) > prec(o), or prec(p) == prec(o) and o is left-associative:
pop p and append it
push o
at end: pop and append all remaining operatorsThe only subtle rule is equal precedence. For a left-associative operator the earlier one leaves first (a-b-c gives ab-c-). For the right-associative ^ the earlier one stays (a^b^c gives abc^^).
Trace for a+b*c-d/e:
| Token | Action | Stack (bottom to top) | Output |
|---|---|---|---|
a | output | (empty) | a |
+ | push | + | a |
b | output | + | ab |
* | * above +: push | +* | ab |
c | output | +* | abc |
- | pop * (higher), pop + (equal, left-assoc), push - | - | abc*+ |
d | output | - | abc*+d |
/ | push | -/ | abc*+d |
e | output | -/ | abc*+de |
| end | pop all | (empty) | abc*+de/- |
The stack never holds more than 2 symbols here.
Infix to prefix
One standard method: reverse the infix string, swapping ( and ); convert with the algorithm above but with the equal-precedence rule mirrored (pop on equal precedence only for the right-associative operator); then reverse the result. For a-b-c this gives --abc, which is , and for a^b^c it gives ^a^bc. The alternative is to build the expression tree and read it in preorder.
Evaluating postfix
EVALUATE-POSTFIX(tokens)
for each token t:
operand -> push its value
operator -> b <- POP(S); a <- POP(S); push (a op b) // first pop is the RIGHT operand
at end: the stack holds exactly one value, the resultTrace for 6 2 3 + - 3 8 2 / + * 2 ^ 3 +:
| Token | Stack after (bottom to top) |
|---|---|
6 2 3 | 6 2 3 |
+ | 6 5 |
- | 1 |
3 8 2 | 1 3 8 2 |
/ | 1 3 4 |
+ | 1 7 |
* | 7 |
2 | 7 2 |
^ | 49 |
3 | 49 3 |
+ | 52 |
The result is 52, and the stack reaches a maximum of 4 values. Getting the operand order wrong for -, / or ^ is an easy mistake: 5 3 - is , not .
Evaluating prefix
Scan right to left with the same stack; now the first value popped is the left operand:
EVALUATE-PREFIX(tokens)
for each token t from right to left:
operand -> push its value
operator -> a <- POP(S); b <- POP(S); push (a op b)- * 2 3 4 is ; - - 8 3 2 is .
Evaluating infix directly with two stacks
Conversion and evaluation can be fused. Keep an operand stack and an operator stack. Process tokens exactly as in the conversion algorithm, but wherever the conversion would append an operator to the output, instead pop two values (right operand first), apply the operator and push the result on the operand stack. At the end, apply the remaining operators; the operand stack then holds the single result. With the table above, 2+3*4-8/2 evaluates to 10, (2+3)*(7-4) to 15, 2^3^2 to 512 and 9-4-3 to 2. This is the essence of operator-precedence evaluation in calculators and simple interpreters.
Balanced brackets
Push each opening bracket; on a closing bracket, the stack must be non-empty and its top must be the matching opener, which is popped. At the end the stack must be empty. {[()()]} is balanced; ([)] fails at ) because the top is [; (( fails at the end; ()) fails at the second ) because the stack is empty.
Worked examples
Example 1. (a+b)*(c-d): postfix ab+cd-*, prefix *+ab-cd.
Example 2. a+b*(c^d-e)^(f+g*h)-i: postfix abcd^e-fgh*+^*+i-. When - arrives after d, the ^ on top is popped; the ( stops further popping. The second ^ (after )) is pushed above * because it has higher precedence.
Example 3. 2 3 2 ^ ^ evaluates to , consistent with right associativity of ^.
Example 4. 5 3 - 2 - evaluates to .
Common traps in expression conversion
Parentheses on the stack. Opening parentheses are pushed; they are never sent to the output. A closing parenthesis pops until the matching opening parenthesis, which is then discarded. Forgetting to discard the opening parenthesis produces a wrong postfix string.
Right-associative operators. Exponentiation (^ in many textbooks) is right-associative: while the top of the stack has strictly greater precedence than the new operator, pop; equal precedence does not cause a pop. So a^b^c becomes abc^^, not ab^c^.
Unary minus. Unary minus is best written as a distinct token (for example u-) with precedence above multiplication. Treating it as ordinary subtraction yields the wrong postfix form.
Important properties and observations
- Both conversion and evaluation use token/stack operations for tokens, assuming -cost arithmetic. Worst-case auxiliary stack space is , plus output storage for conversion: each token is pushed and popped at most once.
- In the conversion the stack holds operators and parentheses; in evaluation it holds operand values.
- A postfix expression with only binary operators is well formed exactly when, scanning left to right, the count (operands minus operators) stays at least 1 after the first token and equals 1 at the end.
- Postfix needs no parentheses and no precedence rules; its evaluation order is fixed by the token order.
- Function calls, recursion and bracket matching are other uses of the same LIFO discipline (Recursion).
GATE examination perspective
- Convert infix to postfix or prefix, possibly with a non-standard precedence or associativity table.
- Maximum stack size or stack contents after reading a given token during conversion or evaluation: write the trace table.
- Evaluate postfix or prefix: watch the operand order for non-commutative operators.
- Expression trees: postfix and prefix are postorder and preorder.
- Bracket matching and other single-stack checks.
Summary
Sources
- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2007: Chapter 2 (syntax-directed translation / expression evaluation).
- D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997: Section 2.3.1 (traversal orders and their correspondence with Polish notations).