150. Evaluate Reverse Polish Notation

  • 26.4%

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

1
2
3
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

https://discuss.leetcode.com/topic/1323/6-132-0-or-1

6/(-132)= 0 or -1

when I test [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/“,””,”17”,”+”,”5”,”+”],

in this program, the result I got is 12, I think I am right. Because when I calculate 6/(-132) = -1, not 0, so i think the result is 12 not 22.


Accepted C++ recursive solution (56 ms) with explanation. Simplest possible?

Algorithm:

pop string from the end of the vector

if it’s number, just return it

if it’s operation, call function recursively for 2nd operand and 1st

1
2
3
4
5
6
7
8
9
10
11
12
13
int evalRPN(vector<string> &n) {
string s = n.back(); n.pop_back();
if ( s== "" || s=="/" || s=="+" || s == "-" ){
int r2 = evalRPN(n);
int r1 = evalRPN(n);
if ( s=="") return r1*r2;
if ( s=="/") return r1/r2;
if ( s=="+") return r1+r2;
if ( s=="-") return r1-r2;
}
else
return atoi(s.c_str());
}

https://discuss.leetcode.com/topic/38178/fancy-c-lambda-expression-solution

Fancy C++ lambda expression solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int evalRPN(vector<string>& tokens) {
unordered_map<string, function<int (int, int) > > map = {
{ "+" , [] (int a, int b) { return a + b; } },
{ "-" , [] (int a, int b) { return a - b; } },
{ "*" , [] (int a, int b) { return a * b; } },
{ "/" , [] (int a, int b) { return a / b; } }
};
std::stack<int> stack;
for (string& s : tokens) {
if (!map.count(s)) {
stack.push(stoi(s));
} else {
int op1 = stack.top();
stack.pop();
int op2 = stack.top();
stack.pop();
stack.push(map[s](op2, op1));
}
}
return stack.top();
}
};

https://discuss.leetcode.com/topic/21965/python-solution-with-comments-don-t-use-eval-function

Python solution with comments (don’t use eval() function).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def evalRPN(self, tokens):
stack = []
for t in tokens:
if t not in ["+", "-", "*", "/"]:
stack.append(int(t))
else:
r, l = stack.pop(), stack.pop()
if t == "+":
stack.append(l+r)
elif t == "-":
stack.append(l-r)
elif t == "*":
stack.append(l*r)
else:
# here take care of the case like "1/-22",
# in Python 2.x, it returns -1, while in
# Leetcode it should return 0
if l*r < 0 and l % r != 0:
stack.append(l/r+1)
else:
stack.append(l/r)
return stack.pop()

https://discuss.leetcode.com/topic/15344/a-simple-python-solution-o-n-72ms

A simple Python solution - O(n) 72ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
# @param {string[]} tokens
# @return {integer}
def __init__(self):
self.operators = {
'+': lambda y, x: x + y,
'-': lambda y, x: x - y,
'*': lambda y, x: x * y,
'/': lambda y, x: int(operator.truediv(x, y))
}

def evalRPN(self, tokens):
if not tokens:
return 0

stack = []

for token in tokens:
if token in self.operators:
stack.append(self.operators[token](stack.pop(), stack.pop()))
else:
stack.append(int(token))

return stack[0]
谢谢你,可爱的朋友。