题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int precedence(char op)
    {
        if(op=='+'||op=='-') return 1;
        if(op=='*'||op=='/') return 2;
        return 0;
    }
    int applyOp(int a,int b,char op)
    {
        switch(op)
        {
            case '+':return a+b;
            case '-':return a-b;
            case '*':return a*b;
            case '/':return a/b;
        }
        return 0;
    }
    int solve(string s) {
        // write code here
        stack<int> value;
        stack<char> ops;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                int a=s[i]-'0';
                while(i+1<s.length()&&s[i+1]>='0'&&s[i+1]<='9')
                {
                    a=a*10+s[i+1]-'0';
                    i++;
                }
                value.push(a);
            }
            //处理负号
            else if(s[i]=='-'&&(i==0||s[i-1]=='('))
            {
                int a=s[i]-'0';
                while(i+1<s.length()&&s[i+1]>='0'&&s[i+1]<='9')
                {
                    a=a*10+s[i+1]-'0';
                    i++;
                }
                value.push(-a);
            }
            else if(s[i]=='(')
            {
                ops.push(s[i]);
            }
            else if(s[i]==')')
            {
                while(!ops.empty()&&ops.top()!='(')
                {
                    int v2=value.top();
                    value.pop();
                    int v1=value.top();
                    value.pop();
                    char o=ops.top();
                    ops.pop();
                    value.push(applyOp(v1,v2,o));
                }
                if(!ops.empty()) ops.pop();
            }
            else
            {
                while(!ops.empty()&&precedence(ops.top())>=precedence(s[i]))
                {
                    int v2=value.top();
                    value.pop();
                    int v1=value.top();
                    value.pop();
                    char o=ops.top();
                    ops.pop();
                    value.push(applyOp(v1,v2,o));
                }
                ops.push(s[i]);
            }
        }
        while(!ops.empty())
        {
            int v2=value.top();
                    value.pop();
                    int v1=value.top();
                    value.pop();
                    char o=ops.top();
                    ops.pop();
                    value.push(applyOp(v1,v2,o));
        }
        return value.top();
    }
};