Problem overview
In reverse Polish notation (postfix), 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 says what is computed first.
eval_rpn receives tokens: Vec<String>, a valid expression, and returns its value as an i32. A 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 they 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.
For ["4", "13", "5", "/", "+"] the answer is 6: 13 / 5 is 2.6, truncated to 2, and 4 + 2 is 6.
Approach: a stack of values
Read the tokens from left to right. A number cannot be used until an operator asks for it, so keep it and wait. When an operator arrives, its operands are the two most recent values that are not used yet. That is exactly the top two items of a stack: take them off, compute, and put the result back, where it may become an operand of a later operator.
Every operator turns two values into one, so after a valid expression the stack holds exactly one value, the answer. Each token is handled once with constant work, so the time is O(n).
Here is the stack after each token of 4 13 5 / +:
4 -> [4]
13 -> [4, 13]
5 -> [4, 13, 5]
/ -> [4, 2]
+ -> [6]The / removes 13 and 5 and puts back 2, then + removes 4 and 2 and puts back 6. For 2 1 + 3 * the stack goes [2], [2, 1], [3], [3, 3], [9].
Step by step
- Declare the stack:
let mut stack: Vec<i32> = Vec::new();. A vector'spushandpopboth work at its end, so the end is the top of the stack. - Loop over each
tokenintokens, once, from left to right. - Test for an operator:
token == "+" || token == "-" || token == "*" || token == "/". A negative number such as"-7"starts with a minus sign, but it is not equal to the one-character token"-", so it is not mistaken for an operator. AStringcan be compared with a string literal using==. - Pop the right operand first:
let b = stack.pop().unwrap();. It was worked out last, so it is on top.pop()returns anOption, andunwrap()takes the value out. - Pop the left operand:
let a = stack.pop().unwrap();. Poppingbbeforeakeeps the order the expression means:8 3 -isa - b. - Apply the operator with an
ifchain:"+"pushesa + b,"-"pushesa - b,"*"pushesa * b, and the lastelse, for"/", pushesa / b. The result takes the place of its two operands. - Handle a number in the outer
else:stack.push(token.parse().unwrap());.parsereturns aResult, andunwrap()takes the number out. The stack's type,Vec<i32>, tellsparseto produce ani32. - Return the last value:
stack.pop().unwrap()on its own line, with no semicolon, so it is the function's value.
The solution in Rust
impl Solution {
fn eval_rpn(tokens: Vec<String>) -> i32 {
let mut stack: Vec<i32> = Vec::new();
for token in tokens {
if token == "+" || token == "-" || token == "*" || token == "/" {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
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(token.parse().unwrap());
}
}
stack.pop().unwrap()
}
}
The Rust details worth a closer look:
- Integer division. Rust's
/on two integers truncates toward zero, which is the rule the problem asks for:-7 / 2is -3 and7 / -2is -3. Rounding down (floor division) would give -4, anddiv_euclidgives -4 as well, so neither fits here. Stringagainst&str.tokenis aStringand"+"is a&str. The standard library lets you compare the two with==.parse()and type inference.token.parse()could produce any number type. Rust picksi32because the vector it is pushed onto holdsi32. It accepts a leading minus sign, so"-7".parse::<i32>()isOk(-7).unwrap(). It panics onNoneorErr. For a valid expression, the stack always has two values when an operator arrives, and every other token is a valid integer, so it never fires. For an invalid one such as["1", "+"]it would panic withcalled `Option::unwrap()` on a `None` value.- Ownership.
for token in tokensmoves the vector into the loop, so eachtokenis an ownedString. The function does not needtokensafterwards. - The last line.
stack.pop().unwrap()has no semicolon, so its value is returned. - Overflow. The lesson's builds use
-O, wherei32overflow wraps silently, and a debug build panics. The constraints guarantee that every value fits in ani32, so it does not come up.
Complexity
Time: O(n). Each of the n tokens is read once, and a push, a pop or a parse takes constant time (a number has a bounded number of digits).
Space: O(n). In the worst case, for example when all the numbers come before all the operators, the stack holds about half of the tokens at once.
Edge cases and common mistakes
- Operand order. For
8 3 -the answer is 5. Using the first popped value as the left operand computes3 - 8and gives -5. The same applies to/. - Negative numbers.
"-7"is a number. Checking whether a token starts with-would treat it as an operator. Compare the whole token with"-"instead. - Truncating division.
-7 2 /gives -3, and7 2 /gives 3. In the longer example,6 / -132truncates to 0, not -1. - A single number.
["42"]has no operator. The number is pushed and then popped as the result, so the answer is 42.["-7"]gives -7. - The result goes back on the stack. Forgetting to push the result of an operator leaves too few values for the next one.
- Using
pop()withoutunwrap().pop()returns anOption<i32>, which cannot be added to a number. The program does not compile until the value is taken out.
Testing
["2", "1", "+", "3", "*"]gives9.["4", "13", "5", "/", "+"]gives6.["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]gives22.["8", "3", "-"]gives5.["-7", "2", "/"]gives-3,["7", "2", "/"]gives3and["7", "-2", "/"]gives-3.["42"]gives42.
