题解 | 表达式求值

#include <cctype>
#include <cstdio>
#include <stack>
#include <string>
#include <utility>

class Solution {
  public:
    // 括号递归，先乘后加
    int solve(string s) {
        return calc(s, 0).first;
    }
  private:
    // 递归计算表达式子串(对括号表达式递归)
    // 返回 <计算结果, 最后处理到的字符下标>
    std::pair<int, int> calc(const std::string& s, int start_index) {
        int x = 0;          // x用于读取完整数字或者暂存括号表达式的计算结果
        char op = '+';      // 数字前方的运算符，初始化为‘+’来让首个数字先入栈
        std::stack<int> st; // 存放用于最终求和的数据
        // 从start_index开始逐字符处理子串
        int i = start_index;
        while (true) {
            // 先尝试读取数字子串
            while (std::isdigit(s[i]) && i < s.size()) {
                x = x * 10 + s[i] - '0'; // 累计读取数字子串
                ++i;
            }
            // 若读取到了数字，此时i一定指向运算符/')'/末尾
            if (s[i] == '(') {
                const auto& p = calc(s, i + 1); // 从'('的下一个字符开始，递归计算括号表达式
                x = p.first;      // x赋值为括号表达式的计算结果
                i = p.second + 1; // 此时i一定指向运算符/')'/末尾
            }
            // 根据数字前方的运算符决定对数字的操作
            switch (op) {
                case '+':
                    st.push(x); // 加法直接入栈
                    break;
                case '-':
                    st.push(-x); // 减法入栈相反数，转化为加法
                    break;
                case '*': // 乘法优先计算，栈顶保留相乘结果
                    int tmp = st.top() * x;
                    st.pop();
                    st.push(tmp);
                    break;
            }
            x = 0; // 完成对数字操作后，重新开始累计
            // 完成了一层括号表达式的递归计算，或者已处理到了末尾，准备结算返回
            if (s[i] == ')' || i >= s.size())
                break;
            // 此处i一定指向运算符
            op = s[i];
            ++i;
        }
        int sum = 0;
        // 完成剩余的加法计算
        while (not st.empty()) {
            sum += st.top();
            st.pop();
        }
        return {sum, i};
    }
};