Problem overview
In reverse Polish notation (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, because the order of the tokens alone says what to compute first.
The method evalRPN(tokens) receives an array of strings holding 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: the first 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 result is 9, because (2 + 1) * 3 = 9. For ["4", "13", "5", "/", "+"] it is 6, because 13 / 5 is 2.6, truncated to 2, and 4 + 2 = 6.
The budget is 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 yet, so it waits. An operator needs the two values that came right before it, and those are the two most recent values not used yet: exactly the two on top of a stack. So the plan is:
- for a number, push it;
- for an operator, pop two values, combine them, and push the result.
The result takes the place of its two operands, so the next operator can use it as one of its own. Each operator turns two values into one, so a valid expression leaves exactly one value on the stack at the end, and that is the answer.
Here is the first example, with the stack after each token:
| token | stack after it |
|---|---|
"2" | [2] |
"1" | [2, 1] |
"+" | [3] |
"3" | [3, 3] |
"*" | [9] |
Every token is handled once with constant work, so the time is O(n). In the worst case, such as many numbers followed by many operators, the stack holds about half the tokens, so the space is O(n).
Step by step
- Create the stack:
const stack: number[] = []. An array'spushandpopboth work at its end, so the end is the top.constonly means thatstackalways names the same array; the array can still change. - Loop over the tokens with
for (const token of tokens), from left to right. - Test for an operator by comparing
tokenwith"+","-","*"and"/", joined with||. A negative number such as"-7"starts with a minus sign too, but it isn't equal to the one-character token"-". - Pop the right operand first into
b: it was worked out last, so it is on top. - Pop the left operand second into
a. This order keeps the meaning:8 3 -isa - b, that is 8 - 3. - For
"+", pusha + b. - For
"-", pusha - b. The order matters here. - For
"*", pusha * b. - For
"/", pushMath.trunc(a / b). Anumberkeeps its fraction, so-7 / 2is-3.5, andMath.truncdrops the fraction, giving -3 as the problem asks. - For anything else, the token is a number: push
parseInt(token), which turns a string such as"-7"into the number -7. - After the loop, return the one value left:
stack.pop().
The solution in TypeScript
class Solution {
evalRPN(tokens: string[]): number {
const stack: number[] = [];
for (const token of tokens) {
if (token === "+" || token === "-" || token === "*" || token === "/") {
const b: number = stack.pop();
const a: number = 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();
}
}
TypeScript details worth knowing
Division. TypeScript has no integer division: / always produces a floating-point number. The two common rounding functions differ for negative results. Math.floor(-7 / 2) is -4 (toward negative infinity), while Math.trunc(-7 / 2) is -3 (toward zero). The problem wants truncation, so it is Math.trunc. For positive results the two agree.
Strings versus numbers. The tokens are strings, so "2" + "1" would be the string "21". Converting with parseInt before pushing keeps the stack full of real numbers. Types such as number[] are erased when the code is compiled to JavaScript, and an annotation never converts anything, so the conversion has to be written in the code.
const declarations with a type. const b: number = stack.pop() tells the compiler that b is a number. pop() returns undefined on an empty array; for a valid expression the stack always has two values when an operator arrives, so that doesn't happen here.
Precision. Values and intermediate results fit in 32 bits, and a number holds integers exactly up to 2^53, so 2147483647 + 1 is exactly 2147483648 and 100000 * 100000 is exactly 10000000000. There is no overflow to worry about, and the two operands of a division are whole numbers, so Math.trunc is exact.
Edge cases and common mistakes
- A single number.
["42"]has no operator: the loop pushes 42 and the method returns it.["-7"]gives -7. - Operand order.
["8", "3", "-"]gives 5, while["3", "8", "-"]gives -5. Popping in the wrong order flips the result of-and/. - Negative numbers.
"-7"must be parsed as a number, not mistaken for the operator"-". Comparing with===against the whole token avoids the confusion. - Division rounding.
["7", "2", "/"]gives 3 and["-7", "2", "/"]gives -3. UsingMath.floorwould give -4 for the second one. - A result of zero. When a truncated division gives a result of zero from a negative fraction, the value is
-0: for example["1", "-2", "/"]returns-0, whichconsole.logprints as-0. It still satisfies=== 0and prints as0throughStringorJSON.stringify, and adding it to another number, as in the third example, gives an ordinary result. - Forgetting
parseInt. Pushing the string itself makes+join text instead of adding numbers.
Testing
The lesson's code gives these results:
["2","1","+","3","*"] -> 9
["4","13","5","/","+"] -> 6
["10","6","9","3","+","-11","*","/","*","17","+","5","+"] -> 22
["8","3","-"] -> 5
["3","8","-"] -> -5
["7","2","/"] -> 3
["-7","2","/"] -> -3
["42"] -> 42
