Evaluating Expressions with Stacks
Why 2 + 3 × 4 is 14
A cheap calculator applies each operator the moment you press the next one, so 2 + 3 × 4 comes out as (2 + 3) × 4 = 20. The rule you learned at school says multiply first: 2 + 12 = 14. The rule is what makes evaluating an expression hard. When the + arrives, you can't apply it yet: something that binds tighter may still come.
Doing it by hand, you'd find every × and ÷, work it out and write the result in its place, then do the + and −. In code that's splicing a list, again and again:
def by_hand(tokens):
t = list(tokens) # numbers and operators, alternating
for level in (("*", "/"), ("+", "-")):
i = 1
while i < len(t):
if t[i] in level: # apply it and splice the result into the list
a, op, b = t[i - 1], t[i], t[i + 1]
t[i - 1:i + 2] = [a * b if op == "*" else int(a / b) if op == "/" else a + b if op == "+" else a - b]
else:
i += 2
return t[0]
Each splice shifts the rest of the list, so a long expression costs O(n²). On our judge, with random single-digit numbers joined by +, - and *:
| Numbers | By hand, splicing | One pass with a stack |
|---|---|---|
| 20,000 | 60 ms | 7.3 ms |
| 40,000 | 211 ms | 14.3 ms |
| 80,000 | 872 ms | 29.0 ms |
Doubling the length made the splicing version about four times slower. The stack version, from the Basic Calculator II section below, keeps what's waiting on a stack and touches each token once.
That's the idea all through this lesson: whatever can't be done yet waits on a stack, until its turn comes.
Postfix: no precedence at all
Write the operator after its two operands and the problem disappears. 2 + 3 × 4 becomes 2 3 4 × +; (2 + 3) × 4 becomes 2 3 + 4 ×. That's postfix, also called reverse Polish notation. There's no precedence to know and no brackets, because the order of the tokens already says what happens first.
Evaluating it takes one stack of values. Push each number. An operator pops two values, applies itself and pushes the result. The value popped first is the right operand: in 13 5 /, 5 comes off first, and the answer is 13 / 5, not 5 / 13.
Evaluating 4 13 5 / + — The tokens on top, the values waiting on the stack. Amber marks the two an operator takes.
Evaluate Reverse Polish Notation in full. Division truncates toward zero, as in C, C++ and Java: −7 / 2 is −3. Python's // rounds down to −4 instead, so Python uses int(a / b), which is exact for the 32-bit values this problem promises:
int evalRPN(const vector<string>& tokens) {
stack<long long> values; // operands waiting for an operator
for (const string& t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
long long b = values.top(); values.pop(); // the first pop is the right operand
long long a = values.top(); values.pop();
if (t == "+") values.push(a + b);
else if (t == "-") values.push(a - b);
else if (t == "*") values.push(a * b);
else values.push(a / b); // C++ division truncates toward zero
} else {
values.push(stoll(t)); // a number, maybe negative like "-11"
}
}
return (int)values.top();
}
def eval_rpn(tokens):
values = [] # operands waiting for an operator
for t in tokens:
if t in ("+", "-", "*", "/"):
b = values.pop() # the first pop is the right operand
a = values.pop()
if t == "+":
values.append(a + b)
elif t == "-":
values.append(a - b)
elif t == "*":
values.append(a * b)
else:
values.append(int(a / b)) # truncate toward zero; // would round down
else:
values.append(int(t)) # a number, maybe negative like "-11"
return values[0]
static int evalRPN(String[] tokens) {
Deque<Integer> values = new ArrayDeque<>(); // operands waiting for an operator
for (String t : tokens) {
if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
int b = values.pop(); // the first pop is the right operand
int a = values.pop();
if (t.equals("+")) values.push(a + b);
else if (t.equals("-")) values.push(a - b);
else if (t.equals("*")) values.push(a * b);
else values.push(a / b); // Java division truncates toward zero
} else {
values.push(Integer.parseInt(t)); // a number, maybe negative like "-11"
}
}
return values.pop();
}
function evalRPN(tokens) {
const values = []; // operands waiting for an operator
for (const t of tokens) {
if (t === "+" || t === "-" || t === "*" || t === "/") {
const b = values.pop(); // the first pop is the right operand
const a = values.pop();
if (t === "+") values.push(a + b);
else if (t === "-") values.push(a - b);
else if (t === "*") values.push(a * b);
else values.push(Math.trunc(a / b)); // truncate toward zero
} else {
values.push(Number(t)); // a number, maybe negative like "-11"
}
}
return values[0];
}
Each printed 9 6 22 for LeetCode's three examples. Every token is pushed once and popped at most once, so evaluation is O(n) time, with O(n) space for the stack.
Infix: operators wait on a stack
To evaluate infix, turn it into postfix first, then use the stack above. The conversion is Dijkstra's shunting-yard algorithm, named after a railway yard that sorts wagons onto a side track. Read the tokens left to right:
- an operand goes straight to the output;
- an operator first sends to the output every operator on the stack that binds at least as tightly, then waits on the stack itself;
(goes on the stack as a fence, and)sends operators out until its(, then drops both;- at the end, the stack empties into the output.
"At least as tightly" includes an equal operator, because - and + work left to right: in 10 - 4 - 3 the first - must happen first. The one exception is ^, which works right to left: 2 ^ 3 ^ 2 is 2 ^ 9 = 512, so an equal ^ stays on the stack.
Converting 2+3*(4-1)^2 — The infix on top, the operators waiting on the stack, the postfix filling in below.
Evaluated with the postfix stack, 2341-2^*+ gives 29, the same as 2 + 3 × (4 − 1)². Here is the conversion as Infix to Postfix Using Stack asks for it, with single letters or digits as operands:
string infixToPostfix(const string& s) {
map<char, int> rank = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
string out;
stack<char> ops; // operators waiting for their turn
for (char c : s) {
if (isalnum(c)) {
out += c; // an operand goes straight out
} else if (c == '(') {
ops.push(c); // a fence: nothing under it leaves until its ')'
} else if (c == ')') {
while (ops.top() != '(') { out += ops.top(); ops.pop(); }
ops.pop(); // drop the '('
} else {
// whatever on top binds at least as tightly leaves first; '^' is right-associative, so an equal '^' stays
while (!ops.empty() && ops.top() != '(' &&
(rank[ops.top()] > rank[c] || (rank[ops.top()] == rank[c] && c != '^'))) {
out += ops.top(); ops.pop();
}
ops.push(c);
}
}
while (!ops.empty()) { out += ops.top(); ops.pop(); }
return out;
}
def infix_to_postfix(s):
rank = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], [] # ops: operators waiting for their turn
for c in s:
if c.isalnum():
out.append(c) # an operand goes straight out
elif c == "(":
ops.append(c) # a fence: nothing under it leaves until its ")"
elif c == ")":
while ops[-1] != "(":
out.append(ops.pop())
ops.pop() # drop the "("
else:
# whatever on top binds at least as tightly leaves first; "^" is right-associative, so an equal "^" stays
while ops and ops[-1] != "(" and (rank[ops[-1]] > rank[c] or (rank[ops[-1]] == rank[c] and c != "^")):
out.append(ops.pop())
ops.append(c)
while ops:
out.append(ops.pop())
return "".join(out)
static String infixToPostfix(String s) {
Map<Character, Integer> rank = Map.of('+', 1, '-', 1, '*', 2, '/', 2, '^', 3);
StringBuilder out = new StringBuilder();
Deque<Character> ops = new ArrayDeque<>(); // operators waiting for their turn
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
out.append(c); // an operand goes straight out
} else if (c == '(') {
ops.push(c); // a fence: nothing under it leaves until its ')'
} else if (c == ')') {
while (ops.peek() != '(') out.append(ops.pop());
ops.pop(); // drop the '('
} else {
// whatever on top binds at least as tightly leaves first; '^' is right-associative, so an equal '^' stays
while (!ops.isEmpty() && ops.peek() != '(' &&
(rank.get(ops.peek()) > rank.get(c) || (rank.get(ops.peek()).equals(rank.get(c)) && c != '^'))) {
out.append(ops.pop());
}
ops.push(c);
}
}
while (!ops.isEmpty()) out.append(ops.pop());
return out.toString();
}
function infixToPostfix(s) {
const rank = { "+": 1, "-": 1, "*": 2, "/": 2, "^": 3 };
const out = [];
const ops = []; // operators waiting for their turn
for (const c of s) {
if (/[a-z0-9]/i.test(c)) {
out.push(c); // an operand goes straight out
} else if (c === "(") {
ops.push(c); // a fence: nothing under it leaves until its ")"
} else if (c === ")") {
while (ops[ops.length - 1] !== "(") out.push(ops.pop());
ops.pop(); // drop the "("
} else {
// whatever on top binds at least as tightly leaves first; "^" is right-associative, so an equal "^" stays
while (ops.length && ops[ops.length - 1] !== "(" &&
(rank[ops[ops.length - 1]] > rank[c] || (rank[ops[ops.length - 1]] === rank[c] && c !== "^"))) {
out.push(ops.pop());
}
ops.push(c);
}
}
while (ops.length) out.push(ops.pop());
return out.join("");
}
Each printed abc*+ abc+*d/ ab-c- abc^^ ab+cd-* for a+b*c, a*(b+c)/d, a-b-c, a^b^c, (a+b)*(c-d). Note ab-c-: the first - left before the second arrived. And abc^^: the two ^ waited and left in reverse. Each token is pushed and popped at most once: O(n).
Now you run the shunting yard
Below, you route every token yourself: an operand to the output, an operator onto the stack once whatever binds at least as tightly has left, a pop when the rules say an operator's turn has come. A move that breaks a rule is refused, with the rule. When the input is used up, the postfix is evaluated on a stack of values, so you see the number your routing produced.
Converting between notations
The six conversion problems all use the same stack, holding finished sub-expressions as strings. From postfix to infix: push operands; an operator pops two, the first being the right one, and pushes the bracketed result:
def postfix_to_infix(s):
parts = [] # finished sub-expressions, as strings
for c in s:
if c.isalnum():
parts.append(c)
else:
b = parts.pop() # the first pop is the right operand
a = parts.pop()
parts.append("(" + a + c + b + ")")
return parts[0]
It returned ((a*b)+c) and ((A+B)*(C-D)) for ab*c+ and AB+CD-*. From prefix, read the string right to left; now the first pop is the left operand:
def prefix_to_infix(s):
parts = []
for c in reversed(s): # prefix read right to left
if c.isalnum():
parts.append(c)
else:
a = parts.pop() # read backwards, the first pop is the left operand
b = parts.pop()
parts.append("(" + a + c + b + ")")
return parts[0]
It returned ((A-(B/C))*((A/K)-L)) and ((A+B)*(C-D)) for *-A/BC-/AKL and *+AB-CD. Postfix to prefix and prefix to postfix are the same loops, building op + a + b or a + b + op instead of a bracketed infix.
Infix to prefix is shunting-yard run right to left, with the output reversed at the end. One rule flips: read backwards, an equal left-associative operator must now stay on the stack, and an equal ^ must leave:
def infix_to_prefix(s):
rank = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], []
for c in reversed(s): # read right to left, so ")" opens and "(" closes
if c.isalnum():
out.append(c)
elif c == ")":
ops.append(c)
elif c == "(":
while ops[-1] != ")":
out.append(ops.pop())
ops.pop()
else:
# read backwards, an equal left-associative operator must stay: pop only what binds tighter (or an equal ^)
while ops and ops[-1] != ")" and (rank[ops[-1]] > rank[c] or (rank[ops[-1]] == rank[c] and c == "^")):
out.append(ops.pop())
ops.append(c)
while ops:
out.append(ops.pop())
return "".join(reversed(out))
It returned /*a+bcd, *-a/bc-/akl and ^a^bc for a*(b+c)/d, (a-b/c)*(a/k-l) and a^b^c, matching Infix to Prefix Conversion. The bugs below show what the unflipped rule does.
Basic Calculator II: two levels, one stack
Basic Calculator II evaluates a string like 14-3*4/5 with non-negative integers, + - * / and spaces, but no brackets. With only two levels you don't need the full shunting yard. Keep the operator before the number you're reading. When the number ends, + pushes it, - pushes its negative, and * or / combine it with the top straight away, since nothing can bind tighter. At the end, add up the stack.
Calculating 14-3*4/5 — The number being applied is highlighted; the stack holds the terms to add up.
int calculate(const string& s) {
vector<long long> terms; // the numbers to add up at the end
long long num = 0;
char op = '+'; // the operator before the number being read
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (isdigit(c)) num = num * 10 + (c - '0'); // a number can have several digits
if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) { // an operator, or the end
if (op == '+') terms.push_back(num);
else if (op == '-') terms.push_back(-num);
else if (op == '*') terms.back() *= num;
else terms.back() /= num; // truncates toward zero
op = c;
num = 0;
}
}
return (int)accumulate(terms.begin(), terms.end(), 0LL);
}
def calculate(s):
terms, num, op = [], 0, "+" # terms: the numbers to add up at the end
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c) # a number can have several digits
if c in "+-*/" or i == len(s) - 1: # an operator, or the end: apply the one before this number
if op == "+":
terms.append(num)
elif op == "-":
terms.append(-num)
elif op == "*":
terms.append(terms.pop() * num)
else:
terms.append(int(terms.pop() / num)) # truncate toward zero
op, num = c, 0
return sum(terms)
static int calculate(String s) {
Deque<Integer> terms = new ArrayDeque<>(); // the numbers to add up at the end
int num = 0;
char op = '+'; // the operator before the number being read
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) num = num * 10 + (c - '0'); // a number can have several digits
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) { // an operator, or the end
if (op == '+') terms.push(num);
else if (op == '-') terms.push(-num);
else if (op == '*') terms.push(terms.pop() * num);
else terms.push(terms.pop() / num); // truncates toward zero
op = c;
num = 0;
}
}
int sum = 0;
for (int t : terms) sum += t;
return sum;
}
function calculate(s) {
const terms = []; // the numbers to add up at the end
let num = 0;
let op = "+"; // the operator before the number being read
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c >= "0" && c <= "9") num = num * 10 + Number(c); // a number can have several digits
if ("+-*/".includes(c) || i === s.length - 1) { // an operator, or the end
if (op === "+") terms.push(num);
else if (op === "-") terms.push(-num);
else if (op === "*") terms.push(terms.pop() * num);
else terms.push(Math.trunc(terms.pop() / num)); // truncate toward zero
op = c;
num = 0;
}
}
return terms.reduce((a, b) => a + b, 0);
}
Each printed 7 1 5 12 for 3+2*2, 3/2, 3+5 / 2, 14-3*4/5, with spaces where LeetCode's examples have them. O(n) time and O(n) space for the terms; keeping only the running sum and the last term brings the space to O(1).
Spotting it, and when it breaks
The clues. An expression in a string; operators with different precedence; "evaluate", "calculator", "parse"; a notation named prefix, postfix or Polish. Any time a step has to wait for something that comes later, a stack holds it.
The near-misses. Brackets with only + and - (Basic Calculator) need a stack of signs, not of operators. A - that is a sign, as in -3 + 5 or 2 * -3, has to be told apart from subtraction while reading the string. Full languages use a recursive descent parser, one function per precedence level, which is shunting-yard written with the call stack.
When it breaks. Deep nesting in a recursive parser runs out of call stack, as Reversing a Linked List measured; the explicit stacks here don't. Large intermediate results overflow 32-bit integers in C++ and Java: the problems here promise 32-bit values, and the C++ templates keep 64 bits anyway.
Bugs that cost a submission
Popping the operands in the wrong order.
def eval_rpn(tokens):
values = [] # operands waiting for an operator
for t in tokens:
if t in ("+", "-", "*", "/"):
a = values.pop() # the first pop taken as the left operand
b = values.pop()
if t == "+":
values.append(a + b)
elif t == "-":
values.append(a - b)
elif t == "*":
values.append(a * b)
else:
values.append(int(a / b)) # truncate toward zero; // would round down
else:
values.append(int(t)) # a number, maybe negative like "-11"
return values[0]
It returned 4 for 4 13 5 / + (5 / 13 is 0) and -2 for 5 3 -, where the answers are 6 and 2. + and * hide this bug; - and / don't.
Python's // on a negative.
def eval_rpn(tokens):
values = [] # operands waiting for an operator
for t in tokens:
if t in ("+", "-", "*", "/"):
b = values.pop() # the first pop is the right operand
a = values.pop()
if t == "+":
values.append(a + b)
elif t == "-":
values.append(a - b)
elif t == "*":
values.append(a * b)
else:
values.append(a // b) # rounds down, not toward zero
else:
values.append(int(t)) # a number, maybe negative like "-11"
return values[0]
It returned 12 for LeetCode's third example instead of 22: 6 // −132 is −1, where truncation gives 0.
^ treated as left-associative.
def infix_to_postfix(s):
rank = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], [] # ops: operators waiting for their turn
for c in s:
if c.isalnum():
out.append(c) # an operand goes straight out
elif c == "(":
ops.append(c) # a fence: nothing under it leaves until its ")"
elif c == ")":
while ops[-1] != "(":
out.append(ops.pop())
ops.pop() # drop the "("
else:
while ops and ops[-1] != "(" and rank[ops[-1]] >= rank[c]: # every equal leaves, "^" too
out.append(ops.pop())
ops.append(c)
while ops:
out.append(ops.pop())
return "".join(out)
For 2^3^2 it produced 23^2^, which is 64, against 232^^, which is 512.
Forgetting the last number. A number is applied only when the next operator arrives, so the last one needs its own check:
def calculate(s):
terms, num, op = [], 0, "+" # terms: the numbers to add up at the end
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c) # a number can have several digits
if c in "+-*/": # only at an operator
if op == "+":
terms.append(num)
elif op == "-":
terms.append(-num)
elif op == "*":
terms.append(terms.pop() * num)
else:
terms.append(int(terms.pop() / num)) # truncate toward zero
op, num = c, 0
return sum(terms)
It returned 5 for 3+2*2 and 2 for 14-3*4/5, where the answers are 7 and 12.
Converting to prefix with the postfix rule.
def infix_to_prefix(s):
rank = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], []
for c in reversed(s): # read right to left, so ")" opens and "(" closes
if c.isalnum():
out.append(c)
elif c == ")":
ops.append(c)
elif c == "(":
while ops[-1] != ")":
out.append(ops.pop())
ops.pop()
else:
while ops and ops[-1] != ")" and rank[ops[-1]] >= rank[c]: # the postfix rule, unchanged
out.append(ops.pop())
ops.append(c)
while ops:
out.append(ops.pop())
return "".join(reversed(out))
For a*(b+c)/d it gave *a/+bcd, which reads as a × ((b + c) / d). The right answer is /*a+bcd.
Check yourself
Quiz
1 / 6Multiple choice
6 2 3 * - evaluate to?Multiple choice
+ arrives and * is on top of the stack. What happens?Multiple choice
- on the stack leave when another - arrives?Multiple choice
infix_to_postfix("a^b^c") return?Multiple choice
14-3*4/5. What is on the stack just before the final sum?Multiple choice
- and /, never with + or *?Practice problems
From easier to harder:
- Evaluate Reverse Polish Notation: one stack of values.
- Postfix to Infix Conversion: a stack of sub-expressions.
- Prefix to Infix Conversion: the same, read right to left.
- Postfix to Prefix Conversion and Prefix to Postfix Conversion: the same loop, a different string built.
- Infix to Postfix Using Stack: the shunting yard.
- Infix to Prefix Conversion: the shunting yard backwards, with the equal rule flipped.
- Basic Calculator II: two levels, × and ÷ at once.
Next, Monotonic Stack: Next Greater and Smaller Elements: a stack that keeps its values in order.