Code & Fun

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

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

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

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

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

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
bool isOp(const string &s) {
return s.size() == 1 && (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/');
}
int calc(int a, char op, int b) {
switch(op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return -1;
}
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto &s: tokens) {
if (!isOp(s)) {
st.push(atoi(s.c_str()));
} else {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
st.push(calc(a, s[0], b));
} // else return -1;
}
return st.top();
}

本文首发于Code & Fun