题解 | #四则运算# C++ 双栈

#include <iostream>
#include <stack>
using namespace std;

void compute(stack<int>& num_st, stack<char>& op_st) {
    int op2 = num_st.top();
    num_st.pop();
    int op1 = num_st.top();
    num_st.pop();
    char op = op_st.top();
    op_st.pop();
    if (op == '+') op1 += op2;
    if (op == '-') op1 -= op2;
    if (op == '*') op1 *= op2;
    if (op == '/') op1 /= op2;
    num_st.push(op1);
}

bool priority(char m, char n) {
    // m 优先级小于n, 返回true
    if (m == '(' || m == '[' || m == '{') {
        return false;
    }
    if ((n == '+' || n == '-') && (m == '*' || m == '/')) {
        return false;
    }
    return true;
}

int main() {
    string str;
    cin >> str;
    stack<int> num_st;
    stack<char> op_st;
    str.push_back('}');
    op_st.push('{');
    bool isOp = false;
    for (int i = 0; i < str.size(); ++i) {
        // 碰到右括号
        if (str[i] == '}' || str[i] == ']' || str[i] == ')') {
            string leftkuo = "([{";
            while (leftkuo.find(op_st.top()) == leftkuo.npos) {
                compute(num_st, op_st);
            }
            op_st.pop(); // 弹出左括号
        } else if (str[i] == '{' || str[i] == '[' || str[i] == '(') {
            op_st.push(str[i]);
        } else if (isOp) {
            // 栈内操作符优先级大，先计算栈内
            while (priority(str[i], op_st.top()) &&
                op_st.top() != '(' && op_st.top() != '[' && op_st.top() != '{') {
                compute(num_st, op_st);
            }
            op_st.push(str[i]);
            isOp = false;
        } else {
            int start = i;
            if (str[i] == '+' || str[i] == '-') {
                i++;
            }
            while (i < str.size() && isdigit(str[i])) i++;
            num_st.push(stoi(str.substr(start, i - start)));
            --i;
            isOp = true;
        }
    }
    cout << num_st.top() << endl;
}