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

课程设计报告-表达式类型的实现-方锐洲专业计算机科学与技术学生姓名方锐洲辅导教师吴伟民~~~~~~~~~~表达式类型的实现~~~~~~~~~~一、需求分析------------------------3三、详细设计----------------------7-13-------------------14五、用户手册------------------------1488八、参考文献------------------------195【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实【基本要求】【测试数据】/*头文件以及存储结构*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0ADTExpression{StatusInput_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串voidjudge_value(&E,&string,i)操作结果：判断字符string[i]，如StatusReadExpr(&E,&exprstring)初始条件：表达式的前缀形式字符串操作结果：以正确的前缀表示式StatusPri_Compare(c1,c2)操作结果：如果两个字符是运算符，voidWriteExpr(&E)操作条件：用带括弧的中缀表达式输voidAssign(&E,V,c,&flag)longOperate(opr1,opr,opr2)操作结果：运算符运算求值，参数StatusCheck(E)没有赋值的变量，以便求算数表达式操作结果：对算术表达式求值，返回voidCompoundExpr(P,&E1,E2)操作条件：构造一个新的复合表达式Read_Inorder_Expr(&string,&pre_ex操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串reversal_string()函数反转得到前voidMergeConst(&E)操作结果：常数合并操作，合并表达在这个课程设计中，有两个源代码文件：结构的声明和辅助存储结构的两个栈的基本操《一》expression.h文件的整2、两个除了栈名和栈存储的元素不一样的StatusInitStack(SqStack*S)/*构造一个StatusStackEmpty(SqStackS)/*若栈S为StatusPush(SqStack*S,SElemTypee)/*插StatusPop(SqStack*S,SElemType*e)/*若StatusGetTop(SqStackS,SElemType*StatusPush1(SqStack1*S,SElemType1e)StatusPop1(SqStack1*S,SElemType1*e)可以从主菜单函数可以明了的了解的程序{printf("\n****************************************");printf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\n2>>>带括弧的中缀表示3>>>对变量进行赋值4>>>对算数表达式求值5>>>构造一个新的复合6>>>以表达式的原书写7>>>合并表达式中所有printf("\n****************************************");printf("\n请输入你的选择>>>>>");choice=getche();}在主函数中，采用多分支程序设计语句voidmain(){while(1){{}}}2、本程序有四个模块，主程序模块，二叉树模主程序模块中的对于表达式的存储结构调原表达式形式输入表达式转换为前缀表达式操/*二叉树结点类型*/typedefstructTElemT{ElemTagtag;/*{INT,CHAR}指示是整型还{/*二叉树的二叉链表存储表示*/typedefstructBiTNode{二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情/*栈的顺序存储表示*//*两个顺序栈*/{SElemType*base;/*在栈构造之前和{相关的基本操作见上面的“expression.hStatusInput_Expr(char*string,intflag);/*以字符序列的形式输入语法正确的前缀/*参数flag=0表示输出的提示信息是"请/*flag=1表示输出的提示信息为"请以表达voidjudge_value(BiTree*E,char/*判断字符string[i]，如果是'0'-'9'常*exprstring);/*以正确的前缀表示式并构造表达式E*/StatusPri_Compare(charc1,charc2);voidWriteExpr(BiTreeE);/*用带括弧的中缀表达式输入表达式*//*实现对表达式中的所有变量V的赋值longOperate(intopr1,charopr,intopr2);/*运算符运算求值，参数opr1,opr2为常现不同的运算，返回运算结果*/StatusCheck(BiTreeE);/*对算术表达式求值*//*构造一个新的复合表达式*/StatusRead_Inorder_Expr(char*string,char*pre_expr);voidMergeConst(BiTree*E);{judge_value(E,exprstring,0);将exprstring[0]存入二叉树的结点中Push(&S,q);Push(&S,q);{if(Pri_Compare(E->data.c,E->lchild->d{/*实现对表达式中的所有变量V的赋值{if(E&&E->data.tag==CHAR)/*树不为空*/{{E=(BiTree)malloc(sizeof(BiTNode));/*{/*以表达式的原书写形式输入，表达式的原c=string[len-1];从字符串的最后一个字符开始向前扫描,len=strlen(string);while(!StackEmpty1(S)&&i>=0)/*栈不为{if(c=='(')字符为'(',Pop1(&S,&c);if((*E)->lchild&&(*E)->rchild)左右孩子{voidmain(){while(1){{case'1':/*输入正确的前缀表达式*/if(Input_Expr(Expr_String,0))输if(ReadExpr(&E,Expr_String))case'2':/*带括弧的中缀表示式输出*/if(flag==1)WriteExpcase'3':/*对变量进行赋值*/{flushall();/*清理缓冲区*/V=getchar();Assign(&E,V,c,&Assign_flag);}elseprintf("\n表达式未构造成case'4':/*对算数表达式求值*/{WriteExpr(E);printf(result);}}elseprintf("\n表达式未构造成case'5':/*构造一个新的复合表达式*/{flushall();/*清理缓冲区*/{if(Read_Inorder_Expr(string,Expr_Stringreversal_string(Expr_String);if(ReadExpr(&E1,Expr_String)){flag=1;P=getchar();CompoundExpr(P,&E,E1);}elseprintf("\n复合新的}}}case'6':/*以表达式的原书写形式输入if(Read_Inorder_Expr(string,Expr_String{reversal_string(Expr_String);if(ReadExpr(&E,Expr_String))}case'7':/*合并表达式中所有常数运算if(flag==1)MergeConst(&E);case'0':/*退出*/}}}除了主函数main()外，其他各个函数相对数main()调用使用的，可以简单的说，各个函1、在起初设计上，针对前缀表达式的要求在这个构造表达式的架构上逐个逐个实现对表本来以为使用递归构造表达式会很难做到出错3、在对各个功能操作的实现上，时间复杂复杂度为O(n+s)。而在以原表达式形式输入操间复杂度取决于输入的字符串的长度n，即4、在调试的过程中，花费时间最为多的是2、进入演示程序后首先出现一个主菜单，3、之后输入你的选择，进入你所要进行的《一》选择‘1’进入测试输入正确的前缀表达‘8’3、输入前缀表达式为一个简单的运算表达4、输入前缀表达式为一个较为复杂的、带6、输入错误的前缀表达式：‘+999’和‘+*5^x2*8x&’《二》选择‘3’进入测试对变量的赋值《三》选择‘4’进入测试求算数表达式的值《四》选择‘5’进入构造新的复合表达式《五》选择‘6’进入以原表达式形式输入构造1、构造表达式‘6*a+9/b-(a+2^3)’BUG，程序的判定带括弧输出表达式时判断两个‘(((3+2)*9)-(6/3)*9+1)/8+18*3’4、构造表达式‘6+-b+9*9’，出错处理《六》选择‘7’进入合并常数操作这个合并常数操作唯一的缺点就是要多次经过对各个操作的测试，可以这样总结的七、课程设计的心得和体会以及问题C++6.0的调试器的操作的熟练度；而且，让我在发现问题解决问题中深刻地理解到完善程序分析更加清晰，递归的思想更加深化！造表达式为架构——其余的操作都是在这个架exprssion.c//包含主程序和表达式的基本/*头文件以及存储结构*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0/*二叉树结点类型*/typedefstructTElemT{ElemTagtag;/*{INT,CHAR}指示是整型还{/*二叉树的二叉链表存储表示*/typedefstructBiTNode{typedefcharSElemType1;/*栈/*栈的顺序存储表示*//*两个顺序栈*/{SElemType*base;/*在栈构造之前和销{SElemType1*top;/*栈顶指针*//*顺序栈的基本操作*/StatusInitStack(SqStack*S)*)malloc(STACK_INIT_SIZE*sizeof(SElemTypeexit(OVERFLOW);/*存储分配失败*/returnOK;}StatusStackEmpty(SqStackS)if(S.top==S.base)returnTRUE;}StatusPush(SqStack*S,SElemTypee)if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/{*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/}*((*S).top)++=e;returnOK;}StatusPop(SqStack*S,SElemType*e)if((*S).top==(*S).base)return*e=*--(*S).top;returnOK;}StatusGetTop(SqStackS,SElemType*e){*e=*(S.top-1);}returnERROR;}/*顺序栈的基本操作*/StatusInitStack1(SqStack1*S)*)malloc(STACK_INIT_SIZE*sizeof(SElemTypeexit(OVERFLOW);/*存储分配失败*/returnOK;}StatusStackEmpty1(SqStack1S)if(S.top==S.base)returnTRUE;}StatusPush1(SqStack1*S,SElemType1e)if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/{*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/}*((*S).top)++=e;returnOK;}StatusPop1(SqStack1*S,SElemType1*e)if((*S).top==(*S).base)return*e=*--(*S).top;returnOK;}StatusGetTop1(SqStack1S,SElemType1{*e=*(S.top-1);}returnERROR;}#include"expression.h"intsave_number[31];/*在按原表达式输入形式中，输入的常量保存到数组save_numbercharExpr_String[30];/*存放表达式的字符/*以字符序列的形式输入语法正确的前缀表/*参数flag=0表示输出的提示信息是"请输/*flag=1表示输出的提示信息为"请以表达式{if(flag==0)printf("\n请输入正确的前flushall();/*清理缓冲区*/gets(string);/*从键盘输入一串字符串作if(strlen(string)==1)/*输入的表达式字if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/if((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z'))/*输入的表达式只有一个数字或字符}/*判断字符string[i]，如果是'0'-'9'常量voidjudge_value(BiTree*E,char{if(string[i]>='0'&&string[i]ng[i]-48;}if(string[i]>=1&&string_number[string[i]];}}/*以正确的前缀表示式并构造表达式E*/*exprstring){BiTreep,q;len=strlen(exprstring);/*len赋值为表judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/{judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/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]=='^')}else/*不是运算符，运算符出栈*/{else{q->rchild=p;Pop(&S,&q);}}}if(StackEmpty(S)&&i>=len)returnelse/*输入的表达式是错误的*/{returnERROR;}}}StatusPri_Compare(charc1,charc2){if((c1=='^'||c1=='*'||c1=='-'||c1=='+'|=='+'||c2=='/')){elsereturnERROR;}{if(c2=='^'||c2=='*'||c2=='/')returnERROR;}}}/*用带括弧的中缀表达式输入表达式*/voidWriteExpr(BiTreeE){if(E->lchild&&E->lchild->data.tag==CHAR{if(Pri_Compare(E->data.c,E->lchild->datf(")");}/*带括弧输出左子树*/}/*访问输出根结点的值*/if(E->data.tag==INT){printf("%d",E->datelseprintf("%c",E->data.c);/*后递归右子树*/if(E->rchild&&E->rchild->data.tag==CHAR{if(Pri_Compare(E->data.c,E->rchild->datf(")");}/*带括弧输出右子树*/}}}/*实现对表达式中的所有变量V的赋值{{if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量，赋值*/Assign(&((*E)->lchild),V,c,flag);/*递归Assign(&((*E)->rchild),V,c,flag);/*递归}}{for(i=1,result=1;i<=exp;i++)result*=x;returnresult;}运算，返回运算结果*/{{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;}}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表达式中仍存在变量没有赋值！没法求出表达式的值！");returnif(Check(E->lchild))/*递归左子树*/Check(E->rchild);/*递归右子树*/}}/*对算术表达式求值*/{{if(!E->lchild&&!E->rchild&&E->data.tag=Operate(Value(E->lchild),E->data.c,Value(E->rchild));}}/*构造一个新的复合表达式*/voidCompoundExpr(charP,BiTree*E1,BiTreeE2){BiTreeE;E=(BiTree)malloc(sizeof(BiTNode));/*E->data.tag=CHAR;E->data.c=P;/*申请到的结点值为P*/E->lchild=(*E1);/*结点的左孩子为E1*/E->rchild=E2;/*结点的右孩子为E2*/WriteExpr(E);/*输出复合好的表达式*/}/*后调用reversal_string()函数反转得到StatusRead_Inorder_Expr(char*string,char*pre_expr){SqStack1S;/*栈定义*/Push1(&S,'#');/*先将字符'#'入栈，用来表示作为栈的最底一个元素*/c=string[len-1];/*从字符串的最后一个{{Pop1(&S,&c);/*出栈，赋值给c*/{*pre_expr++=c;if(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#')Pop1(&S,&c);误!");returnERROR;}}}elseif(c==')')/*字符为')'，入栈*/{Push1(&S,c);}{number=c-48;/*number为第一个常量for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循环扫描string前一个{number=(c1-48)*power(10,j)+number;/*num}save_number[char_number]=number;/*将*pre_expr++=char_number++;}if((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')){printf("\n输入的表达式有误！else*pre_expr++=c;}elseif(c=='*'||c=='/')/*字符为运算{while(GetTop1(S,&c1)&&(c1=='^'))/*将c{Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1Push1(&S,c);/*入栈字符c*/}elseif(c=='+'||c=='-')/*字符为运算{while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'{Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1Push1(&S,c);/*入栈运算符c*/}elseif(c=='^')/*字符为运算符'^'*/{Push1(&S,c);/*入栈运算符'^'*/}");returnERROR;}/*其他字符，错误，返回c=string[i]循环下一个字符*/else/*否则，将清空栈*/while(!StackEmpty1(S)&&GetTop1(S,&c1)&&}Pop1(&S,&c);/*将'#'出栈*/*pre_expr='\0';/*字符串结束符*/if(i<0&&StackEmpty1(S))returnOK;elsereturnERROR;}voidreversal_string(char*exprstring){len=strlen(exprstring);/*len为{temp=exprstring[i];exprstring[i]=exprstring[j];exprstring[j]=temp;}}voidMergeConst(BiTree*E){{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()函数求值*/t;/*修改之前的运算符为常量*/(*E)->lchild=(*E)->rchild=NULL;/*左右孩}{MergeConst(&((*E)->lchild));/*递MergeConst(&((*E)->rchild));/*递}}}{printf("\n\t****************************************");printf("\n\t计算机学院计算机科学与printf("\n\t****************************************");printf("\n\t***********表达式类型的实现*************");printf("\n\tprintf("\n\tprintf("\n\tprintf("\n\tprintf("\n\tprintf("\n\t1>>>输入正确的前缀2>>>带括弧的中缀表3>>>对变量进行赋值4>>>对算数表达式求5>>>构造一个新的复6>>>以表达式的原书printf("\n\tprintf("\n\t7>>>合并表达式中所printf("\n\t****************************************");printf("\n\t请输入你的选择>>>>>");choice=getche();}voidmain(){longresult;/*保存算数表达式运算结果while(1){case'1':/*1>>>输入正确的前缀表printf("\n\t*************************输入提示信息************************");printf("\n\t输入正确的前缀表达A-Z");+,-,*,/,^(乘幂)");printf("\n\t请输入正确的前printf("\n\t*************************************************************");if(Input_Expr(Expr_String,0))if(ReadExpr(&E,Expr_String))造成功！\n输入的带括弧的中缀表达式：case'2':/*2>>>带括弧的中缀表示***********************************");printf("\n\t输出带括弧的中缀表printf("\n\t【注】其中要注意的printf("\n\t如果输出不是printf("\n\t********************************************************************elseprintf("\n表达式未构造成case'3':/*3>>>对变量进行赋值*/printf("\n\t***********************************************");printf("\n\t赋值操作：实现printf("\n\t未构造，请回到主菜单选择构造表达式");printf("\n\t********************************************************************{flushall();/*清理缓冲区*/V=getchar();Assign(&E,V,c,&Assign_flag);elseprintf("\n表达式里没有%c}elseprintf("\n表达式未构造成case'4':/*4>>>对算数表达式求值printf("\n\t********************************");有变量未赋值，即表达式不是算数表达式");printf("\n\t不能求出表printf("\n\t******************************************************************");{{result=Value(E);printf("\n求算数表达