北京理工大学数据结构实验报告 简易计算器(二叉树)

内容发布更新时间 : 2024/12/24 7:48:49星期一 下面是文章的全部内容请认真阅读。

}

while(t!=b);

a[i]='\\0';//完成反序后缀式的逆向 T=create(T,a); //create()函数创建二叉链表

postordertraverse(T);//后序遍历进行计算 printf(\输出结果

return 0;

} //main

3.2其它函数的具体实现

char *convert();

//将运算式转换成逆后缀序列,并将该序列作为返回值; 首先输入运算式,判断是否为数字,将数字存入数组的数值域,并用符号代替数值,产生新的用符号表示的运算式。

然后用字符优先算法将算式转换为逆后缀式,将数组首地址传回给主函数。 并且在输入不合法时给予错误提示。

struct node *create(struct node *T,char d[]); //建立二叉链表,并返回根结点 void postordertraverse(struct node *e);

//进行后序遍历,运用了递归的思想,实际上调用operation函数进行计算

float operation(float a,float b,char c);

//四则运算函数,主要实现运算功能

int in(char c);

//判断是否为运算符,是运算符返回1

部分函数的代码如下: (1)create函数

struct node *create(struct node *T,char d[])

{ //建立二叉链表,并返回根结点 int i;

if(d[w]>='A'&&d[w]<='Z') {T->data=d[w];

for(i=0;array[i].sign!='\\0';i++) {if(array[i].sign==d[w])

{ T->number=array[i].number;break;} }

T->left=NULL; T->right=NULL; w++;

}

else{

if(flag==0)flag=1; else

T=(struct node *)malloc(sizeof(struct node ));

(T)->data=d[w]; w++;

T->left=(struct node *)malloc(sizeof(struct node ));

T->right=(struct node *)malloc(sizeof(struct node ));

T->right=create((T)->right,d); T->left=create((T)->left,d); }

return T;

} //create

(2)operation函数

float operation(float a,float b,char c)

{ //四则运算函数,主要实现运算功能

switch(c) {

case '+':return a+b; case '-':return a-b; case '*':return a*b; case '/':return a/b;

default :printf(\运算符错误!\\n\

} }//operation

(3)in函数 int in(char c)

{ //判断是否为运算符,是运算符返回1;否则返回0 if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')

return 1; else return 0;

}//in

四、调试分析

4.1难点以及困难

1.由于本次试验做过堆栈式计算器,思维存在惯性,打不开新思路; 2.建立二叉链表是最重要的环节,而在这之前,必须先得到后缀表达式,由于之前没有接触过后缀表达式,从而给变成造成了困难。即涉及char型和float型变量统一化,又有算符优先级的判别。 3.二叉链表的建立,要利用好优先级,以及注意操作数为叶子节点这一特点。 4.2经验与体会

1.算式计算的问题是一个非常经典的题目。之前用栈来实现的。但是用栈来实现是一个非常麻烦的过程,第一要解决算式判断,是否为符合规则的算式,第二要由中缀表达式转化为后缀表达式。这两个部分是栈实现计算算式表达式的比较复杂的地方。不仅如此,栈实现里面的各种运算符的优先级,各种条件判断,可以说是麻烦的要命。相比之下,用二叉树免除了算式表达式的检查过程。并不是不需要检查,而是检查的过程就包含在创建二叉树的过程。认真分析,我们会发现,所有的叶子结点必须是操作数结点,而所有的非叶子结点必须是运算符结点,否则表达式的结构一点不正确,创建二叉树的过程就可以对表达式经行检查。

2.总结一句就是:好的数据结构能事半功倍,要培养善于发现的思维,当有某个思路然后去实现它,另外要积累经验。好好理解数据结构! 五、测试结果 1.加减运算

输入:6+9-5 输出:10

2.乘除运算

输入:5.6*2.7/2 输出:7.56

3.四则混合运算

输入:(2+3)*8-3/2 输出:23.5

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi