给出逆波兰表达式字符List,求算式结果,包含加减乘除,除法
truncate toward zero
简单栈操作,遇到数字就压入栈,遇到运算符就用栈顶的两个数字做运算再压入栈
Python版
1 #150
2 #Runtime: 128 ms
3 #Memory Usage: 15.5 MB
4
5 class Solution(object):
6 def cal(self, a, b, op):
7 if op == '+':
8 return a + b
9 if op == '-':
10 return a - b
11 if op == '*':
12 return a * b
13 if op == '/':
14 return math.trunc(float(a) / float(b))
15
16 def evalRPN(self, tokens):
17 """
18 :type tokens: List[str]
19 :rtype: int
20 """
21 stk = []
22 for i in tokens:
23 if i in "*+/-":
24 t = self.cal(stk[-2], stk[-1], i)
25 stk.pop()
26 stk.pop()
27 stk.append(t)
28 else:
29 stk.append(int(i))
30 return stk[0]
CPP版
1 //150
2 //Runtime: 24 ms
3
4 class Solution {
5 public:
6 int evalRPN(vector<string> &tokens) {
7 int stk[1010], k = 0;
8 for(int i = 0; i < tokens.size(); ++i) {
9 if(tokens[i] == "+") {
10 int a = stk[k - 1], b = stk[k - 2];
11 k -= 2;
12 stk[k++] = a + b;
13 }
14 else if(tokens[i] == "-") {
15 int a = stk[k - 1], b = stk[k - 2];
16 k -= 2;
17 stk[k++] = b - a;
18 }
19 else if(tokens[i] == "*") {
20 int a = stk[k - 1], b = stk[k - 2];
21 k -= 2;
22 stk[k++] = b * a;
23 }
24 else if(tokens[i] == "/") {
25 int a = stk[k - 1], b = stk[k - 2];
26 k -= 2;
27 stk[k++] = b / a;
28 }
29 else {
30 stk[k++] = atoi(tokens[i].c_str());
31 }
32 }
33 return stk[0];
34 }
35 };