C语言中NPN表达式转树形结构的函数实现及方法咨询

嘿，我看你正在尝试用C语言实现逆波兰表达式（也就是你说的NPN表达式）转语法树的功能，目前用了strtok来拆分token，但卡在了后续逻辑上。这里我来帮你梳理下思路，修正代码里的问题，再给出完整的实现方案。

首先得明确：逆波兰表达式转树的核心思路是用栈来辅助处理——这是这类问题的标准解法，因为后缀表达式的结构是「操作数1 操作数2 运算符」，刚好可以用栈来暂存已经解析好的节点，遇到运算符时再取出两个节点组合成新的运算符节点。

先说说你当前代码里的几个明显问题：

• 第一个token被跳过了：你调用strtok(string," ")拿到第一个token后，直接进入循环调用strtok(NULL," ")，导致第一个token完全没处理；
• tree变量未初始化：直接用tree->discriminant会触发野指针错误，因为你还没给节点分配内存；
• 只处理了运算符，完全没考虑操作数的情况；
• 没有用栈管理节点，直接赋值tree会覆盖之前的节点，根本没法构建树形结构。

接下来我给你一套完整的实现方案，包括节点定义、栈的辅助函数，以及修正后的表达式解析函数：

1. 先定义树节点结构 #

首先我们需要明确每个节点的类型：要么是存储数值的叶子节点，要么是存储运算符的内部节点。这里用discriminant字段来区分（比如用'v'标记值节点）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// 树节点结构体
typedef struct Node {
    char discriminant; // 'v'表示值节点，其余为运算符（+、-、*、/、p等）
    double value;      // 仅值节点有效
    struct Node* left; // 左子树
    struct Node* right;// 右子树
} Node;

typedef Node* T_Tree; // 你的T_Tree应该是节点指针类型

2. 辅助函数：创建节点和栈操作 #

我们需要两个创建节点的函数，分别用于值节点和运算符节点；另外还需要栈的push/pop操作来暂存节点：

// 创建值节点（叶子节点）
T_Tree createLeafNode(double val) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    node->discriminant = 'v';
    node->value = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建运算符节点（内部节点）
T_Tree createOpNode(char op, T_Tree left, T_Tree right) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    node->discriminant = op;
    node->left = left;
    node->right = right;
    return node;
}

// 栈的实现（用于暂存树节点）
#define STACK_MAX 100
T_Tree stack[STACK_MAX];
int stack_top = -1;

void push(T_Tree node) {
    if (stack_top >= STACK_MAX - 1) {
        fprintf(stderr, "错误：栈溢出，表达式过长\n");
        exit(EXIT_FAILURE);
    }
    stack[++stack_top] = node;
}

T_Tree pop() {
    if (stack_top < 0) {
        fprintf(stderr, "错误：表达式格式无效，栈空时尝试弹出节点\n");
        exit(EXIT_FAILURE);
    }
    return stack[stack_top--];
}

3. 修正后的表达式解析函数 #

现在可以实现核心的readgenerate函数了，逻辑如下：

• 用strtok逐个拆分token；
• 如果是操作数（数字，包括负数和小数），创建值节点压入栈；
• 如果是运算符，弹出栈顶两个节点（注意顺序：先弹右子树，再弹左子树），创建运算符节点后压栈；
• 最后栈中应该只剩一个节点，就是整个表达式树的根节点。

T_Tree readgenerate(char string[]) {
    char *token = strtok(string, " ");
    
    while (token != NULL) {
        // 判断是否是操作数：开头是数字，或者是'-'且后面跟着数字（处理负数）
        if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
            double val = atof(token);
            T_Tree leaf = createLeafNode(val);
            push(leaf);
        } else {
            char op = token[0];
            // 校验运算符是否合法
            if (!(op == '+' || op == '-' || op == '*' || op == '/' || op == 'p')) {
                fprintf(stderr, "错误：未知运算符 '%c'\n", op);
                exit(EXIT_FAILURE);
            }
            // 弹出两个操作数节点，注意顺序：后缀表达式是 左操作数 右操作数 运算符
            // 栈是后进先出，所以先弹的是右操作数，后弹的是左操作数
            T_Tree right_node = pop();
            T_Tree left_node = pop();
            T_Tree op_node = createOpNode(op, left_node, right_node);
            push(op_node);
        }
        token = strtok(NULL, " ");
    }

    // 最终栈中只能有一个节点（根节点），否则表达式格式错误
    if (stack_top != 0) {
        fprintf(stderr, "错误：表达式格式无效，节点数量不匹配\n");
        exit(EXIT_FAILURE);
    }

    return stack[stack_top];
}

4. 额外提示 #

• 记得写一个销毁树的函数，避免内存泄漏：

void destroyTree(T_Tree tree) {
    if (tree == NULL) return;
    destroyTree(tree->left);
    destroyTree(tree->right);
    free(tree);
}

• 测试的时候可以用类似"3 4 + 5 *"这样的逆波兰表达式，解析后应该得到(3+4)*5的树形结构；
• 如果你的'p'运算符是特殊操作（比如幂运算），逻辑和其他二元运算符一致，不需要额外修改，只要确保弹出两个节点即可。

备注：内容来源于stack exchange，提问作者xxjmpxx__