题解 | 四则运算

#include<bits/stdc++.h>
using namespace std;

int getp(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void compute(stack<int>& nums, stack<char>& ops) {
    int b = nums.top();
    nums.pop();
    int a = nums.top();
    nums.pop();
    char op = ops.top();
    ops.pop();
    if (op == '+') nums.push(a + b);
    else if (op == '-') nums.push(a - b);
    else if (op == '*') nums.push(a * b);
    else if (op == '/') nums.push(a / b);
}

int calculate(string s) {
    stack<int> nums;
    stack<char> ops;
    int num = 0;
    bool has_num = false;

    for (int i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
            has_num = true;
        } else {
            if (has_num) {
                nums.push(num);
                num = 0;
                has_num = false;
            }
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.top() != '(') {
                    compute(nums, ops);
                }
                ops.pop();
            } else {
                // 处理负号
                if (c == '-' && (i == 0 || s[i - 1] == '(' || s[i - 1] == '{' ||
                                 s[i - 1] == '[' ||
                                 s[i - 1] == '+' || s[i - 1] == '-' || s[i - 1] == '*' || s[i - 1] == '/')) {
                    nums.push(0);
                    ops.push('-');
                } else {
                    // 处理运算符优先级
                    while (!ops.empty() && ops.top() != '(' && getp(ops.top()) >= getp(c)) {
                        compute(nums, ops);
                    }
                    ops.push(c);
                }
            }
        }
    }

    if (has_num) {
        nums.push(num);
    }
    while (!ops.empty()) {
        compute(nums, ops);
    }
    return nums.top();
}

int main() {
    string s;
    cin >> s;
    replace(s.begin(), s.end(), '[', '(');
    replace(s.begin(), s.end(), ']', ')');
    replace(s.begin(), s.end(), '{', '(');
    replace(s.begin(), s.end(), '}', ')');
    cout << calculate(s) << endl;
    return 0;
}

#牛客春招刷题训练营#https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fdiscuss%2F726480854079250432

1. 预处理括号：将所有类型的括号统一替换为小括号，简化后续处理逻辑。
2. 双栈处理：使用nums栈存储数字，ops栈存储运算符和括号。
3. 运算符优先级：通过get_priority函数实现优先级判断，确保乘除优先于加减。
4. 负号处理：当遇到负号且前方无数字时，压入0并处理为减法操作。
5. 括号处理：遇到右括号时，不断计算直到匹配到左括号，确保括号内优先计算。
6. 最终计算：遍历结束后处理剩余运算符，得到最终结果。