题目描述：
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
使用栈的情况：
思路：
逆波兰式用到栈，遇到数字时入栈，遇到操作符则，出栈，将计算结果入栈。最终栈里有一个存放结果的元素。
方法一：
class Solution {
public:int evalRPN(vector<string> &tokens) {stack<int> ve;int val1;int val2;int size = tokens.size();for(int i = 0;i < size;i++){string s = tokens[i];if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i]== "/")//是操作数的情况{val1 = ve.top();ve.pop();val2 = ve.top();ve.pop();if(s == "+"){ve.push(val2 + val1);}else if(s == "-"){ve.push(val2 - val1);}else if(s == "*"){ve.push(val2 * val1);}else if(s == "/"){if(val1 == 0){return 0;}ve.push(val2 / val1);}}else//是数据的情况{ve.push(atoi(s.c_str()));}}return ve.top();}
};使用递归的方式：
思路：由于一个有效的逆波兰表达式的末尾必定是操作符，所以我们可以从末尾开始处理，如果遇到操作符，调用递归函数，找出前面两个数字，然后进行操作将结果返回，如果遇到的是数字直接返回即可，参见代码如下：
class Solution {
public:int evalRPN(vector<string> &tokens){int op = tokens.size() - 1;return Run(tokens,op);}int Run(vector<string> &tokens,int &op){string str = tokens[op];if(str != "+" && str != "-" && str != "*" && str != "/")//如果遇到数据情况return stoi(str);int num1 = Run(tokens,--op);//操作符的情况递归，直到返回数据int num2 = Run(tokens,--op);if(str == "+"){return num2 + num1;}else if(str == "-"){return num2 - num1;}else if(str == "*"){return num2 * num1;}return num2 / num1;}
};