题解 | 四则运算

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

//弹出一个运算符和两个操作数，计算后的结果压入操作数栈
void compute_num_symbol (stack<int>& num, stack<char>& symbol) {
    //运算符出栈
    char sign = symbol.top();
    symbol.pop();

    //操作数出栈，先弹出的为右操作数，后弹出的为左操作数
    int num1 = num.top(); //右操作数
    num.pop();
    int num2 = num.top(); //左操作数
    num.pop();

    //计算【左操作数 运算符 右操作数】
    int res;
    switch (sign) {
        case '+':
            res = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;
        default:
            break;
    }
    num.push(res);//结果压入操作数栈
}

//判断运算符优先级，乘除为2，加减为1
int priority (char c) {
    if (c == '*' || c == '/')
        return 2;
    else
        return 1;
}

//计算中缀表达式
int count_expression (string str) {
    stack<int> number; //操作数栈
    stack<char> sign; //运算符栈

    //如果开始或左括号后直接跟“-”号，补0（即-4变0-4），这一步是必须的
    for (int i = 0; i < str.length(); ++i) {
        if (i == 0 && str[i] == '-')
            str = "0" + str;
        else if (str[i] == '-' && (str[i - 1] == '(' || str[i - 1] == '[' ||
                                   str[i - 1] == '{'))
            str.insert(i, "0");
    }

    bool flag =
        false; //前一位为符号位是false，为数位是true（用于计算多位数）
    for (char c : str) {
        //当扫描到操作数时，将操作数压入操作数栈
        if (c >= '0' && c <= '9') {
            //前一位为符号位，则直接压入本位
            if (!flag) {
                flag = true;
                number.push(c - '0');
            }
            //前一位为数位，则将上一个数出栈，乘10，再加上本位
            else {
                int num = number.top() * 10 + (c - '0');
                number.pop();
                number.push(num); //新数入栈
            }
        }
        //当扫描到运算符时
        else {
            flag = false;
            if (c == '(' || c == '[' || c == '{')
                sign.push(c);//扫描到左括号，入栈
            else if (c == ')' || c == ']' ||
                     c == '}') {//当扫描到右括号时，依次弹出栈内的运算符，直到弹出左括号时结束
                //当栈顶不是左括号时，继续弹出运算符计算
                while (sign.top() != '(' && sign.top() != '[' &&
                        sign.top() != '{') {
                    compute_num_symbol(number, sign);
                }
                sign.pop();//弹出左括号
            } else { //当扫描到+ - *  /
                while (!sign.empty()) {
                    if (sign.top() == '(' || sign.top() == '[' || sign.top() == '{')
                        break;
                    if (priority(sign.top()) >= priority(
                                c))  //栈顶运算符的优先级大于等于当前的运算符，弹出运算符计算
                        compute_num_symbol(number, sign);
                    else
                        break; //否则结束弹出
                }
                sign.push(c); //当前运算符入栈
            }
        }
    }

    //将剩下的运算符全部弹出
    while (!sign.empty()) {
        compute_num_symbol(number, sign);
    }

    int result = number.top();
    return result;
}//计算中缀表达式

int main () {
    string str;
    cin >> str;
    cout << count_expression(str) << endl;
    return 0;
}