Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Have you met this question in a real interview?
Yes
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() < ) 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() - ;
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);
}
}
};