Medium difficulty · Algorithm · Topics: stack, expression, postfix
Postfix notation (reverse Polish notation) writes the operator after its operands: 2 3 + means 2 + 3. It needs no parentheses and no precedence rules. A stack evaluates a postfix expression in a single left-to-right pass: operands are pushed, and each operator pops its two operands and pushes the result.
When you read 2 3 1 * + 9 - from left to right, an operator always applies to the two most recent results. "Most recent" is exactly what a stack gives you. Numbers wait on the stack until an operator arrives, then collapse into one value that waits in turn.
The invariant: after processing token i, the stack holds the values of all complete sub-expressions seen so far, in order. For a valid expression, exactly one value remains at the end.
stack and walk the tokens with i = 0 .. n - 1.tokens[i] is a number, convert it and push it.right first and then left (order matters for - and /).left operator right and push the result.Test case 0: tokens = ["2", "3", "1", "*", "+", "9", "-"], which is 2 + 3 * 1 - 9.
| i | token | Action | Stack (bottom to top) |
|---|---|---|---|
| 0 | 2 | push | [2] |
| 1 | 3 | push | [2, 3] |
| 2 | 1 | push | [2, 3, 1] |
| 3 | * | 3 * 1 = 3 | [2, 3] |
| 4 | + | 2 + 3 = 5 | [5] |
| 5 | 9 | push | [5, 9] |
| 6 | - | 5 - 9 = -4 | [-4] |
The answer is the last remaining value, -4.
| Case | Time | Why |
|---|---|---|
| Best / Average / Worst | O(n) | each token is pushed and popped at most once |
| Space | O(n) | the stack can hold up to about n / 2 operands (for example 1 2 3 4 + + +) |
- and / the first pop is the right operand, not the left."3" + "1" concatenates. Convert operands with Number.Math.trunc rounds toward zero (-7 / 2 gives -3), while Math.floor would give -4.undefined.tokens is shown as bars/cells with the pointer i moving one step to the right per token.stack array grows on operands and shrinks by one on every operator (two pops, one push).left and right to see the order the operands came off the stack.stack.pop() returns the answer.Input: tokens = ["2", "3", "1", "*", "+", "9", "-"]
Output: -4
class Solution {
evaluatePostfix(tokens) {
const stack = [];
for (let i = 0; i < tokens.length; i++) {
const token = tokens[i];
if (this.isOperator(token)) {
// The right operand was pushed last, so it is popped first.
const right = stack.pop();
const left = stack.pop();
stack.push(this.apply(token, left, right));
} else {
stack.push(Number(token)); // operand: just remember it
}
}
return stack.pop(); // the single value left is the answer
}
isOperator(token) {
return token === "+" || token === "-" || token === "*" || token === "/";
}
apply(operator, left, right) {
if (operator === "+") return left + right;
if (operator === "-") return left - right;
if (operator === "*") return left * right;
return Math.trunc(left / right); // integer division
}
}