C++表达式树详解（从零开始实现表达式树与求值算法）

什么是表达式树？

假设我们有一个中缀表达式：(3 + 5) * 2。它的表达式树如下：

      *     / \    +   2   / \  3   5

可以看到，根节点是乘法运算符 *，左子树是加法表达式 3 + 5，右子树是数字 2。这种结构天然支持递归处理，非常适合用 C++ 的面向对象特性来实现。

步骤一：定义树节点结构

首先，我们需要定义表达式树的节点。每个节点要么是操作数（叶子），要么是运算符（内部节点）。

#include <iostream>#include <string>#include <cctype>// 表达式树节点类class ExprNode {public:    std::string data;          // 存储操作符或操作数    ExprNode* left;            // 左子节点    ExprNode* right;           // 右子节点    // 构造函数    ExprNode(const std::string& val) : data(val), left(nullptr), right(nullptr) {}};

步骤二：构建表达式树（从中缀表达式）

为了构建表达式树，我们需要先将中缀表达式转换为后缀表达式（逆波兰表示法），然后根据后缀表达式构建树。这里我们采用两个栈：一个用于操作符，一个用于节点。

以下是一个简化版的构建函数（假设输入已去除空格且合法）：

#include <stack>#include <vector>#include <sstream>// 判断是否为操作符bool isOperator(const std::string& token) {    return token == "+" || token == "-" || token == "*" || token == "/";}// 获取操作符优先级int getPrecedence(const std::string& op) {    if (op == "+" || op == "-") return 1;    if (op == "*" || op == "/") return 2;    return 0;}// 将中缀表达式字符串分割为 tokenstd::vector<std::string> tokenize(const std::string& expr) {    std::vector<std::string> tokens;    std::string num = "";    for (char c : expr) {        if (std::isdigit(c)) {            num += c;        } else {            if (!num.empty()) {                tokens.push_back(num);                num = "";            }            if (c != ' ') {                tokens.push_back(std::string(1, c));            }        }    }    if (!num.empty()) tokens.push_back(num);    return tokens;}// 构建表达式树ExprNode* buildExpressionTree(const std::string& infix) {    auto tokens = tokenize(infix);    std::stack<ExprNode*> nodeStack;    std::stack<std::string> opStack;    for (const auto& token : tokens) {        if (std::isdigit(token[0])) {            // 操作数：创建节点并压入 nodeStack            nodeStack.push(new ExprNode(token));        } else if (token == "(") {            opStack.push(token);        } else if (token == ")") {            // 弹出直到遇到 '(')            while (!opStack.empty() && opStack.top() != "(") {                ExprNode* right = nodeStack.top(); nodeStack.pop();                ExprNode* left = nodeStack.top(); nodeStack.pop();                ExprNode* opNode = new ExprNode(opStack.top()); opStack.pop();                opNode->left = left;                opNode->right = right;                nodeStack.push(opNode);            }            if (!opStack.empty()) opStack.pop(); // 弹出 '('        } else if (isOperator(token)) {            // 处理操作符            while (!opStack.empty() && opStack.top() != "(" &&                   getPrecedence(opStack.top()) >= getPrecedence(token)) {                ExprNode* right = nodeStack.top(); nodeStack.pop();                ExprNode* left = nodeStack.top(); nodeStack.pop();                ExprNode* opNode = new ExprNode(opStack.top()); opStack.pop();                opNode->left = left;                opNode->right = right;                nodeStack.push(opNode);            }            opStack.push(token);        }    }    // 处理剩余操作符    while (!opStack.empty()) {        ExprNode* right = nodeStack.top(); nodeStack.pop();        ExprNode* left = nodeStack.top(); nodeStack.pop();        ExprNode* opNode = new ExprNode(opStack.top()); opStack.pop();        opNode->left = left;        opNode->right = right;        nodeStack.push(opNode);    }    return nodeStack.top();}

步骤三：计算表达式树的值

有了表达式树后，我们可以通过后序遍历（左右根）递归求值。

double evaluate(ExprNode* root) {    if (!root) return 0.0;    // 如果是叶子节点（操作数）    if (!isOperator(root->data)) {        return std::stod(root->data);    }    double leftVal = evaluate(root->left);    double rightVal = evaluate(root->right);    if (root->data == "+") return leftVal + rightVal;    if (root->data == "-") return leftVal - rightVal;    if (root->data == "*") return leftVal * rightVal;    if (root->data == "/") return leftVal / rightVal;    return 0.0; // 不应到达此处}

完整示例与测试

下面是一个完整的可运行示例：

int main() {    std::string expr = "(3+5)*2";    ExprNode* tree = buildExpressionTree(expr);    double result = evaluate(tree);    std::cout << "表达式: " << expr << std::endl;    std::cout << "计算结果: " << result << std::endl; // 输出 16    return 0;}

总结

通过本教程，你已经学会了如何使用 C++ 实现一个基本的表达式树系统。这项技术广泛应用于编译器设计、计算器开发以及符号计算等领域。掌握C++数据结构中的树结构，不仅能提升你的编程能力，还能加深对表达式求值算法的理解。

虽然我们的实现做了简化（例如未处理负数、函数调用等），但它为你打下了坚实的基础。你可以在此基础上扩展支持更多功能，比如变量、函数或更复杂的语法。

希望这篇关于 C++表达式树 的教程对你有帮助！动手实践是掌握知识的最佳方式，快去写代码试试吧！