算术表达式求值c++栈

在C++中，使用栈数据结构可以用于计算算术表达式的求值。这种方法通常称为逆波兰表示法（Reverse Polish Notation, RPN），也被称为后缀表达式。栈是一种先进后出（LIFO，Last In First Out）的数据结构，在这种求值策略中，遇到操作数时压入栈中，遇到运算符时则弹出最近的两个操作数进行运算，然后将结果压回栈。

下面是一个简单的步骤：

1. 读取输入的算术表达式（例如 "2 3 + 4 *"）。
2. 将数字（操作数）逐个推入栈中。
3. 遇到运算符时，依次从栈顶取出两个操作数，执行相应的运算，并把结果放回栈中。
4. 当表达式全部处理完后，栈顶剩下的就是最终的结果。

以下是一个简化的C++示例代码片段：

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

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

int applyOp(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 要注意避免除零错误
    }
}

int evaluate(string tokens) {
    stack<int> values;
    stack<char> ops;

    for (char token : tokens) {
        if (isdigit(token)) {
            int val = 0;
            while (isdigit(token)) {
                val = (val * 10) + (token - '0');
                token++;
            }
            values.push(val);
        } else if (token == '(') {
            ops.push(token);
        } else if (token == ')') {
            while (!ops.empty() && ops.top() != '(') {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            if (!ops.empty()) {
                ops.pop(); // 弹出左括号
            }
        } else { // 运算符
            while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            ops.push(token);
        }
    }

    // 处理剩余的运算
    while (!ops.empty()) {
        int val2 = values.top();
        values.pop();
        int val1 = values.top();
        values.pop();
        char op = ops.top();
        ops.pop();
        values.push(applyOp(val1, val2, op));
    }

    return values.top();
}

int main() {
    string exp = "2 3 + 4 *";
    cout << "Result of expression: " << evaluate(exp) << endl;
    return 0;
}