双栈表达式求值代码c➕➕

以下是使用 C++ 语言实现的双栈表达式求值代码：

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

int calculate(string expression) {
    stack<char> operator_stack;
    stack<int> operand_stack;

    unordered_map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

    auto evaluate = [&]() {
        char op = operator_stack.top(); operator_stack.pop();
        int operand2 = operand_stack.top(); operand_stack.pop();
        int operand1 = operand_stack.top(); operand_stack.pop();
        int result;
        switch (op) {
            case '+': result = operand1 + operand2; break;
            case '-': result = operand1 - operand2; break;
            case '*': result = operand1 * operand2; break;
            case '/': result = operand1 / operand2; break;
        }
        operand_stack.push(result);
    };

    for (char token : expression) {
        if (isdigit(token)) {
            operand_stack.push(token - '0');
        } else if (token == '+' || token == '-' || token == '*' || token == '/') {
            while (!operator_stack.empty() && operator_stack.top() != '(' && precedence[token] <= precedence[operator_stack.top()]) {
                evaluate();
            }
            operator_stack.push(token);
        } else if (token == '(') {
            operator_stack.push(token);
        } else if (token == ')') {
            while (operator_stack.top() != '(') {
                evaluate();
            }
            operator_stack.pop();
        }
    }

    while (!operator_stack.empty()) {
        evaluate();
    }

    return operand_stack.top();
}

int main() {
    string expression = "3*(4+5)-2/(7-3)";
    int result = calculate(expression);
    cout << "The result of " << expression << " is " << result << endl;
    return 0;
}

这个程序使用了 STL 中的 stack 容器来实现操作符栈和操作数栈。我们还使用了一个无序映射 unordered_map 来存储不同操作符的优先级。在程序的主函数中，我们调用 calculate 函数来计算表达式的值。在 calculate 函数内部，我们定义了一个 lambda 表达式 evaluate，用于弹出操作符栈顶的操作符并弹出操作数栈顶的两个操作数，计算结果并将结果压入操作数栈。然后我们循环扫描表达式的每个字符，如果是数字，就将其压入操作数栈；如果是操作符，就比较其与操作符栈顶的运算符优先级，如果该运算符优先级低于栈顶运算符，则将栈顶运算符弹出并弹出操作数栈顶的两个操作数，计算结果并将结果压入操作数栈，直到该运算符优先级大于栈顶运算符或者栈为空时，将该运算符压入栈中；如果是左括号，就将其压入操作符栈；如果是右括号，就依次弹出操作符栈顶的操作符并弹出操作数栈顶的两个操作数，计算结果并将结果压入操作数栈，直到遇到左括号。最后，我们处理剩余的操作符，直到操作符栈为空，最终操作数栈中仅有一个数，即为表达式的值。