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
思路：
题目的意思是表达式总是先给出两个操作数，然后再给出对应的操作符。当给出一个这样的表达式后，求出表达式对应的值。
难点是后面操作符的操作数也是表达式。解决方法是用一个栈nums来保存所有没有用过的操作数，当遇到操作符时，栈最上面的两个数字就是操作符对应的操作数。最先遇到的操作符他的操作数一定没有嵌套表达式，所以可以得到值，当运算得到新的数字后，压入栈，作为下一个操作符的操作数。
我的代码：数字与字符串转换的时候比较丑。
int evalRPN2(vector<string>& tokens)
{
if(tokens.size() == )
return atoi(tokens[].c_str());
vector<string> nums;
for(int i = ; i < tokens.size(); i++)
{
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
{
string sPreNum, sPostNum, sOp;
int preNum, postNum, tmp;
sPostNum = nums.back();
nums.pop_back();
sPreNum = nums.back();
nums.pop_back();
preNum = atoi(sPreNum.c_str());
postNum = atoi(sPostNum.c_str());
sOp = tokens[i];
switch(sOp[])
{
case '+':
tmp = preNum + postNum; break;
case '-':
tmp = preNum - postNum; break;
case '*':
tmp = preNum * postNum; break;
case '/':
tmp = preNum / postNum; break;
default:
break;
}
char ctmp[];
sprintf(ctmp, "%d", tmp);
nums.push_back(ctmp);
}
else
{
nums.push_back(tokens[i]);
}
}
return atoi(nums[].c_str());
}
大神用递归的答案，相对短一些，但是逻辑不好理解。
int eval_expression(vector<string>& tokens, int& pt)
{
string s = tokens[pt]; if(s == "+" || s == "-" || s == "*" || s== "/") // tokens[r] is an operator
{
pt--;
int v2 = eval_expression(tokens, pt);
pt--;
int v1 = eval_expression(tokens, pt);
if(s == "+")
return v1 + v2;
else if(s == "-")
return v1 - v2;
else if(s == "*")
return v1 * v2;
else
return v1 / v2;
}
else // tokens[r] is a number
{
return atoi(s.c_str());
}
} int evalRPN(vector<string> &tokens) {
int pt = tokens.size()-;
return eval_expression(tokens, pt);
}