题解 | #表达式求值#

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

void caculate(stack<int>& numS, stack<char>& opS) {
    int num2 = numS.top();
    numS.pop();
    int num1 = numS.top();
    numS.pop();
    char op = opS.top();
    opS.pop();
    switch (op) {
        case '+':
            numS.push(num1 + num2);
            break;
        case '-':
            numS.push(num1 - num2);
            break;
        case '*':
            numS.push(num1 * num2);
            break;
        case '/':
            numS.push(num1 / num2);
            break;
    }
}

int main() {
    string str;
    // 双栈法解决
    stack<int> numS;
    stack<char> opS;
    // 设置计算符优先级
    map<char, int> m;
    m.insert(pair<char, int>('+', 0));
    m.insert(pair<char, int>('-', 0));
    m.insert(pair<char, int>('*', 1));
    m.insert(pair<char, int>('/', 1));
    m.insert(pair<char, int>('(', -1));
    getline(cin, str);
    int lastType = 0; // 记录上一个入栈的数据类型,用于识别负数
    for (int i = 0; i < str.size(); i++) {
        if (isdigit(str[i])) {
            int b = i;
            while (isdigit(str[i])) {
                i++;
            }
            string str2(str.begin() + b, str.begin() + i);
            int num = stoi(str2);
            numS.push(num);
            i--;
            lastType = 1;
        } else if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            opS.push('(');
            lastType = 0;
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            while (opS.top() != '(') {
                caculate(numS, opS);
            }
            opS.pop();
        } else if (str[i] == '-') {
            if (lastType == 1) {
                while (!opS.empty() && m[opS.top()] >= m[str[i]]) {
                    caculate(numS, opS);
                }
                opS.push(str[i]);
                lastType = 0;
            } else if (lastType == 0) {
                i++;
                int b = i;
                while (isdigit(str[i])) {
                    i++;
                }
                string str2(str.begin() + b, str.begin() + i);
                int num = 0 - stoi(str2);
                numS.push(num);
                i--;
                lastType = 1;
            }
        } else {
            while (!opS.empty() && m[opS.top()] >= m[str[i]]) {
                caculate(numS, opS);
            }
            opS.push(str[i]);
            lastType = 0;
        }
    }
    while (!opS.empty()) {
        caculate(numS, opS);
    }

    cout << numS.top() << endl;
}

emmm,比起HJ50只有括号的变化，代码直接复用就行。

双栈法