将后缀表达式转化成表达式树C语言具体代码
时间: 2023-06-12 22:05:42 浏览: 88
以下是将后缀表达式转化成表达式树的 C 语言代码,其中使用了栈(Stack)数据结构。
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct node {
char data;
struct node *left;
struct node *right;
};
// 栈结构体
struct stack {
int top;
struct node **items;
};
// 创建新节点
struct node *createNode(char data) {
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 初始化栈
struct stack *createStack(int capacity) {
struct stack *newStack = (struct stack *)malloc(sizeof(struct stack));
newStack->top = -1;
newStack->items = (struct node **)malloc(capacity * sizeof(struct node *));
return newStack;
}
// 判断栈是否为空
int isEmpty(struct stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(struct stack *s) {
return s->top == 99;
}
// 入栈
void push(struct stack *s, struct node *item) {
if (isFull(s)) {
printf("Stack is full\n");
return;
}
s->items[++s->top] = item;
}
// 出栈
struct node *pop(struct stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return NULL;
}
return s->items[s->top--];
}
// 从后缀表达式中构造表达式树
struct node *constructTree(char postfix[]) {
struct stack *s = createStack(strlen(postfix));
struct node *t, *t1, *t2;
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
t = createNode(postfix[i]);
push(s, t);
} else {
t = createNode(postfix[i]);
t1 = pop(s);
t2 = pop(s);
t->right = t1;
t->left = t2;
push(s, t);
}
}
t = pop(s);
free(s);
return t;
}
// 中序遍历表达式树
void inorder(struct node *t) {
if (t) {
inorder(t->left);
printf("%c ", t->data);
inorder(t->right);
}
}
int main() {
char postfix[] = "ab+cd-*";
struct node *root = constructTree(postfix);
printf("Infix expression: ");
inorder(root);
return 0;
}
```
程序中定义了 `struct node` 结构体表示表达式树的节点,`struct stack` 结构体表示栈的数据结构。`createNode` 函数用于创建新节点,`createStack` 函数用于初始化栈。
`isEmpty` 和 `isFull` 函数分别用于判断栈是否为空和已满。`push` 函数用于入栈,`pop` 函数用于出栈。
`constructTree` 函数用于将后缀表达式转化成表达式树,程序中使用栈来辅助构造表达式树。该函数遍历后缀表达式,如果当前字符是数字,则创建一个新节点并将其入栈。如果当前字符是操作符,则弹出栈顶的两个节点,将当前字符作为新节点的值,将弹出的两个节点分别作为新节点的左右子节点,最后将新节点入栈。
`inorder` 函数用于中序遍历表达式树,输出中序遍历的结果即为中缀表达式。
在 `main` 函数中,定义了一个后缀表达式字符串 `postfix`,通过 `constructTree` 函数将其转换成表达式树,并通过 `inorder` 函数输出中缀表达式。