题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    queue<string> transform(string s)    //将前缀表达式转为后缀表达式
    {
        queue<string> q;
        stack<char> t;
        string x;
        for(int i=0;i<s.length();i++)
        {
            while(s[i] >='0' && s[i] <='9')             //将所有运算符前的字符拼接成十进制数,并转换为string
            {
                x.push_back(s[i]);
                i++;
            }
            if(x!="")                                                
            {
                q.push(x);
                x.clear();
            }
            if(s[i] == '(')
                t.push(s[i]);
            else if(t.empty() && (s[i]=='+' || s[i]=='-'||s[i]=='*'))
                t.push(s[i]);
            else if(s[i] == ')')
            {
                while(t.top()!='(')
                {
                    x.push_back(t.top());
                    q.push(x);
                    t.pop();
                    x.clear();
                }
                t.pop();
            }
            else if(s[i] == '+' || s[i] =='*' || s[i] =='-')
            {
                if(s[i] == '*')
                {
                    t.push(s[i]);
                }
                else if((s[i] == '+' || s[i] == '-') && (t.top() == '+' || t.top() == '-' || t.top() == '*'))
                {
                    x.push_back(t.top());
                    q.push(x);
                    x.clear();
                    t.pop();
                    t.push(s[i]);
                }
                else{
                    t.push(s[i]);                  
                }
            }
        }
        while(!t.empty())
        {
            x.push_back(t.top());
            q.push(x);
            t.pop();
            x.clear();
        }
        return q;
    }
    int solve(string s) {
        queue<string> q = transform(s);
        stack<int> t;
        while(!q.empty())
        {
            while(q.front() != "+" && q.front() !="-" && q.front()!="*")
            {
                t.push(atoi(q.front().c_str()));
                q.pop();
            }
            int b=t.top();t.pop();     //右值
            int a=t.top();t.pop();   //左值
            switch(q.front()[0])
            {
                case '+':
                    t.push(a+b);
                    q.pop();
                    break;
                case '-':
                    t.push(a-b);
                    q.pop();
                    break;
                case '*':
                    t.push(b*a);
                    q.pop();
                    break;
                default:
                    q.pop();
                    break;
            }
        }
        return t.top();
    }
};