Problem overview
The method EvalRPN receives a string[] called tokens that holds a valid expression in reverse Polish notation (postfix), and returns its value as an int. In this 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.
Each token is one of the operators "+", "-", "*", "/", 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 is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5. Division truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.
The tokens {"2","1","+","3","*"} give 9, because (2 + 1) * 3 = 9. The tokens {"4","13","5","/","+"} give 6, because 13 / 5 is 2 and 4 + 2 = 6.
Approach: a stack of values worked out so far
Read the tokens from left to right and keep a stack: a collection where the last item added is the first one removed. When a token is a number, push it. When it is an operator, its two operands are the two most recent values that haven't been used yet, and those are exactly the top two items on the stack. Pop them, apply the operator, and push the result, which takes the place of its operands for the next operator to use.
Every operator turns two values into one, and every number adds one, so a valid expression ends with exactly one value on the stack: the answer.
For {"4","13","5","/","+"}: push 4, push 13, push 5. The stack is now 4, 13, 5 with 5 on top. The / pops 5 and then 13 and pushes 13 / 5 = 2, so the stack is 4, 2. The + pops 2 and 4 and pushes 6. The last pop returns 6.
Step by step
- Create the stack: a
Stack<int>namedstack. It holds the values so far, the most recent on top. - Loop over the tokens with
foreach (string token in tokens). Each token is read once, so the whole evaluation is linear. - Test for an operator: compare
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"-", so it is treated as a number. - Pop the right operand first:
int b = stack.Pop(). It was worked out last, so it is on top. - Pop the left operand second:
int a = stack.Pop(). This order keeps the meaning: for8 3 -,ais 8 andbis 3, soa - bis 5. - Apply the operator with an
if/else ifchain and push the result:a + b,a - b,a * b, and, in the lastelse,a / b. For-and/the order matters. - Otherwise it's a number: an
elseon the firstifpushesint.Parse(token). It waits on the stack until an operator needs it. - Return the answer: after the loop,
stack.Pop()gives the single value left.
The solution in C#
class Solution {
public int EvalRPN(string[] tokens) {
Stack<int> stack = new Stack<int>();
foreach (string token in tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = stack.Pop();
int 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(a / b);
}
} else {
stack.Push(int.Parse(token));
}
}
return stack.Pop();
}
}
The C# details worth knowing:
- Integer division truncates toward zero. In C#,
-7 / 2is-3, not-4, and7 / -2is also-3. That matches the lesson's rule with no extra code. For the sample6 / -132, the result is 0. - String comparison with
==. In C#,==on two strings compares their contents, sotoken == "+"does what it looks like. int.Parseand signs.int.Parse("-7")returns -7. A bare"+"is not a number:int.Parse("+")throwsFormatException, which the code never reaches because operators are handled first.Popon an empty stack throwsInvalidOperationException. For a valid expression that can't happen. For an invalid one such as{"+"}, it does.intoverflow wraps silently.a * bwith values that don't fit in 32 bits would wrap. The lesson guarantees that every value computed along the way fits, sointis enough. One more rare case:int.MinValue / -1throwsOverflowException, because the true result doesn't fit.- Pop order.
Stack<T>.Pop()removes and returns the top item, so the firstPopreturns the most recent value: that is the right operand.
Complexity
Time: O(n). Each of the n tokens is read once, and each one does a constant number of stack operations, comparisons and a parse. Push and Pop take constant time.
Space: O(n). In the worst case all the numbers come first and are on the stack at the same time, for example 1 2 3 4 + + +, where four values wait before the first operator. The stack never holds more than the number of tokens.
Edge cases and common mistakes
- A single number.
{"3"}gives 3 and{"-7"}gives -7: the one value is pushed and popped. - Operand order.
{"8","3","-"}gives 5. Poppingabeforebwould compute 3 - 8 = -5. - Division of negatives.
{"-7","2","/"}gives -3,{"7","-2","/"}gives -3 and{"7","2","/"}gives 3. UsingMath.Flooron a floating-point division would give -4 for the first. - Negative numbers mistaken for operators. Testing
token[0] == '-'would treat"-7"as the minus operator. Comparing the whole token avoids it. - Quotients that round to zero.
{"6","-132","/"}gives 0, since 6 / -132 truncates toward zero. - Popping in the wrong order for
/.13 5 /would compute 5 / 13, which is 0, instead of 2.
Testing
{"2","1","+","3","*"}gives9.{"4","13","5","/","+"}gives6.{"10","6","9","3","+","-11","*","/","*","17","+","5","+"}gives22.{"8","3","-"}gives5, and{"-7"}gives-7.{"-7","2","/"}gives-3, and{"7","-2","/"}gives-3.
