[LeetCode] Evaluate Reverse Polish Notation

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问题。逐一扫描每个token，如果是数字，则push入stack，如果是运算符，则从stack中pop出两个数字，进行运算，将结果push回stack。最后留在stack里的数即为最终结果。

以题中例子说明

exp:     2    1      +    3      *

stack:   2    2,1   3    3,3   9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { public: int evalRPN(vector<string> &tokens) { stack<int> s; for(int i=0; i<tokens.size(); i++) { if(isOp(tokens[i])) { int y = s.top(); s.pop(); int x = s.top(); s.pop(); s.push(evaluate(x, y, tokens[i])); } else { s.push(stoi(tokens[i], nullptr, 10)); //s.push(atoi(tokens[i].c_str())); } } return s.top(); } bool isOp(string s) { if(s=="+" || s=="-" || s=="*" || s=="/") return true; return false; } int evaluate(int x, int y, string op) { if(op=="+") return x+y; else if(op=="-") return x-y; else if(op=="*") return x*y; else if(op=="/") return x/y; } };

总结：

1. 易犯的错误是将参与运算的两个数的顺序搞反。要计算 x op y，y是后压入的数，所以也是先被pop出来的数。第二次pop的时候才得到x的值。

2. 要注意stoi和atoi两个库函数的不同用法。