简易计算器(二叉树)

1、实验三简易计算器（二叉树）05111341班 李凌豪 11201312631 需求分析1.1.问题重述（1）问题描述由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。（2）基本要求 a要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。b将中缀表达式转换成二叉表达式树。c后序遍历求出表达式的值（3）数据结构与算法分析一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。a建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符

2、，建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。b求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。（4）测试1.2.问题分析 本实验要求我们编写一个程序，利用二叉树，实现简易计算器的功能。实现实数范围内的四则混合运算，而且要考虑括号对运算顺序的影响。而且，题目要求

3、用二叉树的知识来实现程序功能，因此需要将输入的中序表达式转换成逆波兰序列，然后就以此序列建立二叉链表，之后通过后序遍历实现运算的功能。大概要求就是这样的。2 概要设计2.1.抽象数据类型的定义考虑到，算符为字符型变量，算数为单精度浮点型变量。考虑先讲输入的浮点数替换为char型的符号。Struct jd为二叉链表的节点类型。每一个节点都有字符域data，数字的话会有数值域shuzi为单精度浮点数。struct jdchar data;float shuzi;struct jd *next1;struct jd *next2;Struct haha 类型的数组ka20用来存放运算数，如果是运算数

4、，就存进来，然后用字符域fuhao来代替数值域的单精度shuzi。这样一来，容易进行运算式向逆波兰序列的转换。struct hahachar fuhao;float shuzi;ka20;2.2.主程序流程主函数主要有以下流程：首先，调用zhuanhuan函数实现向逆波兰序列的转换；然后，将得到的逆波兰序列反向，方便之后的建立二叉链表的操作；之后，调用createBTree函数来建立二叉链表；最后调用houxu函数进行后序遍历操作，具体操作就是运算；输出运算结果。具体操作由各子函数实现。2.3.程序模块之间的调用关系主函数直接调用zhuanhuan createBTree houxu三个子函数

5、。zhuanhuan函数直接调用jud函数以及in函数进行判断。houxu函数直接调用yunsuan函数，进行后序遍历中的运算操作。3 详细设计3.1.主函数的具体实现主函数主要调用各子函数。输入操作被放在zhuanhuan函数中，调用zhuanhuan函数实现向逆波兰序列的转换；将得到的逆波兰序列反向，方便之后的建立二叉链表的操作，这也是此主函数中唯一的需要进行运算的程序段；调用createBTree函数来建立二叉链表；最后调用houxu函数进行后序遍历操作，具体操作就是运算。而输出操作仍在主函数内进行。 具体程序如下所示：int main()struct jd *T;flag=0;T=(s

6、truct jd *)malloc(sizeof(struct jd); char *b,a100,*t; int i;b=zhuanhuan();for(t=b;*t!='0't+);i=0;dot-;ai=*t;i+;while(t!=b);ai='0'/完成逆波兰式的逆向 T=createBTree(T,a);printf("n");houxu(T);printf("n%gn",result);return 0; 3.2.子函数的具体实现（1） char *zhuanhuan();此函数功能比较强大，既包含了输入操作

7、部分，也包含了将数值转换为符号进行存储的算法，以及由运算式转换到逆波兰序列的算法。首先输入运算式，判断是否为数字，将数字存入ka20数组的数值域，并用符号代替数值，产生新的用符号表示的运算式。然后用字符优先算法将算式转换为逆波兰式，将数组首地址传回给主函数。并且在输入不合法时显示错误原因。（2） struct jd *createBTree(struct jd *T,char d);建立二叉链表，叶子节点全为数值符号，而其他节点存的是算符。将二叉链表根节点地址返回主函数。（3） int in(char c)此函数用来判断是数值符号还是运算符，是运算符返回1，否则返回0。返回到zhuanhuan

8、函数中。（4） void houxu(struct jd *e)此函数用来后序遍历操作，具体操作为运算，调用yunsuan函数。采用递归算法实现。（5） float yunsuan(float a,float b,char c)真正用来进行双目运算的函数，实现四则运算。4 调试分析4.1.难点以及遇到的困难本次实验的难点主要有两个方面。一方面是怎样把一般运算式存到二叉链表中，这里就要用到逆波兰式，先把一般运算式转换成逆波兰式，就可以轻松建立二叉链表，再由后序遍历运算操作得到最终结果。另一方面，二叉链表的建立也是一个难点，因为我们首次使用二叉树结构编程，二叉树遍历算法要用到递归，这也是难点，但是

9、理解起来并不难，实现起来也不难。其他细节方面，将数值替换成符号算是一种简便的方法吧，这样就将式子变成了只含字符型变量的字符串，处理起来自然方便。4.2.经验及体会 通过这个实验，我们较为熟练地掌握了二叉链表的建立、遍历等操作，成功地编出了一个基于二叉链表的简易计算器。要建立二叉链表，必须有先序遍历、中序遍历或者后序遍历序列，所以需要将输入的运算式转换为逆波兰序列。将数值替换成符号，这样就将式子变成了只含字符型变量的字符串，方便进行你波兰转换。5 测试结果首先测试单一的加减乘除运算： 可见完全正确（测试结果依据的标准答案为华为开发的基于安卓系统的手机科学计算器，下同）。然后验证四则混合运算：与标

10、准答案吻合，故可实现四则混合运算功能。综上所述，该程序可实现实数的混合四则运算功能。6. 附录#include<stdio.h> #include<string.h>#include<stdlib.h>#include<math.h> struct jdchar data;float shuzi;struct jd *next1;struct jd *next2;struct hahachar fuhao;float shuzi;ka20;char *zhuanhuan();/将运算式转换成逆波兰序列 struct jd *createBTree

11、(struct jd *T,char d);/建立二叉链表 void houxu(struct jd *e);/进行后序遍历 float yunsuan(float a,float b,char c);/进行运算 int in(char c);/是运算符返回1 int w,flag;float result=0;int main()struct jd *T;flag=0;T=(struct jd *)malloc(sizeof(struct jd); char *b,a100,*t; int i;b=zhuanhuan();for(t=b;*t!='0't+);i=0;dot-

12、;ai=*t;i+;while(t!=b);ai='0'/完成逆波兰式的逆向 T=createBTree(T,a);printf("n");houxu(T);printf("n%gn",result);return 0; struct jd *createBTree(struct jd *T,char d) int i; if(dw>='A'&&dw<='Z') T->data=dw; for(i=0;kai.fuhao!='0'i+) if(kai.fuh

13、ao=dw) T->shuzi=kai.shuzi;break; T->next1=NULL;T->next2=NULL;w+; else if(flag=0)flag=1;else T=(struct jd *)malloc(sizeof(struct jd ); (T)->data=dw;w+; T->next1=(struct jd *)malloc(sizeof(struct jd ); T->next2=(struct jd *)malloc(sizeof(struct jd ); T->next2=createBTree(T)->ne

14、xt2,d); T->next1=createBTree(T)->next1,d); return T; char *zhuanhuan()w=0; char *a,*b; bool jud(char stack, int n); char str100,str1100; char exp100; char stack100; char ch; int flag=1; unsigned int zs; int i=0,j=0,t=0,top=0,k=0,l=0; printf("请输入表达式:n"); scanf("%s",str1); fo

15、r(i=0;str1i!='0'i+) b=&str1i; if(in(str1i)!=1&&(i=0&&(in(str10)=0)|(i!=0&&in(str1i-1)=1&&in(str1i)=0) kak.shuzi=atof(b); kak.fuhao=k+65; strl=kak.fuhao; k+;l+; else if(in(str1i)=1) strl=str1i;l+; kak.fuhao='0' strl='0' i=0;k=0;l=0; zs=strle

16、n(str); strzs='#' ch=stri; while(ch!='#')if(ch>='A'&&ch<='Z')expt=ch;t+;else if(ch='(')top+;stacktop=ch;k+;else if(ch='')expt=ch;t+;else if(ch=')') if(top!=0) if(jud(stack,top) while(stacktop!='(') expt=stacktop; top-; t+;

17、 top-; l+; else printf("括号不匹配!n"); flag=0; break; elseprintf("括号不匹配!n");flag=0; break;else if(ch='+'|ch='-')while(top!=0&&stacktop!='(')expt=stacktop;top-;t+;top+;stacktop=ch;else if(ch='*'|ch='/')while(stacktop='*'|stacktop

18、='/')expt=stacktop;top-;t+;top+;stacktop=ch;elseprintf("第%d个数开始出错!n",i+1);flag=0;break;i+;ch=stri;if(k!=l)printf("括号不匹配!n");flag=0;else if(strzs-1='+'|strzs-1='-'|strzs-1='*'|strzs-1='/')printf("该式不是中缀表达式!n");flag=0;if(flag!=0)whi

19、le(top!=0)expt=stacktop;t+;top-;printf("逆波兰式输出:");for(j=0;j<t;j+)printf("%c",expj); printf("n");expt='0' a=&exp0;return a; bool jud(char stack ,int n) int i; for( i = 0;i<n;i+) if(stacki='(') return true; break; void houxu(struct jd *e)if(e->next1!=NULL&&e->next2!=NULL)if(e->next1->data='+'|e->next1->data='-'|e->next1->data='*'|e->next1->data='/'|e->next2->data='+'|e->next2->data='-'|e->next2->data='*'|e->next2->