栈的应用中缀表达式求值c++代码实现

栈是一种先进后出（LIFO，Last In First Out）的数据结构，在中缀表达式求值中非常有用。当我们需要将中缀表达式转换为等价的后缀（也称为逆波兰表示法，RPN），然后使用栈来进行计算时，可以利用栈的特性。

以下是一个简单的 C++ 代码实现，用于中缀表达式的求值：

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

using namespace std;

int isOperator(char op) {
    if (op == '+' || op == '-' || op == '*' || op == '/') return true;
    return false;
}

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

double applyOp(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b; // 注意这里除数不能为0
        default: return 0; // 非法操作符
    }
}

double evaluatePostfix(string tokens) {
    stack<double> values;
    stack<char> ops;

    for (char token : tokens) {
        if (!isOperator(token)) {
            values.push(stod(token));
        } else {
            while (!ops.empty() && priority(ops.top()) >= priority(token)) {
                double val2 = values.top(); values.pop();
                double val1 = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            ops.push(token);
        }
    }

    while (!ops.empty()) {
        double val2 = values.top(); values.pop();
        double val1 = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        values.push(applyOp(val1, val2, op));
    }

    return values.top();
}

int main() {
    string expression = "3 + 5 * 2"; // 示例中缀表达式
    cout << "Value of expression: " << evaluatePostfix(expression) << endl;
    return 0;
}

在这个代码中，我们遍历中缀表达式的每个字符，如果是数字就入栈，如果是运算符则取出栈顶两个数做相应运算并压回结果，直到运算符栈为空。最后栈顶剩下的就是表达式的计算结果。