后缀表达式 水题

本题没什么好说的，基本上都能轻松切掉。

class Solution {
   public:
    long long solve(string s) {
        int n = s.length();
        long long now = 0, ans = 0;
        stack<long long> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] >= '0' && s[i] <= '9') {
                now = now * 10 + (s[i] - '0');
            } else if (s[i] == '#') {
                st.push(now);
                now = 0;
            } else {
                long long x2 = st.top();
                st.pop();
                long long x1 = st.top();
                st.pop();
                if (s[i] == '+')
                    st.push(x1 + x2);
                else if (s[i] == '-')
                    st.push(x1 - x2);
                else if (s[i] == '*')
                    st.push(x1 * x2);
            }
        }
        return st.top();
    }
};

但是我们可以通过这题复习一下python：

class Solution:
    def solve(self, s):
        st = []
        num = []
        for c in s:
            if c.isdigit():
                num.append(c)
            elif c == '#':
                now = ''.join(num)
                st.append((now))
                num.clear()
            else:
                y = str(st.pop())
                x = str(st.pop())
                st.append(eval(x+c+y))
        return st.pop()

python List的pop()方法可以弹出数组中指定下标的元素，默认下标-1也就是最后一个元素，然后它还会返回弹出的元素的值。

但是这种写法为了少些几个字用了eval，这带来了大量的类型转换，性能比较差。

这样效率就提升不少了：

class Solution:
    def solve(self, str):
        st = []
        num = 0
        for c in str:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '#':
                st.append(num)
                num = 0
            else:
                b = st.pop()
                a = st.pop()
                if c == '+':
                    st.append(a + b)
                elif c == '-':
                    st.append(a - b)
                else:
                    st.append(a * b)
        return st[0]