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
分析：
/*-----Reverse Polish Notation（逆波兰表达式），又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> cache;
for(int i = 0 ; i < tokens.size(); i++){
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
int num2 = cache.top();
cache.pop();
int num1 = cache.top();
cache.pop();
cache.push(calculate(num1, num2, tokens[i]));
}
else{
cache.push(str2int(tokens[i]));
}
}
return cache.top();
}
int str2int(string s){
int result=0;
int base=1;
for(int i = s.size()-1;i>=0;i--){
if(s[i] == ‘-‘ && i == 0){
result *= -1;
}
else if(s[i] >= ‘0‘ && s[i] <= ‘9‘){
result += base * (s[i] - ‘0‘);
base *= 10;
}
}
return result;
}
int calculate(int num1, int num2, string op){
if(op == "+"){
return num1 + num2;
}
else if(op == "-"){
return num1 - num2;
}
else if(op == "*"){
return num1 * num2;
}else if(op == "/"){
return num1 / num2;
}
}
};
其他方法：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (auto t : tokens) { //自动类型推断
if (t == "+" || t == "-" || t == "*" || t == "/") {
int y = s.top(); s.pop();
int x = s.top(); s.pop();
int z = 0;
switch (t.front()) {
case ‘+‘ :
z = x + y;
break;
case ‘-‘ :
z = x - y;
break;
case ‘*‘ :
z = x * y;
break;
case ‘/‘ :
z = x / y;
break;
}
s.push(z);
} else {
s.push(stoi(t)); //字符串怎么转数值用函数 std::stoi（）函数原型：
//int stoi (const string& str, size_t* idx = 0, int base = 10); base 是进制
}
}
return s.top();
}
};
使用is_operator更简洁：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stn;
for(auto s:tokens) {
if(s.size()>1 || isdigit(s[0])) stn.push(stoi(s));
else {
auto x2=stn.top(); stn.pop();
auto x1=stn.top(); stn.pop();
switch(s[0]) {
case ‘+‘: x1+=x2; break;
case ‘-‘: x1-=x2; break;
case ‘*‘: x1*=x2; break;
case ‘/‘: x1/=x2; break;
}
stn.push(x1);
}
}
return stn.top();
}
};
Evaluate Reverse Polish Notation（堆栈）
原文：http://www.cnblogs.com/carsonzhu/p/4844909.html