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
思路：四则运算，利用stack。这也是IDG资本的一道笔试题。
class Solution {
public:
int strToInt(string str) {
int res = 0,j=1,i;
for(i=str.length()-1; i>=0&&str[i]-'0'>=0&&str[i]-'0'<=9; --i) {
res += (str[i]-'0')*j;
j *= 10;
}
if(i>=0&&str[i]=='-') {
res *= -1;
}
return res;
}
bool isNum(string str) {
if(str[0]=='-'||str[0]=='+') {
if(str.length()>1) {
return true;
}
else {
return false;
}
}
if(str=="*" ||str=="/") {
return false;
}
return true;
}
int evalRPN(vector<string> &tokens) {
int res = 0;
if (tokens.empty()) {
return res;
}
stack<int> S;
int a,b;
int i;
for(i=0; i<tokens.size(); ++i) {
if (isNum(tokens[i])) {
S.push(strToInt(tokens[i]));
continue;
}
a = S.top();
S.pop();
b = S.top();
S.pop();
if(tokens[i] == "+") {
S.push(a+b);
}
else if(tokens[i] == "-") {
S.push(b-a);
}
else if(tokens[i] == "*") {
S.push(a*b);
}
else if(tokens[i] == "/") {
S.push(b/a);
}
}
return S.top();
}
};