题解 | #表达式求值#

#include <cctype>
#include <functional>
#include <queue>
#include <stack>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        queue<char> q;
        for (auto &c: s) {
            q.push(c);
        }
        function<int()> recur = [&]() -> int {
            stack<int> st;
            char bef = '+';
            int num = 0;
            while (!q.empty()) {
                auto now = q.front();
                q.pop();
                if (isdigit(now)) {
                    num = num * 10 + (now - '0');
                }
                if (now == '(') {
                    num = recur();
                }
                if (!isdigit(now) || q.empty()) {
                    switch (bef) {
                        case '+': {
                            st.push(num);
                        } break;
                        case '-': {
                            st.push(-num);
                        } break;
                        case '*': {
                            st.top() *= num;
                        } break;
                    }
                    num = 0;
                    bef = now;
                }
                if (now == ')') {
                    break;
                }
            }
            int res = 0;
            while (!st.empty()) {
                res += st.top();
                st.pop();
            }
            return res;
        };
        return recur();
    }
};

思路：递归。

* 遇到左括号进入递归。

* 遇到右括号退出递归，返回值即为括号里的表达式值。

* 把加减当作正负数存在栈中，结束时一起运算。

* 乘法优先级高，所以遇到乘法时需要马上取出栈顶的数计算。