牛牛与后缀表达式题解

给定牛牛一个后缀表达式s，计算它的结果，例如，1+1对应的后缀表达式为1#1#+，‘#’作为操作数的结束符号。
其中，表达式中只含有‘+’、’-‘、’*‘三种运算，不包含除法。

题解：利用栈进行模拟，摸清栈先进后出的特性，利用这一特性即可方便的计算后缀表达式。先用栈保存数字，在遇到运算符时取栈顶的两个元素进行运算后再放回栈顶即可。

时间复杂度：
空间复杂度：

参考代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    long long solve(string str) {
        // write code here
        stack<long long> n;
        long long s = 0, x = 0, y = 0;
        for (int i = 0; i < str.size(); i++)
        {
            switch (str[i])
            {
            case '+':
                x = n.top();
                n.pop();
                y = n.top();
                n.pop();
                n.push(x + y);
                break;
            case '-':
                x = n.top();
                n.pop();
                y = n.top();
                n.pop();
                n.push(y - x);
                break;
            case '*':
                x = n.top();
                n.pop();
                y = n.top();
                n.pop();
                n.push(x * y);
                break;
            case '/':
                x = n.top();
                n.pop();
                y = n.top();
                n.pop();
                n.push(y / x);
                break;
            case '#':
                n.push(s);
                s = 0;
                break;
            default:
                s = s * 10 + str[i] - '0';
                break;
            }
        }
        return n.top();
    }
};