Evaluate the value of an arithmetic expression in .

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

Some examples:

 

逆波兰表示法计算机，很简单 ，就是一个stack  由符号弹出计算在填入就行了 最后top上的就是计算的最后的结果。

1 class Solution { 2 public: 3     int evalRPN(vector
     
      & tokens) { 4         int sz = tokens.size(); 5         stack
      
       result; 6         int leftEval, rightEval; 7         for (int i = 0; i < sz; ++i){ 8             if (tokens[i].size() == 1 && !isdigit(tokens[i][0])){　　//处理应该注意，防止出现负数 9                 rightEval = result.top(), result.pop();10                 leftEval = result.top(), result.pop();11                 switch (tokens[i][0]){12                 case '+':13                     result.push(leftEval + rightEval);14                     break;15                 case '-':16                     result.push(leftEval - rightEval);17                     break;18                 case '*':19                     result.push(leftEval * rightEval);20                     break;21                 case '/':22                     result.push(leftEval / rightEval);23                     break;24                 default:25                     break;26                 }27             }28             else{29                 if (tokens[i][0] == '-'){30                     result.push(0 - atoi(tokens[i].substr(1, tokens[i].size() - 1).c_str()));31                     cout << result.top();32                 }33                 else34                     result.push(atoi(tokens[i].c_str()));35             }36         }37         return result.top();38     }39 };
      
     

 java版本的方法具体的和上面的差不多，但是java的栈的api用起来确确实实的要容易很多，代码如下所示：

1 public class Solution { 2     public int evalRPN(String[] tokens) { 3         Stack
     
       s = new Stack
      
       (); 4         for(int i = 0; i < tokens.length; i++){ 5             if(isDigit(tokens[i])){ 6                 s.push(Integer.parseInt(tokens[i])); 7             }else{ 8                 int right = s.pop();//分别是左右操作数 9                 int left = s.pop();10                 switch(tokens[i].charAt(0)){11                     case '+':12                         s.push(left + right);13                         break;14                     case '-':15                         s.push(left - right);16                         break;17                     case '*':18                         s.push(left * right);19                         break;20                     case '/':21                         s.push(left / right);22                         break;23                 }24             }25         }26         return s.pop();27     }28     29     public boolean isDigit(String str){30         return Character.isDigit(str.charAt(0))||(str.length() > 1);//防止出现-1这种特殊的数字也需要正确的判断31     }32 }