用stl栈写一个表达式求值

好的，以下是用 STL 栈实现表达式求值的 C++ 代码：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int evaluateExpression(string expression) {
    stack<int> values; // 存储操作数的栈

    stack<char> operators; // 存储运算符的栈

    for (char c : expression) {
        // 如果遇到空格，跳过
        if (c == ' ') {
            continue;
        }
        // 如果遇到左括号，将其压入运算符栈
        else if (c == '(') {
            operators.push(c);
        }
        // 如果遇到数字，将其解析出来并压入操作数栈
        else if (isdigit(c)) {
            int value = 0;
            while (isdigit(c)) {
                value = value * 10 + (c - '0');
                c = expression[++i];
            }
            values.push(value);
            // 因为上面的 while 循环中多读了一个字符，所以这里需要将 i 减一
            i--;
        }
        // 如果遇到右括号，开始计算括号内的表达式
        else if (c == ')') {
            while (!operators.empty() && operators.top() != '(') {
                int operand2 = values.top();
                values.pop();

                int operand1 = values.top();
                values.pop();

                char op = operators.top();
                operators.pop();

                int result;
                if (op == '+') {
                    result = operand1 + operand2;
                } else if (op == '-') {
                    result = operand1 - operand2;
                } else if (op == '*') {
                    result = operand1 * operand2;
                } else {
                    result = operand1 / operand2;
                }

                values.push(result);
            }
            // 将左括号弹出
            operators.pop();
        }
        // 如果遇到运算符，比较优先级，将高优先级的运算符先计算
        else {
            while (!operators.empty() && precedence(operators.top()) >= precedence(c)) {
                int operand2 = values.top();
                values.pop();

                int operand1 = values.top();
                values.pop();

                char op = operators.top();
                operators.pop();

                int result;
                if (op == '+') {
                    result = operand1 + operand2;
                } else if (op == '-') {
                    result = operand1 - operand2;
                } else if (op == '*') {
                    result = operand1 * operand2;
                } else {
                    result = operand1 / operand2;
                }

                values.push(result);
            }
            operators.push(c);
        }
    }

    // 计算最后的结果
    while (!operators.empty()) {
        int operand2 = values.top();
        values.pop();

        int operand1 = values.top();
        values.pop();

        char op = operators.top();
        operators.pop();

        int result;
        if (op == '+') {
            result = operand1 + operand2;
        } else if (op == '-') {
            result = operand1 - operand2;
        } else if (op == '*') {
            result = operand1 * operand2;
        } else {
            result = operand1 / operand2;
        }

        values.push(result);
    }

    return values.top();
}

int precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

int main() {
    string expression = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
    int result = evaluateExpression(expression);
    cout << "The result is: " << result << endl;
    return 0;
}

这里我以一个包含加减乘除和括号的表达式为例进行了演示。在代码中，我们使用了两个栈，一个存储操作数，一个存储运算符。根据运算符的优先级，我们需要不断地将栈中元素弹出进行计算，最后得到表达式的结果。