课程设计报告-表达式类型的实现-方锐洲

课程设计报告-表达式类型的实现-方锐洲数据结构课程设计报告第4页共84页<<数据结构>>课程设计表达式类型的实现学院计算机学院专业计算机科学与技术年级班别2006级01班学号3106006394学生姓名方锐洲辅导教师__吴伟民_______成绩_____________2008年九、附录：程序清单19-35一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。【基本要求】【一】【必做部分】假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作：（1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。（2）WriteExpr(E)――用带括号的中缀表达式输出表达式E。（3）Assign(V，c)――实现对变量V的赋值（V=c），变量的初值为0。（4）Value(E)――对算术表达式E求值。（5）CompoundExpr(p,E1,E2)――构造一个新的复合表达式（E1）p（E2）。【二】【选做部分】（1）以表达式的原书写形式输入，支持大于0的正整数常量；（2）增加常数合并操作MergeConst(E)——合并表达式E中所有常数运算。例如，对表达式E=(2+3-a)*(b+3*4)进行合并常数的操作后，求得E=(5-a)*(b+12)【测试数据】分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。还有很多测试的数据，详细请见附上的文件Test.txt。二、概要设计1、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/ #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW0 typedefintStatus; 2、表达式的抽象数据类型定义ADTExpression{数据对象D：D是具有数值的常量C和没有数值的变量V；数据关系：R={<(V或者C)P(V或者C)>|V,C∈D,<(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E}基本操作：StatusInput_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。voidjudge_value(&E,&string,i)初始条件：树E存在，表达式的前缀字符串string存在；操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整型；否则，存为字符型。StatusReadExpr(&E,&exprstring)初始条件：表达式的前缀形式字符串exprstring存在；操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK，否则返回ERROR。StatusPri_Compare(c1,c2)初始条件：c1和c2是字符；操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR。voidWriteExpr(&E)初始条件：表达式E存在；操作条件：用带括弧的中缀表达式输入表达式E。voidAssign(&E,V,c,&flag)初始条件：表达式E存在，flag为标志是否有赋值过；操作结果：实现对表达式E中的所有变量V的赋值(V=c)。longOperate(opr1,opr,opr2)初始条件：操作数opr1和操作数opr2以及操作运算符opr;操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。StatusCheck(E)初始条件：表达式E存在；操作结果：检查表达式E是否还存在没有赋值的变量，以便求算数表达式E的值。longValue(E)初始条件：表达式E存在；操作结果：对算术表达式求值，返回求到的结果。voidCompoundExpr(P,&E1,E2)初始条件：表达式E1和E2存在；操作条件：构造一个新的复合表达式(E1)P(E2)。StatusRead_Inorder_Expr(&string,&pre_expr)操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回OK，否则，返回ERROR。voidMergeConst(&E)操作结果：常数合并操作，合并表达式E中所有常数运算。}ADTExpression3、整体设计在这个课程设计中，有两个源代码文件：expression.h和expression.c。在expression.h文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作；在expression.c文件中，是实现课程设计要求的各个函数。《一》expression.h文件的整体结构1、各个存储结构的声明；2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下：对于栈SqStack:StatusInitStack(SqStack*S) /*构造一个空栈S*/StatusStackEmpty(SqStackS) /*若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusPush(SqStack*S,SElemTypee) /*插入元素e为新的栈顶元素*/StatusPop(SqStack*S,SElemType*e)/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/StatusGetTop(SqStackS,SElemType*e)/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/对于栈SqStack1:StatusInitStack1(SqStack1*S) /*构造一个空栈S*/StatusStackEmpty1(SqStack1S) /*若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusPush1(SqStack1*S,SElemType1e) /*插入元素e为新的栈顶元素*/StatusPop1(SqStack1*S,SElemType1*e) /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/StatusGetTop1(SqStack1S,SElemType1*e)/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/顺序栈的基本操作的算法见程序清单。《二》expression.c文件的整体结构1、主程序模块的整体流程可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu()如下： charmenu() { charchoice; printf("\n****************************************"); printf("\n1>>>输入正确的前缀表达式"); printf("\n2>>>带括弧的中缀表示式输出"); printf("\n3>>>对变量进行赋值"); printf("\n4>>>对算数表达式求值"); printf("\n5>>>构造一个新的复合表达式"); printf("\n6>>>以表达式的原书写形式输入"); printf("\n7>>>合并表达式中所有常数运算"); printf("\n0>>>退出"); printf("\n****************************************"); printf("\n请输入你的选择>>>>>"); choice=getche(); returnchoice; }在主函数中，采用多分支程序设计语句switch()使程序产生不同的流向，从而达到实现课程设计的各个要求。voidmain(){ while(1) { 清屏； switch(主菜单) { 根据不同的选择，调用不同的操作函数，完成各个操作； } }}2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：主程序模块主程序模块二叉树模块顺序栈SqStack模块顺序栈SqStack1模块主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。三、详细设计1、二叉树的存储类型/*二叉树结点类型*/ typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedefstructTElemType { ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/ union { intnum;/*tag=INT时，为整型*/ charc;/*tag=CHAR时，为字符型*/ }; }TElemType; /*二叉树的二叉链表存储表示*/ typedefstructBiTNode { TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。2、顺序栈的存储类型/*栈的顺序存储表示*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*//*两个顺序栈*/typedefstructSqStack { SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack;/*顺序栈SqStack*/typedefstructSqStack1 { SElemType1*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType1*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack1;/*顺序栈SqStack1*/相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。3、表达式的基本操作StatusInput_Expr(char*string,intflag);/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*//*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式："*//*flag=1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式："*/voidjudge_value(BiTree*E,char*string,inti);/*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/StatusReadExpr(BiTree*E,char*exprstring);/*以正确的前缀表示式并构造表达式E*/StatusPri_Compare(charc1,charc2);/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/voidWriteExpr(BiTreeE);/*用带括弧的中缀表达式输入表达式*/voidAssign(BiTree*E,charV,intc,int*flag);/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/longOperate(intopr1,charopr,intopr2);/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/StatusCheck(BiTreeE);/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/longValue(BiTreeE);/*对算术表达式求值*/voidCompoundExpr(charP,BiTree*E1,BiTreeE2);/*构造一个新的复合表达式*/StatusRead_Inorder_Expr(char*string,char*pre_expr);/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr*/voidMergeConst(BiTree*E);/*常数合并操作函数，合并表达式E中所有常数运算*/下面列出部分基本操作的伪码算法，未列出的请见程序清单。其中部分基本操作的伪码算法如下：StatusReadExpr(BiTree*E,char*exprstring)StatusReadExpr(BiTree*E,char*exprstring){/*以正确的前缀表示式并构造表达式E*/ 申请根结点空间(*E)=(BiTree)malloc(sizeof(BiTNode));并且左右孩子指针置空； 表达式只有一个字符，二叉树只有根结点； 否则{judge_value(E,exprstring,0);将exprstring[0]存入二叉树的结点中InitStack(&S);/*初始化栈*/Push(&S,q);Push(&S,q);入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式for(i=1;i<len&&!StackEmpty(S);i++){申请根结点空间p=(BiTree)malloc(sizeof(BiTNode));并且左右孩子指针置空；if(exprstring[i]为运算符)运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走;else不是运算符，运算符出栈;}根据StackEmpty(S)&&i>=len判断输入的表达式是正确的；正确返回OK，错误返回ERROR;}}voidWriteExpr(BiTreeE)voidWriteExpr(BiTreeE){/*用带括弧的中缀表达式输入表达式*/ if(E)/*树不为空*/ { 先递归左子树;WriteExpr(E->lchild); 其中要考虑何时带括弧输出： if(Pri_Compare(E->data.c,E->lchild->data.c))E->data.c比E->lchild->data.c优先,带括弧输出左子树;访问输出根结点的值;后递归右子树;WriteExpr(E->lchild);其中要考虑何时带括弧输出： if(Pri_Compare(E->data.c,E->lchild->data.c))E->data.c比E->lchild->data.c优先,带括弧输出右子树;}}voidAssign(BiTree*E,charV,intc,int*flag)voidAssign(BiTree*E,charV,intc,int*flag){/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ if(*E)/*树不空*/ { if((*E)->data.tag==CHAR&&(*E)->data.c==V){如果找到要赋值的变量，赋值；*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/}}longOperate(intopr1,charopr,intopr2)longOperate(intopr1,charopr,intopr2){/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ switch(opr){ 根据不同的运算符，进入不同分支求出result； 后返回result;}}StatusCheck(BiTreeE)StatusCheck(BiTreeE){/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/if(E&&E->data.tag==CHAR)/*树不为空*/{ 如果找到没有赋值的变量，返回ERROR； if(Check(E->lchild))/*递归左子树*/ Check(E->rchild);/*递归右子树*/}}longValue(BiTreeE)longValue(BiTreeE);{/*对算术表达式求值*/if(E)/*树不为空*/{ 如果是叶子结点，返回叶子的结点的值； returnOperate(Value(E->lchild),E->data.c,Value(E->rchild));后根遍历的次序对表达式求值；}}voidCompoundExpr(charP,BiTree*E1,BiTreeE2)voidCompoundExpr(charP,BiTree*E1,BiTreeE2);{/*构造一个新的复合表达式*/ E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->lchild=(*E1);/*结点的左孩子为E1*/ E->rchild=E2;/*结点的右孩子为E2*/ (*E1)=E;/*(*E1)为根结点*/}StatusRead_Inorder_Expr(char*string,char*pre_expr)StatusRead_Inorder_Expr(char*string,char*pre_expr);{/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr*/InitStack1(&S);/*初始栈*/c=string[len-1];从字符串的最后一个字符开始向前扫描,len=strlen(string);while(!StackEmpty1(S)&&i>=0)/*栈不为空且i大于等于0*/{ if(c=='(')字符为'(',Pop1(&S,&c);while(c!=')')假如c不为')',出栈;elseif(c==')')字符为')'，入栈,Push1(&S,c);elseif(c>='0'&&c<='9')字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小;elseif((c>='a'&&c<='z')||(c>='A'&&c<='Z'))字符为'a'-'z'或'A'-'Z'之间的变量;elseif(c=='*'||c=='/')字符为运算符'*'或'/'比较优先级，后确定是入栈还是出栈；elseif(c=='+'||c=='-')字符为运算符'+'或'-'比较优先级，后确定是入栈还是出栈；elseif(c=='^')字符为运算符'^'优先级最大，不用比较，直接入栈；else{printf("\n输入的表达式有误！");returnERROR;}其他字符，错误，返回ERROR。下一个字符，继续循环。}*pre_expr='\0';/*字符串结束符*/判断构造是否成功，成功返回OK；否则返回ERROR;}voidMergeConst(BiTree*E)voidMergeConst(BiTree*E);{/*常数合并操作函数，合并表达式E中所有常数运算*/ if((*E)->lchild&&(*E)->rchild)左右孩子不为空 { if((*E)->lchild->data.tag==INT&&(*E)->rchild->data.tag==INT)假如左右孩子为常量，合并,并且删除常量的结点； else { MergeConst(&((*E)->lchild));/*递归左孩子*/ MergeConst(&((*E)->rchild));/*递归右孩子*/ } }}4、主程序和其他伪码算法voidmain(){ while(1) { switch(menu()) { case'1':/*输入正确的前缀表达式*/ if(Input_Expr(Expr_String,0))输入正确的前缀表达式 if(ReadExpr(&E,Expr_String))构造表达式 {flag=1;printf("\n表达式构造成功！");} case'2':/*带括弧的中缀表示式输出*/ if(flag==1)WriteExpr(E); elseprintf("\n表达式未构造成功！请构造成功的表达式！"); case'3':/*对变量进行赋值*/ if(flag==1) { flushall();/*清理缓冲区*/ V=getchar(); scanf(&c); Assign(&E,V,c,&Assign_flag); } elseprintf("\n表达式未构造成功！请构造成功的表达式！"); case'4':/*对算数表达式求值*/ if(flag==1) { if(Check(E)) {result=Value(E);WriteExpr(E);printf(result);} } elseprintf("\n表达式未构造成功！请构造成功的表达式！"); case'5':/*构造一个新的复合表达式*/ if(flag==1) { flushall();/*清理缓冲区*/ if(Input_Expr(string,1)) { if(Read_Inorder_Expr(string,Expr_String)) {/*按原表达式形式输入*/ reversal_string(Expr_String); if(ReadExpr(&E1,Expr_String)) {flag=1;P=getchar(); CompoundExpr(P,&E,E1); } elseprintf("\n复合新的表达式失败！请按任意键返回主菜单！");}}} case'6':/*以表达式的原书写形式输入*/ if(Input_Expr(string,1)) if(Read_Inorder_Expr(string,Expr_String)) { reversal_string(Expr_String); if(ReadExpr(&E,Expr_String)) {flag=1;printf("\n表达式构造成功！");} } case'7':/*合并表达式中所有常数运算*/ if(flag==1)MergeConst(&E); case'0':/*退出*/}}}5、函数的调用关系除了主函数main()外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。四、设计和调试分析1、在起初设计上，针对前缀表达式的要求构造表达式E，常量的范围限定在0-9之间，后在这个构造表达式的架构上逐个逐个实现对表达式上的操作；后扩展到以表达式的原书写形式输入，整体架构是不变的，只是增加一些细节的处理功能。这样的设计从开始到最后都处于可扩展的模块化设计。2、在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。3、在对各个功能操作的实现上，时间复杂度大多数是O(n)，空间上增加了辅助栈，空间复杂度为O(n+s)。而在以原表达式形式输入操作上，实际上是对字符串的操作，将一串原表达式字符串处理为前缀表达式字符串而已，算法时间复杂度取决于输入的字符串的长度n，即O(n)，空间复杂度为O(2n+s)。整体的算法设计没有什么可取之处，对于减少时间复杂度和空间复杂度上没有什么细细考虑。4、在调试的过程中，花费时间最为多的是对输入错误表达式的出错处理，更改增加的代码几乎都是为了出错处理，但是，觉得这样的调试才更能锻炼一个人的编程能力。课程设计注重的不单单只是基本程序的完成，更多注重的是出错处理和界面的美化！五、用户手册1、本程序的运行环境为DOS操作系统，执行文件为：expression.exe；2、进入演示程序后首先出现一个主菜单，主菜单界面如下：3、之后输入你的选择，进入你所要进行的操作中。六、测试《一》选择‘1’进入测试输入正确的前缀表达式操作1、输入的前缀表达式为一个不大于9常量：‘82、输入前缀表达式为一个变量：‘Z’3、输入前缀表达式为一个简单的运算表达式：‘-914、输入前缀表达式为一个较为复杂的、带有变量的表达式：‘+++*3^x3*2^x2x65、输入前缀表达式‘*-+23a+b*34’6、输入错误的前缀表达式：‘+999’和‘+*5^x2*8x&《二》选择‘3’进入测试对变量的赋值1、对前缀表达式‘3*x^3+2*x^2+x+6’中变量x进行赋值2、对前缀表达式‘a+b*c’中的变量b进行赋值，赋值为63、对前缀表达式‘5*x^2+8*x’中不存在的变量y进行赋值，赋值为4《三》选择‘4’进入测试求算数表达式的值1、求算数表达式‘9+8’2、求算数表达式‘（65+98）*（9^2+(21-96)）’的值3、求仍存在变量的表达式‘3+a*9-6’《四》选择‘5’进入构造新的复合表达式1、未构造表达式E时2、已构造了表达式E时《五》选择‘6’进入以原表达式形式输入构造表达式1、构造表达式‘6*a+9/b-(a+2^3)’输出的结果少了括弧，这个是程序中的一个BUG，程序的判定带括弧输出表达式时判断两个优先级别时的一个很大的BUG，一个本人自己没法解决的BUG。2、构造表达式‘(((3+2)*9)-(6/3)*9+1)/8+18*3输出的结果简化了多余的括弧，这一点是一个很大的优化。3、构造表达式‘66++’，出错处理4、构造表达式‘6+-b+9*9’5、构造表达式‘9+a+(6+5))*a’,出错处理多余输入的括弧6、构造表达式‘6#9+8*6’《六》选择‘7’进入合并常数操作1、构造表达式‘(2+3-a)*(b+3*4)’，后合并常数操作2、构造表达式‘（3+3*4）*(1*2+8/2)’，经过多次合并，得出最后结果这个合并常数操作唯一的缺点就是要多次操作，但是，这个缺点也不能说为缺点，它可以很清晰的反映出表达式求值的步骤！经过对各个操作的测试，可以这样总结的说，基本完成了课程设计的要求，虽说其中有一些操作还存在BUG需要去完善改进。七、课程设计的心得和体会以及问题此次课程设计相对于我来说，难度适中，相对于这个学期写的那些小算法来说，这个课程设计能充分发挥出学习数据结构后的能力；而相对于之前做的设计性实验，又有了实际的应用，现实应用度增加。从接触C语言编程到现在，我就觉得：编程不是简简单单的写出程序，更多的是出错处理和界面设计。这次课程设计中，更让我深刻体会到这个道理。编出大体的程序架构，花费了我的时间不多，而花费了我很多时间的是在调试和测试数据上！这次课程设计，不仅训练了我对VisualC++6.0的调试器的操作的熟练度；而且，让我在发现问题解决问题中深刻地理解到完善程序的重要性。这次课程设计在技术上的学习上，我觉得，让我更懂得递归！递归的使用更加熟练，递归的分析更加清晰，递归的思想更加深化！做课程设计，我觉得，第一点是架构，一个好的架构，可以让细节更完善；在这次课程设计中，我首先确定的是一个架构——前缀表达式构造表达式为架构——其余的操作都是在这个架构上增加扩充。第二点是调试测试分析，一个完善的程序是要经过千锤百炼的，也能做到更加完善；第三点是心得的总结！总的来说，这次课程设计，让我学了很多，总结了很多！八、参考文献严蔚敏，吴伟民著，数据结构（C语言版），北京：清华大学出版社，2007谭浩强著，C程序设计（第三版），北京：清华大学出版社，2005九、附录：程序清单源程序文件名清单：expression.h //包含头文件，存储结构的声明，以及两个顺序栈的基本操作exprssion.c //包含主程序和表达式的基本操作《一》文件expression.h /*头文件以及存储结构*/ #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW0 typedefintStatus; /*二叉树结点类型*/ typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedefstructTElemType { ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/ union { intnum;/*tag=INT时，为整型*/ charc;/*tag=CHAR时，为字符型*/ }; }TElemType; /*二叉树的二叉链表存储表示*/ typedefstructBiTNode { TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree; typedefBiTreeSElemType;/*栈SqStack的元素*/ typedefcharSElemType1;/*栈SqStack1的元素*/ /*栈的顺序存储表示*/ #defineSTACK_INIT_SIZE10/*存储空间初始分配量*/ #defineSTACKINCREMENT2/*存储空间分配增量*//*两个顺序栈*/ typedefstructSqStack { SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack;/*顺序栈*/ typedefstructSqStack1 { SElemType1*base;/*在栈构造之前和销毁之后，base的值为NULL*/ SElemType1*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间，以元素为单位*/ }SqStack1;/*顺序栈*/ /*顺序栈的基本操作*/ StatusInitStack(SqStack*S) {/*构造一个空栈S*/ (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK; } StatusStackEmpty(SqStackS) {/*若栈S为空栈，则返回TRUE，否则返回FALSE*/ if(S.top==S.base)returnTRUE; elsereturnFALSE; } StatusPush(SqStack*S,SElemTypee) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/ { (*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; returnOK; } StatusPop(SqStack*S,SElemType*e) {/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/ if((*S).top==(*S).base)returnERROR; *e=*--(*S).top; returnOK; } StatusGetTop(SqStackS,SElemType*e) {/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/ if(S.top>S.base) { *e=*(S.top-1); returnOK; } else returnERROR; } /*顺序栈的基本操作*/ StatusInitStack1(SqStack1*S) {/*构造一个空栈S*/ (*S).base=(SElemType1*)malloc(STACK_INIT_SIZE*sizeof(SElemType1)); if(!(*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK; } StatusStackEmpty1(SqStack1S) {/*若栈S为空栈，则返回TRUE，否则返回FALSE*/ if(S.top==S.base)returnTRUE; elsereturnFALSE; } StatusPush1(SqStack1*S,SElemType1e) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/ { (*S).base=(SElemType1*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1)); if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; returnOK; } StatusPop1(SqStack1*S,SElemType1*e) {/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/ if((*S).top==(*S).base)returnERROR; *e=*--(*S).top; returnOK; } StatusGetTop1(SqStack1S,SElemType1*e) {/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/ if(S.top>S.base) { *e=*(S.top-1); returnOK; } else returnERROR; }《二》文件expression.c #include"expression.h" /*全局变量*/ intsave_number[31];/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为30个，0单元不用*/ charExpr_String[30];/*存放表达式的字符串*/ /*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/ /*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式："*/ /*flag=1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式："*/ StatusInput_Expr(char*string,intflag) { if(flag==0)printf("\n请输入正确的前缀表示式："); elseprintf("\n请以表达式的原书写形式输入正确表示式："); flushall();/*清理缓冲区*/ gets(string);/*从键盘输入一串字符串作为表达式*/ if(strlen(string)==1)/*输入的表达式字符串长度为1*/ if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/ {printf("\n表达式只有一个字符，为运算符，错误！");returnERROR;} elseif((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z')) /*输入的表达式只有一个数字或字符*/ {printf("\n表达式只有一个字符！");returnOK;} else{printf("\n输入的字符不是运算符也不是变量常量，错误！");returnERROR;} returnOK; } /*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/ voidjudge_value(BiTree*E,char*string,inti) { if(string[i]>='0'&&string[i]<='9')/*为常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} elseif(string[i]>=1&&string[i]<=20)/*为常量，常量存于数组save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*为变量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];} } /*以正确的前缀表示式并构造表达式E*/ StatusReadExpr(BiTree*E,char*exprstring) { SqStackS; inti,len;/*len为表达式的长度*/ BiTreep,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len赋值为表达式的长度*/ if(len==1)/*表达式长度为1时，二叉树只有根结点*/ judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ else { judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ InitStack(&S);/*初始化栈*/ q=(*E); Push(&S,q);/*入栈*/ Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/ for(i=1;i<len&&!StackEmpty(S);i++) { p=(BiTree)malloc(sizeof(BiTNode)); judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/ if(!q->lchild) {q->lchild=p;Push(&S,p);q=p;} else {q->rchild=p;Push(&S,p);q=p;} } else/*不是运算符，运算符出栈*/ { if(!q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->rchild=p;Pop(&S,&q);} } } if(StackEmpty(S)&&i>=len) returnOK;/*栈空且i>=len，说明输入的表达式是正确的*/ else /*输入的表达式是错误的*/ { printf("\n输入的表达式有误！"); returnERROR; } } } /*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/ StatusPri_Compare(charc1,charc2) { if((c1=='^'||c1=='*'||c1=='-'||c1=='+'||c1=='/')&&(c2=='^'||c2=='*'||c2=='-'||c2=='+'||c2=='/')) {/*c1和c2为运算符*/ if(c1=='^')/*c1为指数运算符，则当c2不为'^'时，c1比c2优先*/ { if(c2!='^')returnOK; elsereturnERROR; } elseif(c1=='*'||c1=='/')/*c1为乘法或除法运算符，则当c2为'+'或'-'，c1比c2优先*/ { if(c2=='^'||c2=='*'||c2=='/')returnERROR; elsereturnOK; } elsereturnERROR;/*其余，c1不比c2优先*/ } elsereturnERROR;/*c1和c2不是运算符*/ } /*用带括弧的中缀表达式输入表达式*/ voidWriteExpr(BiTreeE) { if(E)/*树不为空*/ { /*先递归左子树*/ if(E->lchild&&E->lchild->data.tag==CHAR)/*E的左孩子不为空，且左孩子为字符*/ { if(Pri_Compare(E->data.c,E->lchild->data.c))/*E->data.c比E->lchild->data.c优先*/ {printf("(");WriteExpr(E->lchild);printf(")");}/*带括弧输出左子树*/ elseWriteExpr(E->lchild);/*否则，不带括弧输出左子树*/ } elseWriteExpr(E->lchild);/*否则，输出左子树*/ /*访问输出根结点的值*/ if(E->data.tag==INT){printf("%d",E->data.num);} elseprintf("%c",E->data.c); /*后递归右子树*/ if(E->rchild&&E->rchild->data.tag==CHAR)/*E的右孩子不为空，且右孩子为字符*/ { if(Pri_Compare(E->data.c,E->rchild->data.c))/*E->data.c比E->rchild->data.c优先*/ {printf("(");WriteExpr(E->rchild);printf(")");}/*带括弧输出右子树*/ elseWriteExpr(E->rchild);/*否则，不带括弧输出右子树*/ } elseWriteExpr(E->rchild);/*否则，输出右子树*/ } } /*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/ voidAssign(BiTree*E,charV,intc,int*flag) { if(*E) { if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量，赋值*/ {(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/ } } /*指数运算函数，底数为x，指数为exp*/ longpower(intx,intexp) { longresult; inti; for(i=1,result=1;i<=exp;i++) result*=x; returnresult; } /*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/ longOperate(intopr1,charopr,intopr2) { longresult; switch(opr) { case'+':/*加法*/ result=opr1+opr2; returnresult;break; case'-':/*减法*/ result=opr1-opr2; returnresult;break; case'*':/*乘法*/ result=opr1*opr2; returnresult;break; case'/':/*除法，除法是在整型类型上的除法*/ result=opr1/opr2; returnresult;break; case'^':/*指数运算*/ result=power(opr1,opr2); returnresult;break; default:break; } } /*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/ StatusCheck(BiTreeE) { if(E&&E->data.tag==CHAR)/*树不为空*/ { if(E->data.c!='*'&&E->data.c!='^'&&E->data.c!='-'&&E->data.c!='+'&&E->data.c!='/') {printf("\n表达式中仍存在变量没有赋值！没法求出表达式的值！");returnERROR;} /*存在变量，提示信息，后返回ERROR*/ if(Check(E->lchild))/*递归左子树*/ Check(E->rchild);/*递归右子树*/ } } /*对算术表达式求值*/ longValue(BiTreeE) { if(E)/*树不为空*/ { if(!E->lchild&&!E->rchild&&E->data.tag==INT)return(E->data.num); /*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/ returnOperate(Value(E->lchild),E->data.c,Value(E->rchild)); /*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了Value()函数求左子树的值和右子树的值*/ } } /*构造一个新的复合表达式*/ voidCompoundExpr(charP,BiTree*E1,BiTreeE2) { BiTreeE; E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->data.tag=CHAR; E->data.c=P;/*申请到的结点值为P*/ E->lchild=(*E1);/*结点的左孩子为E1*/ E->rchild=E2;/*结点的右孩子为E2*/ (*E1)=E;/*(*E1)为根结点*/ printf("\n表达式E复合成功！其表达式变为：\n"); WriteExpr(E);/*输出复合好的表达式*/ } /*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr*/ /*后调用reversal_string()函数反转得到前缀表达式pre_expr*/ StatusRead_Inorder_Expr(char*string,char*pre_expr) { inti,j,len,char_number=1;/*len表示字符串string的长度，char_number是记录数组save_number[]的个数*/ intnumber;/*保存大于9的常量*/ charc,c1; SqStack1S;/*栈定义*/ InitStack1(&S);/*初始栈*/ Push1(&S,'#');/*先将字符'#'入栈，用来表示作为栈的最底一个元素*/ len=strlen(string);/*len为字符串string的长度*/ c=string[len-1];/*从字符串的最后一个字符开始向前扫描*/ i=len-1; while(!StackEmpty1(S)&&i>=0)/*栈不为空且i大于等于0*/ { if(c=='(')/*字符为'('*/ { Pop1(&S,&c);/*出栈，赋值给c*/ while(c!=')')/*假如c不为')',出栈*/ { *pre_expr++=c; if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#')Pop1(&S,&c); else{printf("\n输入的表达式有误!");returnERROR;} } } elseif(c==')')/*字符为')'，入栈*/ { Push1(&S,c); } elseif(c>='0'&&c<='9')/*字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小*/ { number=c-48;/*number为第一个常量字符的ASCII码-48*/ for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循环扫描string前一个字符，求出常量后赋给number*/ { number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/ c1=string[i-2]; } save_number[char_number]=number;/*将number存入到数组save_number中，下标为char_number*/ *pre_expr++=char_number++; } elseif((c>='a'&&c<='z')||(c>='A'&&c<='Z'))/*字符为'a'-'z'或'A'-'Z'之间的变量*/ {/*string下一个字符不能为常量或变量，否则，出错*/ if((string[i-1]>='0'&&string[i-1]<='9')||(string[i-1]>='A'&&string[i-1]<='Z')||(string[i-1]>='a'&&string[i-1]<='z')) {printf("\n输入的表达式有误！");returnERROR;} else *pre_expr++=c; } elseif(c=='*'||c=='/')/*字符为运算符'*'或'/'*/ { while(GetTop1(S,&c1)&&(c1=='^'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈字符c*/ } elseif(c=='+'||c=='-')/*字符为运算符'+'或'-'*/ { while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'||c1=='/'))/*将c与栈顶的字符c1比较优先级*/ {Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈运算符c*/ } elseif(c=='^')/*字符为运算符'^'*/ { Push1(&S,c);/*入栈运算符'^'*/ } else{printf("\n输入的表达式有误！");returnERROR;}/*其他字符，错误，返回ERROR*/ i--;/*下一个字符*/ if(i>=0)c=string[i];/*i不小于0，c=string[i]循环下一个字符*/ else/*否则，将清空栈*/ while(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') {Pop1(&S,&c);*pre_expr++=c;} } Pop1(&S,&c);/*将'#'出栈*/ *pre_expr='\0';/*字符串结束符*/ if(i<0&&StackEmpty1(S))returnOK; elsereturnERROR; } /*将字符串exprstring反转过来*/ voidreversal_string(char*exprstring) { intlen,i,j; chartemp; len=strlen(exprstring);/*len为exprstring的长度*/ for(i=0,j=len-1;i<j;i++,j--)/*字符串前后两个字符对换*/ { temp=exprstring[i]; exprstring[i]=exprstring[j]; exprstring[j]=temp; } } /*常数合并操作函数，合并表达式E中所有常数运算*/ voidMergeConst(BiTree*E) { longresult; if((*E)->lchild&&(*E)->rchild)/*左右孩子不为空*/ { if((*E)->lchild->data.tag==INT&&(*E)->rchild->data.tag==INT)/*假如左右孩子为常量，合并*/ { result=Operate((*E)->lchild->data.num,(*E)->data.c,(*E)->rchild->data.num);/*常数合并运算，调用Operate()函数求值*/ (*E)->data.tag=INT;(*E)->data.num=result;/*修改之前的运算符为常量*/ free((*E)->lchild);/*释放左孩子*/ free((*E)->rchild);/*释放右孩子*/ (*E)->lchild=(*E)->rchild=NULL;/*左右孩子置空*/ } else { MergeConst(&((*E)->lchild));/*递归左孩子*/ MergeConst(&((*E)->rchild));/*递归右孩子*/ } } } /*主菜单*/ charmenu() { charchoice; printf("\n\t****************************************"); printf("\n\t计算机学院计算机科学与技术06级01班"); printf("\n\t学号：3106006394姓名：方锐洲"); printf("\n\t****************************************"); printf("\n\t***********表达式类型的实现*************"); printf("\n\t1>>>输入正确的前缀表达式"); printf("\n\t2>>>带括弧的中缀表示式输出"); printf("\n\t3>>>对变量进行赋值"); printf("\n\t4>>>对算数表达式求值"); printf("\n\t5>>>构造一个新的复合表达式"); printf("\n\t6>>>以表达式的原书写形式输入"); printf("\n\t7>>>合并表达式中所有常数运算"); printf("\n\t0>>>退出"); printf("\n\t****************************************"); printf("\n\t请输入你的选择>>>>>"); choice=getche(); returnchoice; } /*主函数*/ voidmain() { BiTreeE,E1;/*两个表达式E和E1*/ intflag=0;/*表达式E构造标志，为0表示未构造，为1表示已构造*/ longresult;/*保存算数表达式运算结果*/ charV,P; intc; charstring[30]; while(1) { system("cls"); switch(menu()) { case'1':/*1>>>输入正确的前缀表达式*/ printf("\n\t*************************输入提示信息************************"); printf("\n\t输入正确的前缀表达式的要求："); printf("\n\t\t【变量】a-z或A-Z"); printf("\n\t\t【常量】0-9，不能超过9"); printf("\n\t\t【运算符】+,-,*,/,^(乘幂)"); printf("\n\t请输入正确的前缀表达式，后按回车键存入缓冲区，否则可能会出错！"); printf("\n\t*************************************************************"); if(Input_Expr(Expr_String,0)) if(ReadExpr(&E,Expr_String)) {flag=1;printf("\n表达式构造成功！\n输入的带括弧的中缀表达式：");WriteExpr(E);} getch(); break; case'2':/*2>>>带括弧的中缀表示式输出*/ printf("\n\t********************输出说明信息***********************************"); printf("\n\t输出带括弧的中缀表达式："); printf("\n\t【1】如果表达式已经构造成功的，输出表达式；"); printf("\n\t【2】如果表达式还未构造成功的，请返回主菜单选择构造表达式；"); printf("\n\t【注】其中要注意的是，可能有一些表达式构造时没有办法判断为有误，"); printf("\n\t如果输出不是你想得到的，说明你之前输入的表达式有误，请重新构造！"); printf("\n\t********************************************************************"); if(flag==1){printf("\n带括弧的中缀表达式为：");WriteExpr(E);} elseprintf("\n表达式未构造成功！请构造成功的表达式！"); getch(); break; case'3':/*3>>>对变量进行赋值*/ printf("\n\t********************赋值操作说明信息***********************************"); printf("\n\t赋值操作：实现对表达式中的某一个变量V的赋值，即使V=C，C为一整数"); printf("\n\t【1】根据输出的表达式，输入要赋值的变量V，只能输入一个字符，否则出错"); printf("\n\t【2】输入要将变量