Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Example
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6LeetCode上的原题，请参见我之前的博客Evaluate Reverse Polish Notation。
解法一：
class Solution { public: /** * @param tokens The Reverse Polish Notation * @return the value */ int evalRPN(vector<string>& tokens) { stack<int> s; for (auto a : tokens) { if (a == "+" || a == "-" || a == "*" || a == "/") { if (s.size() < 2) break; int t = s.top(); s.pop(); int k = s.top(); s.pop(); if (a == "+") k += t; else if (a == "-") k -= t; else if (a == "*") k *= t; else if (a == "/") k /= t; s.push(k); } else { s.push(stoi(a)); } } return s.top(); } };
解法二：
class Solution { public: /** * @param tokens The Reverse Polish Notation * @return the value */ int evalRPN(vector<string>& tokens) { int op = tokens.size() - 1; return helper(tokens, op); } int helper(vector<string>& tokens, int& op) { string s = tokens[op]; if (s == "+" || s == "-" || s == "*" || s == "/") { int v2 = helper(tokens, --op); int v1 = helper(tokens, --op); if (s == "+") return v1 + v2; else if (s == "-") return v1 - v2; else if (s == "*") return v1 * v2; else return v1 / v2; } else { return stoi(s); } } };
本文转自博客园Grandyang的博客，原文链接：计算逆波兰表达式[LintCode] Evaluate Reverse Polish Notation ，如需转载请自行联系原博主。
