数据结构实验报告三
——简易计算器（二叉树）
姓名：任子龙 学号：********** 班级：********
一、需求分析
（1）问题描述
由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该二叉树的后序遍历求出计算表达式的值。
（2）基本要求
a．要求对输入的表达式能判断出是否合法，不合法要有错误提示信息。
b．将中缀表达式转换成二叉表达式树。
c．后序遍历求出表达式的值。
（3）数据结构与算法分析
一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。
a．建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。
b．求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。
（4）测试
a.加减运算
输入：6+9-5 输出：10
b.乘除运算
输入：5.6*2.7/2 输出：7.56
c.四则混合运算
输入：(2+3)*8-3/2 输出：23.5
d.非法输入
输入：（5+6（*5 输出：括号不匹配！
1.2问题分析
与之前利用栈实现计算器功能不同，本实验采取的方法是：将中缀表达式转换成一棵二叉表达式树，通过对该树的后序遍历求出计算表达式的值。所以，实验的重点是如何“将中缀
表达式转换成一棵二叉表达式树”；
如上图所示，该二叉表达式树表示的是计算式（5+2）*3。可以看出，操作数均为叶子结点，其它结点为操作符；构建二叉树的整体思路是：（1）将中缀表达式转化为后缀表达式；（2）利用（1）中的后缀表达式，在此基础上构建二叉表达式树。
最后的求值，可以通过递归调用函数，后序遍历二叉树来完成。
物华天宝的意思二、概要设计
2.1抽象数据类型定义
本程序主要用到的数据结构是二叉链表，所以先行定义链表结点，其中每一个节点包含两个数据域和两个指针域，数据域分别存放char型变量和float型变量，相对应是运算符和操作数；指针域分别指向两个左右孩子。
世界上最大的蟒蛇 struct node{
char data;
float number;
struct node *left;
struct node *right;
};
另外，考虑到程序还需转换后缀表达式，所以又建立了另一种结点类型变量，并定义其类型的数组array[20]：
struct oprtnumber{
char sign; //存放符号型变量
float number; //存放浮点数
玫瑰花的品质
}array[20];
2.2主程序流程
主函数流程如下：
int main()
{
char *b,a[100],*t;
b=convert(); //中缀表达式转为反序后缀表达式
do
{ 完成反序后缀式的逆向 ；
内眼角疼怎么回事
琴声
}
T=create(T,a); //create()函数创建二叉链表
postordertraver(T);//后序遍历进行计算
输出结果；
} //main
2.3程序模块调用关系
具体关系如下图所示：
三、详细设计
密云县3.1主函数的具体过程
int main()
{ struct node *T;
flag=0;
T=(struct node *)malloc(sizeof(struct node));
char *b,a[100],*t;
int i; b=convert(); //中缀表达式转为反序后缀表达式
for(t=b;*t!='\0';t++);
i=0;
do
{ t--;
a[i]=*t; i++;
}
while(t!=b);
a[i]='\0';//完成反序后缀式的逆向
水冷原理
T=create(T,a); //create()函数创建二叉链表
postordertraver(T);//后序遍历进行计算
printf("%g",result); //输出结果
return 0;
} //main
3.2其它函数的具体实现
char *convert();
//将运算式转换成逆后缀序列，并将该序列作为返回值；
首先输入运算式，判断是否为数字，将数字存入数组的数值域，并用符号代替数值，产生新的用符号表示的运算式。
然后用字符优先算法将算式转换为逆后缀式，将数组首地址传回给主函数。 并且在输入不合法时给予错误提示。
struct node *create(struct node *T,char d[]);
//建立二叉链表，并返回根结点
void postordertraver(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;
