题解 | #四则运算#

#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;
}

双栈法，这里讲几个要点

第一：输入的数字不止个位数，要做好转化，这里用了str的一个构造方法；

第二：每准备入栈一个新的非左括号运算符之前，要判断一下这个新运算符与当前栈顶运算符的优先级，如果栈顶的运算符优先级大于或等于（一定要有等于）这个新运算符的优先级，则用这个栈顶符号做一次运算；运算过程可以写一个函数，优先级可以使用一个map；

第三：对于负数的读入，写一个标志位，如果上一个输入的符号为数字，则该‘-’符号是运算符；如果上一个输入的符号为运算符，则该‘-’符号代表负数的前缀；初始标志位为上一次输入为符号的状态；

第四：在字符串读入完成后，继续运算直到运算符栈为空后输出数字栈的栈顶元素即可。

建议理解的时候在纸张上画出栈帮助理解运行过程。