题解 | #牛牛与后缀表达式#

思路

考察递归，遇到操作数入栈，遇到运算符将栈顶前两个元素出栈运算，再将结果入栈，遍历完后栈顶元素即表达式结果

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    long long legalExp(string str) {
        // write code here
        stack<long long> st;
        long long tmp = 0;
        for(int i = 0;i < str.length();i++){
            if((str[i] >= '0')&&(str[i] <= '9')){    //若为数字字符，转数字
                tmp = tmp*10 + (str[i] - '0');
                continue;
            }
            else if(str[i] == '#'){    //若为#，说明操作数加载完成，入栈
                st.push(tmp);
                tmp = 0;
                continue;
            }
            else{    //若为运算符，取栈顶前两个元素作运算，结果再入栈
                long long Right = st.top(),Left;
                st.pop(); Left = st.top(); st.pop();
                if(str[i] == '+') st.push(Left + Right);
                if(str[i] == '-') st.push(Left - Right);
                if(str[i] == '*') st.push(Left * Right);
            }
        }
        return st.top();
    }
};