Evaluate Reverse Polish Notation -- Leetcode

Question:

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

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

Some examples:

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

Answer:
[C++]

1. class Solution {  
2. public:  
3.     int evalRPN(vector<string> &tokens) {  
4.         stack<int> numeric;  
5.           
6.         for(auto& t : tokens)  
7.         {  
8.             if (isdigit(t[0]) || t.size()>1)  
9.                 numeric.push(atoi(t.c_str()));  
10.             else  
11.             {  
12.                 int o1, o2;  
13.                 o2 = numeric.top();  
14.                 numeric.pop();  
15.                 o1 = numeric.top();  
16.                 numeric.pop();  
17.                   
18.                 switch(t[0])  
19.                 {  
20.                     case '+':  
21.                         numeric.push(o1 + o2);  
22.                         break;  
23.                     case '-':  
24.                         numeric.push(o1 - o2);  
25.                         break;  
26.                     case '*':  
27.                         numeric.push(o1 * o2);  
28.                         break;  
29.                     case '/':  
30.                         numeric.push(o1 / o2);  
31.                         break;  
32.                 }  
33.             }  
34.         }  
35.           
36.         return numeric.top();  
37.     }  
38. };

[Python]

计算符号在后缀上。可以理解成二叉树的后序遍历（操作符都在父节点上）

[python] view plaincopy

1. class Solution:  
2.     # @param tokens, a list of string  
3.     # @return an integer  
4.     def operator(self,a,b,op):  
5.         a = int(a)  
6.         b = int(b)  
7.         if op == "+":  
8.             return int(a+b)  
9.         elif op  == "-":  
10.             return int(a-b)  
11.         elif op == "*":  
12.             return int(a*b)  
13.         elif op == "/":  
14.             if b == 0:  
15.                 return 0  
16.             else:  
17.                 return int(float(a)/float(b))  
18.           
19.           
20.     def evalRPN(self, tokens):  
21.         stack = []  
22.         tl = len(tokens)  
23.         op = ["+","-","*","/"]  
24.         for i in range(tl):  
25.             if tokens[i] in op:  
26.                 a = stack.pop()  
27.                 b = stack.pop()  
28.                 c = self.operator(b,a,tokens[i])  
29.                 stack.append(c)  
30.             else:  
31.                 stack.append(tokens[i])  
32.         return int(stack[0])