题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        stack<int> val;
        stack<char> ops;
        int sum=0;
        for(int i=0; i<s.size();i++)
        {
            if(s[i]>='0'&&s[i]<='9')
                sum = sum*10+(s[i]-'0');
            else
            {
                if (sum!=0){
                    val.push(sum);
                    sum = 0;
                }
                if(ops.empty() || judge(s[i], ops.top())==true)
                    ops.push(s[i]);
                else{
                    if(s[i]==')'){
                        while(ops.top()!='(')
                        {
                            int x = val.top();
                            val.pop();
                            int y = val.top();
                            val.pop();
                            if(ops.top()=='+') val.push(x+y);
                            else if (ops.top()=='-') val.push(y-x);
                            else if (ops.top()=='*') val.push(x*y);
                            else val.push(y/x);
                            ops.pop();
                        }
                        ops.pop();
                    }
                    else 
                    {
                        while (!ops.empty() && judge(s[i], ops.top())==false)
                        {
                            int x = val.top();
                            val.pop();
                            int y = val.top();
                            val.pop();
                            if(ops.top()=='+') val.push(x+y);
                            else if (ops.top()=='-') val.push(y-x);
                            else if (ops.top()=='*') val.push(x*y);
                            else val.push(y/x);
                            ops.pop();
                        }
                        ops.push(s[i]);
                    }
                }
            }
        }
        if(sum!=0) val.push(sum);
        while(!ops.empty())
        {
            int x = val.top();
            val.pop();
            int y = val.top();
            val.pop();
            if(ops.top()=='+') val.push(x+y);
            else if (ops.top()=='-') val.push(y-x);
            else if (ops.top()=='*') val.push(x*y);
            else val.push(y/x);
            ops.pop();
        }
        return val.top();
    }
    bool judge(char c1,char c2)
    {
        if(c1=='(')
            return true;
        else if(c1==')')
            return false;
        else if(c2=='(')
            return true;
        else if((c1=='*'||c1=='/')&&(c2=='+'||c2=='-'))
            return true;
        else return false;
    }
};