题解 | #表达式求值#

利用vector存储每段计算结果

#include <cctype>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 测试用算术表达式
// 3+2*(1+2*(-4/(8-6)+7))
// -4/(-6+8)
// -(3+2)

// 计算算术表达式   lBound与rBound都参与计算，防止越界
int compute(const string& s, int lBound, int rBound) {
    // 初始化运算符与左边界
    char op = '+';
    int left = lBound;
    if ('-' == s[lBound]) {
        op = '-';
        left++;
    }
    // 当前数值
    int num = 0;
    // 当前数值的vector数组
    vector<int> vecNum;

    for (int i = left; i <= rBound; i++) {
        // 当前i为数字，优先级最高
        if (isdigit(s[i])) {
            num = 10 * num + s[i] - '0';
        }
        
        // 当前i为左括号，找到右括号并递归计算
        if ('(' == s[i]) {
            // 括号深度layer
            int layer = 0;
            int j = i;
            while (j <= rBound) {
                if ('(' == s[j]) {
                    // 括号深度递增
                    layer++;
                    j++;
                }
                else if (')' == s[j]) {
                    // 括号深度递减
                    layer--;
                    // 检查括号是否已结束
                    if (0 == layer) {
                        // 当且仅当j为与i对应的右括号时，break
                        break;
                    }
                    j++;
                }
                else {
                    // 非左右括号，仅j递增
                    j++;
                }
            }
            
            // 递归计算括号内的算术表达式，边界去括号
            num = compute(s, i + 1, j - 1);
            // 从右括号后一位继续计算
            i = j + 1;
        }

        // 当前i非数字或已经到了算术表达式的末尾
        if (!isdigit(s[i]) || i == rBound) {
            switch (op) {
                case '+':
                {
                    vecNum.push_back(num);
                    break;
                }
                case '-':
                {
                    vecNum.push_back(-num);
                    break;
                }
                case '*':
                {
                    vecNum.back() *= num;
                    break;
                }
                case '/':
                {
                    vecNum.back() /= num;
                    break;
                }
                case '(':
                case ')':
                {
                    break;
                }
                default:
                {
                    cout << "unknown char" << op << endl;
                    break;
                }
            }

            // 更新op，字符串末尾为数字时op可能是数字
            op = s[i];
            num = 0;
        }
    }

    // 计算结果&打印
    int result = 0;
    for (int x : vecNum) {
        result += x;
    }
    return result;
}

int main() {
    // 获取算术表达式
    string s;
    getline(cin, s);
    // 循环运算
    int result = compute(s, 0, s.length() - 1);
    cout << result;
}