用C语言建立一个表达式树,仅适用于十进制的加减乘除四则运算,参考结构:typedef struct ExpressionTree{int element;ExpressionTree* left_tree;ExpressionTree* right_tree;}ExpressionTree, *ExpressionTreeRoot;并包含以下数据操作:int evaluate(ExpressionTreeRoot &T);//获得整个表达式树或者相关子树的计算结果;void in_fix( int, bool );//以中缀方式打印表达式;void reverse_polish();//以后缀方式打印表达式;bool is_leaf();//判断节点是否为叶子节点;
时间: 2024-02-21 14:02:15 浏览: 55
数据结构c语言版.docx
好的,以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct ExpressionTree {
int element;
struct ExpressionTree* left_tree;
struct ExpressionTree* right_tree;
} ExpressionTree, *ExpressionTreeRoot;
int evaluate(ExpressionTreeRoot T) {
if (T->left_tree == NULL && T->right_tree == NULL) {
return T->element;
} else {
int left_value = evaluate(T->left_tree);
int right_value = evaluate(T->right_tree);
switch (T->element) {
case '+':
return left_value + right_value;
case '-':
return left_value - right_value;
case '*':
return left_value * right_value;
case '/':
return left_value / right_value;
default:
return 0;
}
}
}
void in_fix(ExpressionTreeRoot T, bool is_root) {
if (T == NULL) return;
if (T->left_tree != NULL) {
if (!is_root && is_leaf(T->left_tree)) {
printf("(");
}
in_fix(T->left_tree, false);
}
printf("%c", T->element);
if (T->right_tree != NULL) {
in_fix(T->right_tree, false);
if (!is_root && is_leaf(T->right_tree)) {
printf(")");
}
}
}
void reverse_polish(ExpressionTreeRoot T) {
if (T == NULL) return;
reverse_polish(T->left_tree);
reverse_polish(T->right_tree);
printf("%c", T->element);
}
bool is_leaf(ExpressionTreeRoot T) {
return T->left_tree == NULL && T->right_tree == NULL;
}
int main() {
ExpressionTreeRoot root = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->element = '+';
root->left_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->left_tree->element = '*';
root->right_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->right_tree->element = '-';
root->left_tree->left_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->left_tree->left_tree->element = 3;
root->left_tree->right_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->left_tree->right_tree->element = 4;
root->right_tree->left_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->right_tree->left_tree->element = 5;
root->right_tree->right_tree = (ExpressionTree*)malloc(sizeof(ExpressionTree));
root->right_tree->right_tree->element = 2;
printf("Infix expression: ");
in_fix(root, true);
printf("\n");
printf("Reverse Polish notation: ");
reverse_polish(root);
printf("\n");
printf("Result: %d\n", evaluate(root));
return 0;
}
```
这个程序将建立一个如下所示的表达式树:
```
+
/ \
* -
/ \ / \
3 4 5 2
```
并且提供了三个操作:
- `in_fix`:以中缀方式输出表达式
- `reverse_polish`:以后缀方式输出表达式
- `evaluate`:计算整个表达式树的结果
你可以根据需要进行修改和扩展。
阅读全文