数据结构课程实验报告-实验5HUNAN UNIVERSITY 课程实习报告题目：四则运算表达式求值学生姓名康小雪学生学号 20090810310专业班级计科三班指导老师李晓鸿完成日期2010-10-24一、需求分析1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误2．.输入的表达式包含数字和运算符及括号，之间用空格隔开3．数字可以为整数和小数4．运算结果保留两位小数输入输出举例输入：21+23*（12-6）输出：21 23 12 6 -*+二、概要设计在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。
最后用堆栈来实现后缀表达式的计算。
抽象数据类型二叉树ADT BiTree{数据对象D：D是具有相同特性的数据元素集合数据关系R：若D为空集，则R为空集，则称BinaryTree 为空二叉树；若D不为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集；（3）若D1≠空集，则D1中存在唯一元素x1，<root，x1>∈H,且存在D1shang deguanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，<root，xr>∈H，且存在Dr上的关系Hr∈H;H={<root,x1>,<root,xr>,H1,Hr};（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树基本操作P:InitBiTree（&T）操作结果：构造空二叉树TDestroyBiTree（&T）初始条件：二叉树T存在操作结果：销毁二叉树TCreateBiTree（&T，definition）初始条件：definition给出二叉树T的定义操作结果：按definition构造二叉树T ClearBiTree（&T）初始条件：二叉树T存在操作结果：将二叉树T清空为空树TreeBiEmpty(T)初始条件：二叉树T存在操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSETreeBiDepth（T）初始条件：二叉树T存在操作结果：返回二叉树T的深度Root（T）初始条件：二叉树T存在操作结果：返回T的根Value（T,cur_e）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：返回cur_e的值Assign（T, cur_e，value）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：结点cur_e赋值为valueParent（T,cur_e）初始条件：而擦树T存在，cur_e是T中的某个结点操作结果：若cur_e是非根结点，则返回它的双亲，否则函数值为空LeftChild（T，cur_e）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回空RightChild（&T,&p,i）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为空LeftSibling（T,e）初始条件：二叉树T存在，e是T中的某个结点操作结果：返回e的左兄弟，若e是T的左孩子或无左兄弟，返回空RightSibling（T,e）初始条件：二叉树T存在，e是T中的某个结点操作结果：返回e的右兄弟，若e是T的右孩子或无右兄弟，返回空InsertChild（&T,&p,I,c）初始条件：二叉树T存在，p指向T中某个结点，1<=i<=p所指结点的度+1，非空树c与T 不相交操作结果：插入c为T中p指结点的第i棵子树DeleteChild（&T,&p,i）初始条件：树T存在，p指向T中某个结点，1<=i<=p所值结点的度操作结果：删除T中p所指结点的第i棵子树PreOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，Visit是对界定操作的应用函数操作结果：先序遍历T，对每个结点调用函数visit（）一次且仅一次，一旦visit()失败，则操作失败InOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，Visit是对界定操作的应用函数操作结果：中序遍历T，对每个结点调用函数visit（）一次且仅一次，一旦visit()失败，则操作失败PostOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，Visit是对界定操作的应用函数操作结果：后序遍历T，对每个结点调用函数visit（）一次且仅一次，一旦visit()失败，则操作失败}ADT Tree堆栈ADT Stack{数据对象：D={aa i i|∈ElemType,i=1,2,…,n,n>=0}数据关系：R1={a a a a i1i i 1i |，，--><∈D,i=2,…,n} 基本操作： InitStack(&S)操作结果：构造一个空栈SDestroyStack （&S ）初始条件：栈S 已存在操作结果：栈S 被销毁ClearStack （&S ）初始条件：栈S 已存在操作结果：栈S 清为空栈StackEmpty （S ）初始条件：栈S 已存在操作结果：若S 为空栈，则返回TRUE,否则FALSEStackLength （S ）初始条件：栈S 已存在操作结果：返回S 元素的个数，即栈的长度 GeTop （S,&e ）初始条件：栈S 已存在且非空操作结果：用e 返回S 的栈顶元素Push （&S ，e ）初始条件：栈S 已存在操作结果：插入元素e为新的栈顶元素Pop（&S,&e）初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并返回e StackTraverse（S,visit()）初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败}ADT Stack算法的基本思想以(A+B)*(C-D/E)这样一个表达式为列求它的后缀表达式按照优先级加上括号，得到：(A+B)*(C-(D/E))然后从最外层括号开始，依次转化成二叉树1、根是* ，左子树(A+B)，右子树(C-(D/E))2、右子树的根- ，右子树的左子树C，右子树的右子树(D/E)3、(A+B)的根+，左子树A ，右子树B4、(D/E)的根/ ，左子树D，右子树E可以画出表达式对应的2叉树，操作数作为叶子节点，操作符作为非叶子节点,如图所示。
再逆序遍历二叉树可得逆波兰表达式为：AB+CDE/-*利用堆栈的方法计算后缀表达式的值程序的流程程序由三个模块组成：（1）输入模块：在主函数中输入中缀表达式（2）转换模块：将中缀表达式转换为后缀表达式，并打印（3）计算模块：生成的后缀表达式用于计算，打印最后结果三、详细设计物理数据类型二叉树#define Max_TREE_SIZE 100Typedef TElemType SqBiTree[MAX_TREE_SIZE];SqBiTree bt;堆栈#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2typedef float SElemtype;typedef int Status;算法的具体步骤//基本操作的函数原型//二叉树的存储结构表示Typedef struct BiTNode{TElemType data;Srtuct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//基本操作的函数原型说明Status CreatBiTree(BiTree &T)//按先序次序插入二叉树中结点的值（一个字符）//构造二叉链表表示二叉树TStatus PreOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）//采用二叉链表的存储结构，Visit是对结点操作的应用函数//先序遍历二叉树，对每个结点调用且仅调用一次Visit函数//一旦Visit函数失败则操作失败Status InOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）//采用二叉链表的存储结构，Visit是对结点操作的应用函数//中序遍历二叉树，对每个结点调用且仅调用一次Visit函数//一旦Visit函数失败则操作失败Status PostOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）//采用二叉链表的存储结构，Visit是对结点操作的应用函数//后序遍历二叉树，对每个结点调用且仅调用一次Visit函数//一旦Visit函数失败则操作失败//堆栈的存储结构表示typedef struct{SElemtype * base;SElemtype * top;int stacksize;} SqStack;Status InitStack(SqStack &S){S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype ));if (! S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}int StackLength(SqStack S){//获得堆栈元素的个数//填空return S.top-S.base;}Status Push(SqStack &S, SElemtype e) {//入栈//填空S.top++;*(S.top)=e;return true;}Status Pop(SqStack &S, SElemtype &e) {//出栈//填空if(S.top<S.base) return false ;e=*(S.top);S.top--;return true;}算法的时空分析遍历所有的结点上限是O(n),故此算法的增长率上限为O(n)输入和输出的格式请输入中缀表达式：//输出//等待输入//输出后缀表达式后缀表达式：//输出结果运算结果为：四、调试分析略。