题解 | #表达式求值#

#include <cctype>
#include <string>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */

    int solve(string s) {
        stack<char> operatorStack; //运算符栈
        stack<int> numStack; //操作数栈

        for (int i = 0; i < s.size(); ++i) {
            if (isdigit(s[i])) {
                int num = 0;
                while (i < s.size() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                numStack.push(num);
                i--;
            } else if (s[i] == '(') {
                operatorStack.push(s[i]);
            } else if (s[i] == ')') {
                //计算括号内的运算
                while (!operatorStack.empty() && operatorStack.top() != '(') {
                    int value1 = numStack.top();
                    numStack.pop();
                    int value2 = numStack.top();
                    numStack.pop();
                    char op = operatorStack.top();
                    operatorStack.pop();
                    numStack.push(calculate(value2, value1, op));
                }
                //将左括号出栈
                operatorStack.pop();
            } else {
                //假如是运算符 并且当前运算符的优先级要小于等于运算符栈顶的运算符 弹出操作数栈的上面两个元素与运算符栈顶的运算符计算
                while (!operatorStack.empty() &&
                        getPriority(operatorStack.top()) >= getPriority(s[i])) {
                    int value1 = numStack.top();
                    numStack.pop();
                    int value2 = numStack.top();
                    numStack.pop();
                    char op = operatorStack.top();
                    operatorStack.pop();
                    numStack.push(calculate(value2, value1, op));
                }
                operatorStack.push(s[i]);
            }
        }

        //判读运算符栈是否还有运算符 如果还有就把剩余的计算完
        while (!operatorStack.empty()) {
            int value1 = numStack.top();
            numStack.pop();
            int value2 = numStack.top();
            numStack.pop();
            char op = operatorStack.top();
            operatorStack.pop();
            numStack.push(calculate(value2, value1, op));
        }

        return numStack.top();
    }

    //获取优先级
    int getPriority(char ch) {
        switch (ch) {
            case '+':
            case '-':
                return 1;
            case '*':
                return 2;
            default:
                return 0;
        }
    }

    //计算
    int calculate(int value1, int value2, char op) {
        switch (op) {
            case '+':
                return value1 + value2;
            case '-':
                return value1 - value2;
            case '*':
                return value1 * value2;
            default:
                return 0;
        }
    }
};