题解 | #表达式求值# 双栈

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

map<char, int> prioit = {
    {'+', 0},
    {'-', 0},
    {'*', 1},
    {'/', 1},
    {'(', -1},
    {')', 2}
};
bool compare(char& a, char& b) {
    if (prioit[a] < prioit[b]) return false;
    return true;
}

void myOperator(stack<int>& num, stack<char>& op) {
    int b = num.top();
    num.pop();
    int a = num.top();
    num.pop();
    char c = op.top();
    op.pop();

    int res;
    switch (c) {
        case '+':
            res =  a + b;
            break;
        case '-':
            res = a - b;
            break;
        case '*':
            res = a * b;
            break;
        case '/':
            res = a / b;
            break;
    }
    num.push(res);
}

int main() {
    string s;
    cin >> s;
    s = s + ")";
    stack<int> num;
    stack<char> op;
    op.push('(');
    string n = "";
    char pre = '(';
    for (char& i : s) {
        if (prioit.count(i) == 0) {
            n += i;
        } else {
            if (i == '-') {
                if (prioit.count(pre) != 0 && pre != ')') {
                    num.push(0);
                }
            }

            if (n.size() != 0) {
                int num_ = stoi(n);
                num.push(num_);
                n = "";
            }
            if (i == '(') {
                op.push(i);
            } else if (i == ')') {
                while (op.top() != '(') {
                    myOperator(num, op);
                }
                op.pop();
            } else {
                while (compare(op.top(), i)) {
                    myOperator(num, op);
                }
                op.push(i);
            }
        }
        pre = i;
    }

    cout << num.top();
}
// 64 位输出请用 printf("%lld")