C++语言表达式求值算法详解（从零实现中缀表达式到结果的完整解析流程）

为什么需要转换成后缀表达式？

中缀表达式（如 3 + 4）是我们人类习惯的写法，但对计算机来说处理起来很麻烦，因为要不断判断运算符优先级和括号。

而后缀表达式（如 3 4 +）没有括号，也不需要考虑优先级，只需从左到右扫描，遇到数字就压栈，遇到运算符就弹出两个数计算后再压回栈——非常适合用栈来实现。

步骤一：中缀转后缀（使用调度场算法）

我们将使用著名的调度场算法（Shunting Yard Algorithm）来完成转换。核心思路如下：

1. 从左到右扫描中缀表达式的每个字符
2. 如果是数字，直接输出到结果队列
3. 如果是运算符，根据优先级决定是否先弹出栈中已有运算符
4. 遇到左括号 ( 压栈；遇到右括号 ) 则不断弹出直到遇到左括号
5. 最后将栈中剩余运算符全部弹出

下面是一个完整的 C++ 实现：

#include <iostream>#include <stack>#include <queue>#include <cctype>#include <string>#include <vector>// 获取运算符优先级int precedence(char op) {    if (op == '+' || op == '-') return 1;    if (op == '*' || op == '/') return 2;    return 0;}// 中缀转后缀std::queue<std::string> infixToPostfix(const std::string& expr) {    std::stack<char> ops;    std::queue<std::string> output;    std::string number = "";    for (char c : expr) {        if (std::isspace(c)) continue; // 忽略空格        if (std::isdigit(c)) {            number += c;        } else {            if (!number.empty()) {                output.push(number);                number = "";            }            if (c == '(') {                ops.push(c);            } else if (c == ')') {                while (!ops.empty() && ops.top() != '(') {                    output.push(std::string(1, ops.top()));                    ops.pop();                }                if (!ops.empty()) ops.pop(); // 弹出 '('            } else if (c == '+' || c == '-' || c == '*' || c == '/') {                while (!ops.empty() && ops.top() != '(' &&                       precedence(ops.top()) >= precedence(c)) {                    output.push(std::string(1, ops.top()));                    ops.pop();                }                ops.push(c);            }        }    }    if (!number.empty()) {        output.push(number);    }    while (!ops.empty()) {        output.push(std::string(1, ops.top()));        ops.pop();    }    return output;}

步骤二：后缀表达式求值

有了后缀表达式后，求值就变得非常简单。我们只需要一个数字栈：

1. 从左到右读取后缀表达式的每个 token
2. 如果是数字，压入栈
3. 如果是运算符，弹出两个数字（注意顺序！），计算结果后压回栈
4. 最后栈中只剩一个数，就是最终结果

C++ 实现如下：

// 后缀表达式求值double evaluatePostfix(std::queue<std::string> postfix) {    std::stack<double> nums;    while (!postfix.empty()) {        std::string token = postfix.front();        postfix.pop();        if (token == "+" || token == "-" || token == "*" || token == "/") {            double b = nums.top(); nums.pop();            double a = nums.top(); nums.pop();            double result;            if (token == "+") result = a + b;            else if (token == "-") result = a - b;            else if (token == "*") result = a * b;            else if (token == "/") result = a / b;            nums.push(result);        } else {            nums.push(std::stod(token));        }    }    return nums.top();}

完整示例与测试

现在我们把两部分组合起来，并测试几个表达式：

int main() {    std::string expr = "3 + 5 * (2 - 8)";    auto postfix = infixToPostfix(expr);    double result = evaluatePostfix(postfix);    std::cout << "表达式: " << expr << std::endl;    std::cout << "结果: " << result << std::endl; // 输出 -27    return 0;}

运行结果：

表达式: 3 + 5 * (2 - 8)结果: -27

总结

通过本文，你已经掌握了如何用 C++ 实现一个完整的表达式求值算法。核心知识点包括：

• 使用调度场算法将中缀表达式转为后缀表达式
• 利用栈结构高效求值后缀表达式
• 处理运算符优先级和括号嵌套

这套方法不仅适用于基础四则运算，稍作扩展还能支持函数、变量、更多运算符等，是学习编译原理和解释器开发的重要基础。

希望这篇教程能帮助你理解 C++表达式求值、表达式解析算法、C++中缀转后缀 以及 栈实现表达式计算 这些关键概念。动手试试吧，你也可以写出自己的计算器！