题目： 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
分析： 所谓的逆波兰表达式就是后缀表达式，参见我的另一篇博客：计算器：中缀表达式转后缀表达式 这道题的解法同样是利用栈，遇到数字压栈，遇到运算符栈顶两个数字进行运算，结果压栈，最后返回栈顶数字即可。
C++代码：
class Solution{public:int evalRPN(vector<string> &tokens){stack<int> operands;size_t size = tokens.size();int operandX, operandY;int result;for (size_t i = 0; i < size; i++){if (tokens[i] == “+” || tokens[i] == “-” || tokens[i] == “*” || tokens[i] == “/”){operandY = operands.top();operands.pop();operandX = operands.top();operands.pop();//C++的switch语句不支持string类型switch (tokens[i][0]){case ‘+’:result = operandX + operandY;break;case ‘-‘:result = operandX – operandY;break;case ‘*’:result = operandX * operandY;break;case ‘/’:result = operandX / operandY;break;default:break;}operands.push(result);}else{operands.push(atoi(tokens[i].c_str()));}}return operands.top();}};
C#代码：
public class Solution{(string[] tokens){Stack<int> operands = new Stack<int>();int operandX, operandY;int result = 0;foreach (string item in tokens){if (item == “+” || item == “-” || item == “*” || item == “/”){operandY = operands.Pop();operandX = operands.Pop();switch (item){case “+”:result = operandX + operandY;break;case “-“:result = operandX – operandY;break;case “*”:result = operandX * operandY;break;case “/”:result = operandX / operandY;break;default:break;}operands.Push(result);}else{operands.Push(Int32.Parse(item));}}return operands.Peek();}}
Python代码： 注意：1. Python中没有switch…case语句；2. Python中的除法和C语言中的除法不一样，所以对负数我们要做特殊处理，，得到的结果才能和C系语言的结果一样
:operands = []operators = [‘+’, ‘-‘, ‘*’, ‘/’]for i in range(len(tokens)):if tokens[i] in operators:operandy = operands.pop()operandx = operands.pop()if tokens[i] == ‘+’:result = operandx + operandyelif tokens[i] == ‘-‘:result = operandx – operandyelif tokens[i] == ‘*’:result = operandx * operandytokens[i] == ‘/’:if (operandx > 0) ^ (operandy > 0):result = -1 * (abs(operandx) / abs(operandy))else:result = operandx / operandyoperands.append(result)else:operands.append(int(tokens[i]))return operands.pop()
以诚感人者，人亦诚而应。
