题解 | #表达式求值#

中缀表达式求值：适合用递归

后缀表达式：适合用栈

写第二遍发现还是不会，逻辑理不清晰

class Solution {
public:
    int solve(string s) {
        // 字符数字转整型；一组括号内计算的结果
      int sum = 0, ans = 0;
        //  标志位的更新落后于当前符号位
        //  确保读到符号位时，符号位后续数字已知
        //  最后一个符号位更新时间是读到字符串末尾，见下面判断
      char flag = '+';
      std::stack<int> res;
      
      for (int i = 0; i <= s.size(); ++i) {
          //  数字字符转换
        if (s[i] >= '0' && s[i] <= '9') {
          while (s[i] >= '0' && s[i] <= '9') {
            sum = sum * 10 + (s[i] - '0');
            ++i;
          }
        }
          //  括号，转化为子问题进行递归
        if (s[i] == '(') {
          int j = i + 1;
          int cnt = 1;
            //  统计连续的括号
            //  确定子字符串的始末位置
          while (cnt) {
            if (s[j] == '(') {
              ++cnt;
            }
            if (s[j] == ')') {
              --cnt;
            }
            ++j;
          }
            //  除第一对括号外的子字符串
          sum = solve(s.substr(i + 1, j - (i + 1)));
            //  j指向括号下一位元素
          i = j;
        }
          //  遇到运算符
          //  知道前一个运算符之后的数字读取完毕
          //  更新运算符，同时计算前一个运算符的结果
          //  最后一个运算符的更新需要来到字符串的尾后元素
        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || i == s.size()) {
          if (flag == '+') {
            res.push(sum);
          }
          if (flag == '-') {
            res.push(-sum);
          }
          if (flag == '*') {
            int s1 = res.top();
            res.pop();
            res.push(s1 * sum);
          }
          flag = s[i];
          sum = 0;
        }
      }
      
        //  子结果的求和
      while (!res.empty()) {
        ans += res.top();
        res.pop();
      }
      
      return ans;
    }
};