C语言后缀表达式转二叉树

以下是C语言代码实现后缀表达式转二叉树：

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

typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} Node;

typedef struct stack {
    Node *data;
    struct stack *next;
} Stack;

Node* new_node(char data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Stack* new_stack() {
    Stack *stack = (Stack*) malloc(sizeof(Stack));
    stack->data = NULL;
    stack->next = NULL;
    return stack;
}

void push(Stack *stack, Node *node) {
    Stack *new_top = new_stack();
    new_top->data = node;
    new_top->next = stack->next;
    stack->next = new_top;
}

Node* pop(Stack *stack) {
    if (stack->next == NULL) {
        return NULL;
    }
    Node *node = stack->next->data;
    Stack *temp = stack->next;
    stack->next = stack->next->next;
    free(temp);
    return node;
}

Node* build_expression_tree(char* postfix) {
    Stack *stack = new_stack();
    int n = strlen(postfix);
    for (int i = 0; i < n; i++) {
        if (isdigit(postfix[i])) {
            Node *node = new_node(postfix[i]);
            push(stack, node);
        } else {
            Node *node = new_node(postfix[i]);
            node->right = pop(stack);
            node->left = pop(stack);
            push(stack, node);
        }
    }
    return pop(stack);
}

void inorder_traversal(Node *node) {
    if (node == NULL) {
        return;
    }
    if (node->left != NULL || node->right != NULL) {
        printf("(");
    }
    inorder_traversal(node->left);
    printf("%c", node->data);
    inorder_traversal(node->right);
    if (node->left != NULL || node->right != NULL) {
        printf(")");
    }
}

int main() {
    char postfix[100];
    printf("Enter postfix expression: ");
    scanf("%s", postfix);
    Node *root = build_expression_tree(postfix);
    printf("Inorder traversal: ");
    inorder_traversal(root);
    printf("\n");
    return 0;
}

该程序首先定义了两个结构体，分别表示节点和栈。节点结构体包含数据和左右子树指针，栈结构体包含数据和下一个节点指针。接着定义了一些函数，分别用于创建新节点、创建新栈、入栈、出栈和构建表达式二叉树。其中，构建表达式二叉树的算法如下：

1. 从左到右扫描后缀表达式。

2. 如果遇到数字，就创建一个新节点，并将其压入栈中。

3. 如果遇到运算符，就创建一个新节点，从栈中弹出两个节点作为其左右子树，然后将新节点压入栈中。

4. 扫描结束后，栈中剩下的节点就是表达式二叉树的根节点。

最后，程序通过中序遍历输出表达式二叉树。