[C++知识库]中缀表达式求值(C++)

整数中缀表达式求解问题

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

int cal(char oper, stack<int> &operands) {
    int num_after = operands.top();
    operands.pop();
    if (oper == '!') {
        return -num_after;
    }
    int num_before = operands.top();
    operands.pop();
    if (oper == '+') {
        return num_before + num_after;
    }
    else if (oper == '-') {
        return num_before - num_after;
    }
    else if (oper == '*') {
        return num_before * num_after;
    }
    else if (oper == '/') {
        return num_before / num_after;
    }
    else if (oper == '\\') {
        return num_after / num_before;
    }
    return 0;
}
//分解字符串，将数字和运算符存入数组中
vector<string> parse_string(string str) {
    vector<string> store;
    string add;
    for (int i = 0; i < str.size();) {
        while (str[i] >= '0' && str[i] <= '9') {
            add += str[i];
            ++i;
        }
        if (add.size() > 0) {
            store.push_back(add);
            add = "";
        }
        if (i == str.size()) {
            break;
        }
        else if (str[i] == '+' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')') {
            add += str[i];
            store.push_back(add);
            add = "";
            ++i;
        }
        //判断‘-’为减号或者负号
        else if (str[i] == '-') {
            if (i == 0 || str[i - 1] == '(') {
                add += '!';
            }
            else {
                add += '-';
            }
            store.push_back(add);
            add = "";
            ++i;
        }
    }
    return store;
}

int calculate_expression(string expression) {
    //不同运算符的优先级， '!'表示负号
    unordered_map<char, int> priority = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0} , {'!', 3} };
    stack<int> operands;
    stack<string> operators;
    vector<string> parsed_expression = parse_string(expression);
    //当前运算符优先级低于栈顶运算符优先级时，进行前面高优先级的运算
    for (string& str : parsed_expression) {
        if (str == "+" || str == "-" || str == "*" || str == "/" || str == "!") {
            if (operators.empty() || priority[operators.top()[0]] <= priority[str[0]]) {
                operators.push(str);
            }
            else {
                int priority_before = priority[operators.top()[0]];
                int priority_after = priority[str[0]];
                while (!operators.empty() && priority_after < priority_before) {
                    char oper = operators.top()[0];
                    operators.pop();
                    operands.push(cal(oper, operands));
                    if (!operators.empty()) {
                        priority_before = priority[operators.top()[0]];
                    }
                }
                operators.push(str);
            }
        }
        else if (str == "(") {
            operators.push(str);
        }
        else if (str == ")") {
            //遇到右括号时，计算括号内表达式
            char oper = operators.top()[0];
            while (oper != '(') {
                operators.pop();
                //由于是从后往前运算，当遇到 /*, --这两种情况时，后面的运算符需要进行改变
                //A/B*C -> A*(C/B) ||  A-B-C -> A-(B+C)
                if (!operators.empty() && oper == '-' && operators.top() == "-") {
                    oper = '+';
                }
                if (!operators.empty() && oper == '*' && operators.top() == "/") {
                    operators.top() = "*";
                    oper = '\\';
                }
                operands.push(cal(oper, operands));
                oper = operators.top()[0];
            }
            operators.pop();            
        }
        else {
            operands.push(atoi(str.c_str()));
        }
    }
    //处理剩下同优先级的运算符
    while (!operators.empty()) {
        char oper = operators.top()[0];
        operators.pop();
        if (!operators.empty() && oper == '-' && operators.top() == "-") {
            oper = '+';
        }
        if (!operators.empty() && oper == '*' && operators.top() == "/") {
            operators.top() = "*";
            oper = '\\';
        }
        operands.push(cal(oper, operands));
    }
    //最终的计算结果保存在操作数中
    return operands.top();
}

int main() {
    string expression = "(-16/4*(3-(-1)))+11*3";
    cout << expression << " == " << calculate_expression(expression);
    return 0;
}