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, because the order of the tokens alone says what is computed first.
evalRPN receives a vector<string> named tokens 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 they are worked out: the first is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5. Integer division truncates toward zero, so 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, which is 4 + (13 / 5) = 4 + 2. The third example, {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}, gives 22. 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 its operator arrives, so it has to wait. When an operator arrives, its operands are the two most recent values that haven't been used yet. "Most recent first" is exactly what a stack gives.
- A number is pushed onto the stack.
- An operator pops two values, computes the result and pushes it back. The result takes the place of its two operands, and the next operator may use it as an operand.
Every operator turns two values into one, so a valid expression leaves exactly one value on the stack: the answer. Here is the stack for {"2", "1", "+", "3", "*"}, top on the right:
after 2: [2]
after 1: [2 1]
after +: [3]
after 3: [3 3]
after *: [9]
And for {"4", "13", "5", "/", "+"}:
after 4: [4]
after 13: [4 13]
after 5: [4 13 5]
after /: [4 2]
after +: [6]
At / the top two values are 13 and 5. The one popped first, 5, is the right operand, so the result is 13 / 5 = 2.
Step by step
- Declare the stack:
stack<int> stack, empty. It holds the values worked out so far, the most recent on top. - Loop over the tokens with
for (string& token : tokens). Each token is read once, so the loop isO(n), and the&avoids copying each string. - Test for an operator: compare
tokenwith each of the four operators using||. A negative number like"-7"starts with a minus sign, but it isn't equal to the one-character token"-", so it counts as a number. - Pop the right operand: read
stack.top()intob, then callpop().pop()returns nothing, so the value must be read first. The right operand was worked out last, so it is on top. - Pop the left operand into
athe same way. Poppingbfirst andasecond keeps the meaning:8 3 -isa - b. - Addition: if the token is
"+", pusha + b. - Subtraction:
else ifit is"-", pusha - b. The order matters here. - Multiplication:
else ifit is"*", pusha * b. - Division: the remaining operator is
"/", so a plainelsepushesa / b. - Numbers: the
elseof the outerifpushesstoi(token), which turns a string such as"-7"into theint-7. - Return
stack.top(), the one value left.
The solution in C++
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stack;
for (string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = stack.top();
stack.pop();
int a = stack.top();
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(a / b);
}
} else {
stack.push(stoi(token));
}
}
return stack.top();
}
};
The C++ details worth a closer look:
- Division truncates toward zero. Since C++11 the
/operator on two integers always truncates toward zero, which is the rule the statement asks for.-7 / 2is -3, and6 / -132is 0. A language that rounds down would give -4 for-7 / 2, but C++ doesn't. The remainder follows the same rule:-7 % 2is -1. token == "+"works on strings. Thestd::stringtype overloads==to compare contents, so comparing with a string literal is safe. Comparing twochar*pointers would not be.stoiconverts a string to anintand accepts a leading-. It throws an exception if the text isn't a number, which can't happen here because every non-operator token is an integer.- The variable named
stackhides the type namestackfor the rest of the function. That compiles because the type is already used in the declaration and isn't needed again. In code of your own, a name likevaluesavoids the confusion. top()andpop()are separate.top()returns a reference to the last element, andpop()removes it and returnsvoid. Callingtop()on an empty stack is undefined behaviour, but a valid expression never does that.- Overflow.
a + b,a * band the like areintoperations. The constraints promise every value computed along the way fits in 32 bits, so nolong longis needed here. Signed overflow would be undefined behaviour.
Complexity
Time: O(n). Each token is handled once, and a push, a pop or a comparison with a one-character string takes constant time. stoi works on a short string.
Space: O(n). In the worst case all the numbers come first, as in 2 1 3 4 + + +, and the stack holds them all before any operator runs.
Edge cases and common mistakes
- Swapped operands. Computing
b - aturns8 3 -into -5 instead of 5. The same applies to division. The value popped first is the right operand. - Treating
"-7"as an operator. Checking only the first character of the token for'-'sends negative numbers to the operator branch. Compare the whole token with"-". - A single number.
{"42"}returns 42 and{"-7"}returns -7: the loop pushes the number and the function returns the top. - Truncation.
{"-7", "2", "/"}returns -3,{"7", "-2", "/"}returns -3, and{"7", "2", "/"}returns 3. In the long example, 6 / -132 becomes 0, so10 * 0is 0 and the result is 0 + 17 + 5 = 22. - Reading
top()afterpop(). The popped value is gone, so read it into a variable first. - Using
vectoriteration indices. A range-based loop is enough here: the tokens are read in order and never revisited.
Testing
{"2", "1", "+", "3", "*"}gives 9.{"4", "13", "5", "/", "+"}gives 6.{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}gives 22.{"8", "3", "-"}gives 5, and{"3", "8", "-"}gives -5.{"-7", "2", "/"}gives -3, and{"7", "2", "/"}gives 3.{"42"}gives 42.
