Medium difficulty · Algorithm · Topics: stack, expression, prefix
Prefix notation (Polish notation) writes the operator before its operands: + 2 3 means 2 + 3. Like postfix, it needs no parentheses. A stack evaluates it with one pass from right to left: operands are pushed, and each operator pops two operands and pushes the result.
In - + 2 * 3 1 9 every operator is followed by the expressions it applies to. If we read the tokens backwards, the operands of an operator are always seen before the operator itself, which is the same situation as in postfix. So the only change from postfix evaluation is the scan direction, and the operand order.
The invariant: after processing token i (moving leftwards), the stack holds the values of the complete sub-expressions that start at index i or later.
stack and walk the tokens with i = n - 1 down to 0.tokens[i] is a number, convert it and push it.left first and then right. Scanning backwards reverses the order compared with postfix.left operator right and push the result.i = 0, the last remaining value is the answer.Test case 0: tokens = ["-", "+", "2", "*", "3", "1", "9"], which is (2 + 3 * 1) - 9.
| i | token | Action | Stack (bottom to top) |
|---|---|---|---|
| 6 | 9 | push | [9] |
| 5 | 1 | push | [9, 1] |
| 4 | 3 | push | [9, 1, 3] |
| 3 | * | left = 3, right = 1: 3 * 1 = 3 | [9, 3] |
| 2 | 2 | push | [9, 3, 2] |
| 1 | + | left = 2, right = 3: 2 + 3 = 5 | [9, 5] |
| 0 | - | left = 5, right = 9: 5 - 9 = -4 | [-4] |
| Case | Time | Why |
|---|---|---|
| Best / Average / Worst | O(n) | one pass, each token pushed and popped at most once |
| Space | O(n) | the stack holds pending operands |
(+ 1 2) is essentially prefix).- and /.Number() on operand tokens, which are strings.Math.floor instead of Math.trunc for integer division of negative numbers.i moves from the end of tokens towards the start.stack; whenever the pointer lands on an operator, two values leave and one result arrives.left and right on each operator step to confirm which came off first.Input: tokens = ["-", "+", "2", "*", "3", "1", "9"]
Output: -4
class Solution {
evaluatePrefix(tokens) {
const stack = [];
// Scan right to left so that operands are on the stack before their operator.
for (let i = tokens.length - 1; i >= 0; i--) {
const token = tokens[i];
if (this.isOperator(token)) {
// The left operand was pushed last, so it is popped first.
const left = stack.pop();
const right = 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
}
}