简易计算器(二叉树)浅析.doc

实验三 ——简易计算器（二叉树） 李凌豪 1120131263 需求分析 1.1.问题重述 （1）问题描述 由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。 （2）基本要求 a．要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。 b．将中缀表达式转换成二叉表达式树。 c．后序遍历求出表达式的值 （3）数据结构与算法分析 一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。 a．建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前有哪些信誉好的足球投注网站，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。 b．求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。 （4）测试 1.2.问题分析 本实验要求我们编写一个程序，利用二叉树，实现简易计算器的功能。实现实数范围内的四则混合运算，而且要考虑括号对运算顺序的影响。而且，题目要求用二叉树的知识来实现程序功能，因此需要将输入的中序表达式转换成逆波兰序列，然后就以此序列建立二叉链表，之后通过后序遍历实现运算的功能。大概要求就是这样的。 概要设计 2.1.抽象数据类型的定义 考虑到，算符为字符型变量，算数为单精度浮点型变量。考虑先讲输入的浮点数替换为char型的符号。 Struct jd为二叉链表的节点类型。每一个节点都有字符域data，数字的话会有数值域shuzi为单精度浮点数。 struct jd{ char data; float shuzi; struct jd *next1; struct jd *next2; }; Struct haha 类型的数组ka[20]用来存放运算数，如果是运算数，就存进来，然后用字符域fuhao来代替数值域的单精度shuzi。这样一来，容易进行运算式向逆波兰序列的转换。 struct haha{ char fuhao; float shuzi; }ka[20]; 2.2.主程序流程 主函数主要有以下流程： 首先，调用zhuanhuan函数实现向逆波兰序列的转换； 然后，将得到的逆波兰序列反向，方便之后的建立二叉链表的操作； 之后，调用createBTree函数来建立二叉链表； 最后调用houxu函数进行后序遍历操作，具体操作就是运算； 输出运算结果。 具体操作由各子函数实现。 2.3.程序模块之间的调用关系 主函数直接调用zhuanhuan createBTree houxu三个子函数。 zhuanhuan函数直接调用jud函数以及in函数进行判断。 houxu函数直接调用yunsuan函数，进行后序遍历中的运算操作。 详细设计 3.1.主函数的具体实现 主函数主要调用各子函数。输入操作被放在zhuanhuan函数中，调用zhuanhuan函数实现向逆波兰序列的转换；将得到的逆波兰序列反向，方便之后的建立二叉链表的操作，这也是此主函数中唯一的需要进行运算的程序段；调用createBTree函数来建立二叉链表；最后调用houxu函数进行后序遍历操作，具体操作就是运算。而输出操作仍在主函数内进行。 具体程序如下所示： int main(){ struct jd *T; flag=0; T=(struct jd *)malloc(sizeof(struct jd)); char *b,a[100],*t; int i; b=zhuanhuan(); for(t=b;*t!=\0;t++); i=0; do{t--; a[i]=*t; i++;} while(t!=b); a[i]=\0;//完成逆波兰式的逆向 T=createBTree(T,a); printf(\n); houxu(T);printf(\n%g\n,result); return 0; } 3.2.子函数的具体实现 char *zhuanhuan(); 此函数功能比较强大，既包含了输入操作部分，也包含了将数值转换为符号进行存储的算法，以及由运算式转换到逆波兰序列的算法。 首先输入运算式，判断是否为数字，将数字存入ka[20]数组的数值域，并用符号代替数值，产生新的用符号表示的运算式。 然后用字符