How do you evaluate a postfix (reverse Polish) expression?
Scan tokens left to right. Push numbers onto a stack. When you see an operator, pop two numbers, apply the operator (the first popped is the right operand), and push the result. The final stack value is the answer.
Explain it simply
In postfix notation the operator comes after its numbers: "2 1 +" means 2 + 1. There are no brackets and no precedence rules to worry about, which is why calculators and compilers like it.
A stack handles it naturally. Numbers wait on the stack. The moment an operator arrives, it uses the two most recent numbers, which are exactly the top two items.
Example
function evalPostfix(tokens) {
const stack = [];
for (const t of tokens) {
if (["+", "-", "*", "/"].includes(t)) {
const b = stack.pop();
const a = stack.pop();
if (t === "+") stack.push(a + b);
else if (t === "-") stack.push(a - b);
else if (t === "*") stack.push(a * b);
else stack.push(Math.trunc(a / b));
} else {
stack.push(Number(t));
}
}
return stack.pop();
}
console.log(evalPostfix(["2", "1", "+", "3", "*"])); // Output: 9
console.log(evalPostfix(["4", "13", "5", "/", "+"])); // Output: 6Complexity
Time O(n), space O(n).
What to say in the interview
"I push operands on a stack and, at each operator, pop the top two values, apply the operator and push the result. Order matters: the first value popped is the right-hand operand. It is O(n) time and O(n) space."
Common mistakes
- Reversing the operands, which gives wrong answers for subtraction and division.
- Using floating-point division when the problem asks for integer division.