题解 | 四则运算

#include <bits/stdc++.h>
using namespace std;
// 定义运算符优先级
unordered_map<char, int> pri = {
    {'+', 0},
    {'-', 0},
    {'*', 1},
    {'/', 1}
};
// 计算过程: ops栈弹出运算符，nums栈弹出两个元素进行计算
void cal(vector<int>& nums, vector<char>& ops) {
    int b = nums.back();
    nums.pop_back();
    int a = nums.back();
    nums.pop_back();
    char op = ops.back();
    if(op == '+') {
        nums.emplace_back(a + b);
    } else if(op == '-') {
        nums.emplace_back(a - b);
    } else if(op == '*') {
        nums.emplace_back(a * b);
    } else if(op == '/') {
        nums.emplace_back(a / b);
    }
    ops.pop_back();
}
int calculate(const string& s) {
    // 整体思路: 栈中运算符优先级应该是从低到高递增的，而对于'*', '/'这种优先级相同的运算符，需要考虑结合性，
    // 四则运算的运算符都是从左到右的结合性，也就是说同级运算符，一定是先算左边，从这个意义上来看，同级运算符
    // 在左边的优先级高，在右边的优先级低
    // 于是运算符栈是一个优先级严格递增的单调栈（因为在'+'后紧接着'-'，那'+'应该被计算，遇到同级运算符相当   于遇到了更低优先级的运算符）
    // 在遇到优先级变低的符号后就弹出栈顶元素并进行计算（这里提的优先级已经是考虑了结合性的优先级）
    // 遇到左括号直接入栈，如果左括号右边就是 '-'，还需要把0入nums栈
    // 遇到右括号直接一直弹出ops的运算符进行运算直到遇到左括号，然后把左括号弹出栈
    // 遍历完字符串后不要忘记ops栈不为空还得继续计算
    // 用vector模拟栈
    vector<char> ops;
    vector<int> nums;
    // 对于单目运算符'-'，在栈顶加0即可
    if(s[0] == '-') {
        nums.emplace_back(0);
    }
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] >= '0' && s[i] <= '9') {
            int j = i;
            for(; j < s.size() && s[j] >= '0' && s[j] <= '9'; ++j);
            nums.emplace_back(stoi(s.substr(i, j - i)));
            i = j - 1;
            continue;
        }
        if(s[i] == '(') {
            ops.emplace_back('(');
            if(s[i + 1] == '-') {
                nums.emplace_back(0);
            }
            continue;
        }
        if(s[i] == ')') {
            while(ops.back() != '(') {
                cal(nums, ops);
            }
            ops.pop_back();
            continue;
        }
        while(!ops.empty() && ops.back() != '(' && pri[s[i]] <= pri[ops.back()]) {
            cal(nums, ops);
        }
        ops.emplace_back(s[i]);
    }
    while(!ops.empty()) {
        cal(nums, ops);
    }
    return nums.back();
}
int main() {
    string s;
    cin >> s;
    for(char& c : s) {
        if(c == '[' || c == '{') {
            c = '(';
        } else if(c == '}' || c == ']') {
            c = ')';
        }
    }
    cout << calculate(s);
}
// 64 位输出请用 printf("%lld")