简易计算器二叉树重点讲义资料

实验三——简易计算器（二叉树）05111341 班李凌豪 1120131263 1．需求分析1.1. 问题重述（1）问题描述由键盘输入一算术表达式， 以中缀形式输入， 试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。（2）基本要求a．要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。b．将中缀表达式转换成二叉表达式树。c．后序遍历求出表达式的值（3）数据结构与算法分析一棵表达式树， 它的树叶是操作数， 如常量或变量名字， 而其他的结点为操作符。a．建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前搜索， 找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。 注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树， 右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。b．求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值， 最后读取根结点中的运算符， 以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。（4）测试1.2. 问题分析本实验要求我们编写一个程序，利用二叉树， 实现简易计算器的功能。 实现实数范围内的四则混合运算， 而且要考虑括号对运算顺序的影响。而且，题目要求用二叉树的知识来实现程序功能， 因此需要将输入的中序表达式转换成逆波兰序列，然后就以此序列建立二叉链表，之后通过后序遍历实现运算的功能。大概要求就是这样的。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 函数实现向逆波兰序列的转换；然后...