C语言表达式树详解（从零构建表达式树并实现求值）

为什么使用表达式树？

使用表达式树构建有以下优势：

• 结构清晰，便于递归处理
• 支持前缀、中缀、后缀表达式的相互转换
• 是编译器和解释器中语法分析的重要组成部分

用C语言实现表达式树

首先，我们需要定义树节点的结构。每个节点包含数据（操作符或操作数）、左子树和右子树指针。

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>typedef struct TreeNode {    char data[20];               // 存储操作符或操作数    struct TreeNode* left;    struct TreeNode* right;} TreeNode;// 创建新节点TreeNode* createNode(const char* value) {    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));    strcpy(node->data, value);    node->left = NULL;    node->right = NULL;    return node;}

构建表达式树（从中缀表达式）

为了简化，我们假设输入是一个合法的后缀表达式（逆波兰表达式），因为从中缀构建需要处理括号和运算符优先级，较为复杂。后缀表达式可以直接用栈构建表达式树。

// 判断是否为操作符int isOperator(const char* token) {    return (strcmp(token, "+") == 0 || strcmp(token, "-") == 0 ||            strcmp(token, "*") == 0 || strcmp(token, "/") == 0);}// 从后缀表达式构建表达式树TreeNode* buildExpressionTree(char* postfix[]) {    TreeNode* stack[100];    int top = -1;    int i = 0;    while (postfix[i] != NULL) {        TreeNode* node = createNode(postfix[i]);        if (isOperator(postfix[i])) {            // 操作符：弹出两个操作数            node->right = stack[top--];            node->left = stack[top--];        }        // 压入当前节点        stack[++top] = node;        i++;    }    return stack[top];}

表达式求值

有了表达式树，我们可以通过表达式求值算法递归计算结果：

double evaluate(TreeNode* root) {    if (root == NULL) return 0;    // 如果是叶子节点，返回数值    if (root->left == NULL && root->right == NULL) {        return atof(root->data);    }    // 递归计算左右子树    double leftVal = evaluate(root->left);    double rightVal = evaluate(root->right);    // 根据操作符进行运算    if (strcmp(root->data, "+") == 0)        return leftVal + rightVal;    else if (strcmp(root->data, "-") == 0)        return leftVal - rightVal;    else if (strcmp(root->data, "*") == 0)        return leftVal * rightVal;    else if (strcmp(root->data, "/") == 0)        return leftVal / rightVal;    return 0; // 错误情况}

完整示例

下面是一个完整的测试程序，计算表达式 (3 + 5) * 2，其后缀形式为 3 5 + 2 *：

int main() {    // 后缀表达式: 3 5 + 2 *    char* postfix[] = {"3", "5", "+", "2", "*", NULL};    TreeNode* root = buildExpressionTree(postfix);    double result = evaluate(root);    printf("表达式求值结果: %.2f\n", result); // 输出: 16.00    return 0;}

总结

通过本教程，你已经掌握了C语言二叉树在表达式处理中的应用。表达式树不仅帮助我们理解编译原理的基础，还能用于计算器、公式引擎等实际项目中。建议你动手实现并尝试扩展功能，比如支持括号、变量或更多运算符。

记住，学习C语言表达式树的关键在于理解树的递归结构和后缀表达式的构建逻辑。多练习，你就能轻松驾驭这一强大工具！