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
题意：求逆波兰表达式的值
思路：首先说明什么是逆波兰表达式操作符紧邻于对应的（最后一个）操作数之后，比如“1 2 +”。
像括号匹配和求逆波兰表达式是栈典型的应用。该题的思路是：将遍历字符串，将数字型字符压入栈中，遇到操作符，从栈中取出操作符计算所需的数位，进行计算，并将计算结果压入栈中，以便参加后续的计算。代码如下：
1 class Solution { 2 public: 3 int evalRPN(vector<string> &tokens) 4 { 5 if(tokens.empty()) return 0; 6 7 int len=tokens.size(); 8 stack<int> stk; 9 for(int i=0;i<len;++i) 10 { 11 string s=tokens[i]; 12 if(s=="+"||s=="-"||s=="*"||s=="/") 13 { 14 if(stk.size()<2) 15 return 0; 16 int num1=stk.top(); 17 stk.pop(); 18 int num2=stk.top(); 19 stk.pop(); 20 21 int res=0; 22 if(s=="+") 23 res=num1+num2; 24 if(s=="-") 25 res=num2-num1; 26 if(s=="*") 27 res=num2*num1; 28 if(s=="/") 29 res=num2/num1; 30 stk.push(res); 31 } 32 else 33 { 34 stk.push(atoi(s.c_str())); // 35 } 36 } 37 return stk.top(); 38 } 39 };
[Leetcode] evaluate reverse polish notation 计算逆波兰表达式
原文：http://www.cnblogs.com/love-yh/p/7192062.html