题解 | #表达式求值#

#include <cctype>
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    // 计算函数
    int caculate(int a, int b, char op)
    {
        switch (op)
        {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        default:
            return 0;
        }
    }

    // 优先级函数
    int precedence(char op)
    {
        switch (op)
        {
        case '+':
        case '-':
            return 1;
        case '*':
            return 2;
        default:
            return 0;
        }
    }

    int solve(string s)
    {
        // 双栈
        stack<char> op;
        stack<int> num;

        for (int i = 0; i < s.length(); ++i)
        {
            // 防空格
            if (isspace(s[i]))
                continue;
            // 进入数字识别状态，isdigit(s[i]) = s[i] >= '0' && s[i] <= '9'
            if (isdigit(s[i]))
            {
                int flag = i;
                int n = 0;
                while (isdigit(s[flag]))
                {
                    n = n * 10 + (s[flag] - '0');
                    flag++;
                }

                i = flag - 1;
                num.push(n);
            }

            else if (s[i] == '(')
            {
                op.push(s[i]);
            }

            // 碰到右括号触发计算
            else if (s[i] == ')')
            {
                while (!op.empty() && op.top() != '(')
                {
                    int b = num.top();
                    num.pop();
                    int a = num.top();
                    num.pop();
                    char opt = op.top();
                    op.pop();

                    num.push(caculate(a, b, opt));
                }
                op.pop(); // 弹出左括号
            }

            // 其他符号
            else
            {
                // 如果栈顶的优先级大于现在符号，则需要弹栈，并进行计算
                while (!op.empty() && precedence(op.top()) >= precedence(s[i]))
                {
                    int b = num.top();
                    num.pop();
                    int a = num.top();
                    num.pop();
                    char opt = op.top();
                    op.pop();

                    num.push(caculate(a, b, opt));
                }
                op.push(s[i]);
            }
        }

        // 处理剩下的部分
        while (!op.empty())
        {
            int b = num.top();
            num.pop();
            int a = num.top();
            num.pop();
            char opt = op.top();
            op.pop();

            num.push(caculate(a, b, opt));
        }

        return num.top();
    }
};

双栈做法，个人感觉比较好理解