后缀表达式用二叉树计算的例子和C代码
时间: 2024-05-06 20:17:44 浏览: 11
下面是一个用二叉树计算后缀表达式的例子和相应的C代码:
假设我们要计算后缀表达式 "5 3 +",我们可以构建如下的二叉树:
```
+
/ \
5 3
```
根据后缀表达式的计算规则,我们从下往上按照操作符进行计算,最终得到结果 8。
下面是相应的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct Node {
char val;
struct Node *left;
struct Node *right;
};
struct Node *newNode(char val) {
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int evaluate(struct Node *root) {
if (root == NULL) {
return 0;
}
if (isdigit(root->val)) {
return root->val - '0';
}
int left_val = evaluate(root->left);
int right_val = evaluate(root->right);
switch (root->val) {
case '+':
return left_val + right_val;
case '-':
return left_val - right_val;
case '*':
return left_val * right_val;
case '/':
return left_val / right_val;
default:
return 0;
}
}
struct Node *constructTree(char postfix[]) {
struct Node *stack[100];
int top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
struct Node *node = newNode(postfix[i]);
stack[++top] = node;
} else {
struct Node *node = newNode(postfix[i]);
node->right = stack[top--];
node->left = stack[top--];
stack[++top] = node;
}
}
return stack[top];
}
int main() {
char postfix[] = "53+";
struct Node *root = constructTree(postfix);
printf("Result: %d\n", evaluate(root));
return 0;
}
```
在上述代码中,我们首先定义了一个 `Node` 结构体表示二叉树的节点,其中包括节点的值和左右子树。然后,我们实现了三个函数:
- `newNode`:用于创建新节点的函数。
- `evaluate`:用于计算二叉树的值的函数。在该函数中,我们首先判断当前节点的值是否为数字,如果是则返回该数字,否则递归计算左右子树的值,并根据当前节点的值进行相应的计算。
- `constructTree`:用于根据后缀表达式构建二叉树的函数。在该函数中,我们使用一个栈来实现。遍历后缀表达式的每个字符,如果是数字则创建一个新节点并将其压入栈中,否则弹出栈顶的两个节点作为当前节点的左右子树,并将该节点压入栈中。
最后,在 `main` 函数中我们调用 `constructTree` 函数构建二叉树,再调用 `evaluate` 函数计算二叉树的值。