Code & Func

因为最近在总结 LeetCode 中 Stack 标签下做过的题目，然后这道题做了但是没有写题解，所以补充一下。

一道Medium的题目，但是数据结构课上提到栈时，都会举这个例子才对，所以这道题挺简单的。

因为输入的已经是解析好的token了，所以不用额外的做 parse 的工作。我们只需要用一个栈来保存操作树即可。

当遇到一个操作数时，就压入栈中。
当遇到一个操作符时，就弹出两个操作数，然后根据操作符对这两个操作数进行操作，并将结果压入栈中。

由于题目保证了输入一定是正确的，所以很多判断都可以省略掉。然后又一个需要主要的就是栈是后进先出的，所以操作数的顺序不要弄反了就好了。

1
bool isOp(const string &s) {
2
  return s.size() == 1 && (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/');
3
}
4
int calc(int a, char op, int b) {
5
  switch(op) {
6
    case '+': return a + b;
7
    case '-': return a - b;
8
    case '*': return a * b;
9
    case '/': return a / b;
10
  }
11
  return -1;
12
}
13
int evalRPN(vector<string>& tokens) {
14
  stack<int> st;
15
  for(auto &s: tokens) {
10 collapsed lines
16
    if (!isOp(s)) {
17
      st.push(atoi(s.c_str()));
18
    } else {
19
      int b = st.top(); st.pop();
20
      int a = st.top(); st.pop();
21
      st.push(calc(a, s[0], b));
22
    }  // else return -1;
23
  }
24
  return st.top();
25
}