Problem overview
In reverse Polish notation, also called postfix notation, an operator comes after its two operands. 3 + 4 is written 3 4 +, and (1 + 2) * 3 is written 1 2 + 3 *. No parentheses are needed: the order of the tokens alone says what is computed first.
The method evalRPN(tokens) receives an array of strings that holds a valid expression and returns its value. Each token is an operator ("+", "-", "*" or "/") or an integer such as "42" or "-7". An operator works on the two values right before it, once those are worked out. The first of them is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5, not 3 - 8. Division truncates toward zero: 7 / 2 is 3 and -7 / 2 is -3.
For ["2", "1", "+", "3", "*"] the answer is 9, which is (2 + 1) * 3. For ["4", "13", "5", "/", "+"] it is 6: 13 / 5 is 2.6, truncated to 2, and 4 + 2 is 6. The statement asks for O(n) time and O(n) extra space, where n is the number of tokens.
Approach: a stack of values
Read the tokens from left to right. A number can't be used until an operator arrives, so it waits. When an operator arrives, its operands are the two most recent values that haven't been used yet. That is exactly what a stack gives: the most recently added value is on top. The operator takes the two top values, computes, and pushes the result, which takes the place of its two operands so that a later operator can use it.
In JavaScript an array works as a stack: push adds to the end and pop removes from the end, so the end of the array is the top of the stack.
Every operator turns two values into one, and every number adds one value. In a valid expression, exactly one value is left at the end, and that value is the result. Each token is handled once, with a constant amount of work, so the whole evaluation is linear.
The order of the two pops matters. The right operand was computed last, so it is on top: pop it first as b, then pop the left operand as a. The operation is then a - b or a / b, as written.
Step by step
- Create an empty array
stack. It holds the values worked out so far, the most recent on top. - Loop over the tokens with
for...of. Each token is read once. - Test for an operator by comparing
tokenwith each of the four operator strings, joined with||. A negative number such as"-7"starts with a minus sign, but it isn't equal to the one-character token"-", so it isn't mistaken for the operator. - Pop the right operand into
b. - Pop the left operand into
a. - For
"+", pusha + b. - For
"-", pusha - b. The order matters here. - For
"*", pusha * b. - For
"/", pushMath.trunc(a / b). JavaScript's/keeps the fraction, so-7 / 2is-3.5, andMath.truncdrops the fraction to give-3. - For anything else, a number, push
parseInt(token). The value waits on the stack until an operator uses it. - After the loop, pop the one value left and return it.
The solution in JavaScript
class Solution {
evalRPN(tokens) {
let stack = [];
for (let token of tokens) {
if (token === "+" || token === "-" || token === "*" || token === "/") {
let b = stack.pop();
let a = stack.pop();
if (token === "+") {
stack.push(a + b);
} else if (token === "-") {
stack.push(a - b);
} else if (token === "*") {
stack.push(a * b);
} else {
stack.push(Math.trunc(a / b));
}
} else {
stack.push(parseInt(token));
}
}
return stack.pop();
}
}
The JavaScript details worth a closer look:
- Tokens are strings, so convert them. The input holds
"2", not2.parseInt("-7")gives the number-7. Without the conversion,+would join strings:"-7" + "2"is"-72", not -5. Math.truncagainstMath.floor.Math.trunc(-7 / 2)is-3, as the problem asks.Math.floor(-7 / 2)is-4, which rounds toward negative infinity and is wrong for negative results.- Negative zero.
Math.truncof a small negative fraction gives-0:Math.trunc(6 / -132)is-0. JavaScript has a negative zero, and-0 === 0istrue. Adding to it, as the third example does with10 * -0 + 17, gives an ordinary number. If the final answer is-0, as for["-1", "2", "/"],console.login Node prints-0although the value equals 0. ===compares strings exactly. The operator test uses===, so a token is an operator only when it is exactly that one character.pop()on an empty array. It returnsundefinedinstead of throwing. A valid expression never pops from an empty stack, but an invalid one would silently compute withundefinedand end up withNaN.- Safe size. The values and every result along the way fit in a 32-bit signed integer, and JavaScript numbers hold such integers exactly.
Tracing ["2", "1", "+", "3", "*"]
| token | action | stack afterwards |
|---|---|---|
| "2" | push 2 | [2] |
| "1" | push 1 | [2, 1] |
| "+" | pop b = 1, a = 2, push 3 | [3] |
| "3" | push 3 | [3, 3] |
| "*" | pop b = 3, a = 3, push 9 | [9] |
The loop ends, the last pop() returns 9.
Tracing ["4", "13", "5", "/", "+"]
| token | action | stack afterwards |
|---|---|---|
| "4" | push 4 | [4] |
| "13" | push 13 | [4, 13] |
| "5" | push 5 | [4, 13, 5] |
| "/" | pop b = 5, a = 13, push 2 | [4, 2] |
| "+" | pop b = 2, a = 4, push 6 | [6] |
Complexity
Time: O(n). Each token is read once. A number costs one push, and an operator costs two pops and one push, all constant-time array operations at the end of the array.
Space: O(n). In the worst case all the numbers come first and the stack holds about half of the tokens before any operator runs.
Edge cases and common mistakes
- A single number.
["42"]returns 42: the number is pushed, and the finalpop()returns it. - Operand order.
["8", "3", "-"]returns 5, and["3", "8", "-"]returns -5. Poppingabeforebwould swap the operands and reverse every subtraction and division. - Truncating division.
["7", "2", "/"]returns 3,["-7", "2", "/"]returns -3, and["7", "-2", "/"]returns -3. UsingMath.floorwould give -4 for the last two. - Division below one.
["1", "2", "/"]returns 0. - Negative numbers read as operators. Checking
token.startsWith("-")ortoken[0] === "-"would treat"-11"as an operator. Compare the whole token instead. - Forgetting
parseInt."2" + "1"is"21", so addition would join strings instead of adding numbers. Subtraction and multiplication would still convert the strings, which can hide the bug in a few test cases. - Returning the stack. The answer is the single number on top, not the array.
Testing
["2", "1", "+", "3", "*"]gives9.["4", "13", "5", "/", "+"]gives6.["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]gives22.["42"]gives42.["8", "3", "-"]gives5and["3", "8", "-"]gives-5.["7", "2", "/"]gives3and["-7", "2", "/"]gives-3.
