题解 | #表达式求值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int pre(char ch)
    {
        if (ch == '+')
            return 1;
        else if (ch == '-')
            return 1;
        else if (ch == '*')
            return 2;
        else
            return 2;
    }

    int solve(int v1, int v2, char ch)
    {
        if (ch == '+')
            return v1 + v2;
        else if (ch == '-')
            return v1 - v2;
        else if (ch == '*')
            return v1 * v2;
        else
            return v1 / v2;
    }
    int solve(string s) {
        // write code here
        stack<int> is;
        stack<char> op;
        for (int i = 0; i < s.size(); i++)
        {
            char ch = s[i];
            if (isdigit(ch)){
                int sum = 0;
                int j = i;
                while (j < s.size() && isdigit(s[j])) sum = sum * 10 + (s[j++] - '0');
                is.push(sum);
                i = j - 1;		// 修改索引到最后一个数字，然后执行下一次 for 循环
            }
            else if (ch == '(')
                op.push(ch);
            else if (ch == '+' || ch == '-' || ch == '*' || ch == '/'){
                while (!op.empty() && op.top() != '(' && pre(ch) <= pre(op.top())){
                    int v2 = is.top();
                    is.pop();
                    int v1 = is.top();
                    is.pop();
                    
                    char op1 = op.top();
                    op.pop();
                    
                    int ans = solve(v1, v2, op1);
                    is.push(ans);
                }
                op.push(ch);
            }
            else if (ch == ')'){
                while (!op.empty() && op.top() != '('){
                    int v2 = is.top();
                    is.pop();
                    int v1 = is.top();
                    is.pop();
                    
                    char op1 = op.top();
                    op.pop();
                    
                    int ans = solve(v1, v2, op1);
                    is.push(ans);
                }
                if (!op.empty()){
                    op.pop();
                }
            }
        }
        
        while (!op.empty())
        {
            int v2 = is.top();
            is.pop();
            int v1 = is.top();
            is.pop();

            char op1 = op.top();
            op.pop();

            int ans = solve(v1, v2, op1);
            is.push(ans);
        }
        
        int ans = is.top();
        is.pop();
        
        return ans;
    }
};