課程設(shè)計(jì)報(bào)告-表達(dá)式類型的實(shí)現(xiàn)-方銳洲

課程設(shè)計(jì)報(bào)告-表達(dá)式類型的實(shí)現(xiàn)-方銳洲專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名方銳洲輔導(dǎo)教師吳偉民~~~~~~~~~~表達(dá)式類型的實(shí)現(xiàn)~~~~~~~~~~一、需求分析------------------------3三、詳細(xì)設(shè)計(jì)----------------------7-13-------------------14五、用戶手冊(cè)------------------------1488八、參考文獻(xiàn)------------------------195【問(wèn)題的描述】一個(gè)表達(dá)式和一棵二叉樹之間，存在著自然的對(duì)應(yīng)關(guān)系。寫一個(gè)程序，實(shí)【基本要求】【測(cè)試數(shù)據(jù)】/*頭文件以及存儲(chǔ)結(jié)構(gòu)*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0ADTExpression{StatusInput_Expr(&string,flag)操作結(jié)果：以字符序列的形式輸入語(yǔ)法正確的前綴表達(dá)式，保存到字符串voidjudge_value(&E,&string,i)操作結(jié)果：判斷字符string[i]，如StatusReadExpr(&E,&exprstring)初始條件：表達(dá)式的前綴形式字符串操作結(jié)果：以正確的前綴表示式StatusPri_Compare(c1,c2)操作結(jié)果：如果兩個(gè)字符是運(yùn)算符，voidWriteExpr(&E)操作條件：用帶括弧的中綴表達(dá)式輸voidAssign(&E,V,c,&flag)longOperate(opr1,opr,opr2)操作結(jié)果：運(yùn)算符運(yùn)算求值，參數(shù)StatusCheck(E)沒有賦值的變量，以便求算數(shù)表達(dá)式操作結(jié)果：對(duì)算術(shù)表達(dá)式求值，返回voidCompoundExpr(P,&E1,E2)操作條件：構(gòu)造一個(gè)新的復(fù)合表達(dá)式Read_Inorder_Expr(&string,&pre_ex操作結(jié)果：以表達(dá)式的原書寫形式輸入，表達(dá)式的原書寫形式字符串reversal_string()函數(shù)反轉(zhuǎn)得到前voidMergeConst(&E)操作結(jié)果：常數(shù)合并操作，合并表達(dá)在這個(gè)課程設(shè)計(jì)中，有兩個(gè)源代碼文件：結(jié)構(gòu)的聲明和輔助存儲(chǔ)結(jié)構(gòu)的兩個(gè)棧的基本操《一》expression.h文件的整2、兩個(gè)除了棧名和棧存儲(chǔ)的元素不一樣的StatusInitStack(SqStack*S)/*構(gòu)造一個(gè)StatusStackEmpty(SqStackS)/*若棧S為StatusPush(SqStack*S,SElemTypee)/*插StatusPop(SqStack*S,SElemType*e)/*若StatusGetTop(SqStackS,SElemType*StatusPush1(SqStack1*S,SElemType1e)StatusPop1(SqStack1*S,SElemType1*e)可以從主菜單函數(shù)可以明了的了解的程序{printf("\n****************************************");printf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\nprintf("\n2>>>帶括弧的中綴表示3>>>對(duì)變量進(jìn)行賦值4>>>對(duì)算數(shù)表達(dá)式求值5>>>構(gòu)造一個(gè)新的復(fù)合6>>>以表達(dá)式的原書寫7>>>合并表達(dá)式中所有printf("\n****************************************");printf("\n請(qǐng)輸入你的選擇>>>>>");choice=getche();}在主函數(shù)中，采用多分支程序設(shè)計(jì)語(yǔ)句voidmain(){while(1){{}}}2、本程序有四個(gè)模塊，主程序模塊，二叉樹模主程序模塊中的對(duì)于表達(dá)式的存儲(chǔ)結(jié)構(gòu)調(diào)原表達(dá)式形式輸入表達(dá)式轉(zhuǎn)換為前綴表達(dá)式操/*二叉樹結(jié)點(diǎn)類型*/typedefstructTElemT{ElemTagtag;/*{INT,CHAR}指示是整型還{/*二叉樹的二叉鏈表存儲(chǔ)表示*/typedefstructBiTNode{二叉樹的基本操作已經(jīng)在構(gòu)造表達(dá)式和表達(dá)式中的基本操作中根據(jù)不同的功能和實(shí)際情/*棧的順序存儲(chǔ)表示*//*兩個(gè)順序棧*/{SElemType*base;/*在棧構(gòu)造之前和{相關(guān)的基本操作見上面的“expression.hStatusInput_Expr(char*string,intflag);/*以字符序列的形式輸入語(yǔ)法正確的前綴/*參數(shù)flag=0表示輸出的提示信息是"請(qǐng)/*flag=1表示輸出的提示信息為"請(qǐng)以表達(dá)voidjudge_value(BiTree*E,char/*判斷字符string[i]，如果是'0'-'9'常*exprstring);/*以正確的前綴表示式并構(gòu)造表達(dá)式E*/StatusPri_Compare(charc1,charc2);voidWriteExpr(BiTreeE);/*用帶括弧的中綴表達(dá)式輸入表達(dá)式*//*實(shí)現(xiàn)對(duì)表達(dá)式中的所有變量V的賦值longOperate(intopr1,charopr,intopr2);/*運(yùn)算符運(yùn)算求值，參數(shù)opr1,opr2為?，F(xiàn)不同的運(yùn)算，返回運(yùn)算結(jié)果*/StatusCheck(BiTreeE);/*對(duì)算術(shù)表達(dá)式求值*//*構(gòu)造一個(gè)新的復(fù)合表達(dá)式*/StatusRead_Inorder_Expr(char*string,char*pre_expr);voidMergeConst(BiTree*E);{judge_value(E,exprstring,0);將exprstring[0]存入二叉樹的結(jié)點(diǎn)中Push(&S,q);Push(&S,q);{if(Pri_Compare(E->data.c,E->lchild->d{/*實(shí)現(xiàn)對(duì)表達(dá)式中的所有變量V的賦值{if(E&&E->data.tag==CHAR)/*樹不為空*/{{E=(BiTree)malloc(sizeof(BiTNode));/*{/*以表達(dá)式的原書寫形式輸入，表達(dá)式的原c=string[len-1];從字符串的最后一個(gè)字符開始向前掃描,len=strlen(string);while(!StackEmpty1(S)&&i>=0)/*棧不為{if(c=='(')字符為'(',Pop1(&S,&c);if((*E)->lchild&&(*E)->rchild)左右孩子{voidmain(){while(1){{case'1':/*輸入正確的前綴表達(dá)式*/if(Input_Expr(Expr_String,0))輸if(ReadExpr(&E,Expr_String))case'2':/*帶括弧的中綴表示式輸出*/if(flag==1)WriteExpcase'3':/*對(duì)變量進(jìn)行賦值*/{flushall();/*清理緩沖區(qū)*/V=getchar();Assign(&E,V,c,&Assign_flag);}elseprintf("\n表達(dá)式未構(gòu)造成case'4':/*對(duì)算數(shù)表達(dá)式求值*/{WriteExpr(E);printf(result);}}elseprintf("\n表達(dá)式未構(gòu)造成case'5':/*構(gòu)造一個(gè)新的復(fù)合表達(dá)式*/{flushall();/*清理緩沖區(qū)*/{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復(fù)合新的}}}case'6':/*以表達(dá)式的原書寫形式輸入if(Read_Inorder_Expr(string,Expr_String{reversal_string(Expr_String);if(ReadExpr(&E,Expr_String))}case'7':/*合并表達(dá)式中所有常數(shù)運(yùn)算if(flag==1)MergeConst(&E);case'0':/*退出*/}}}除了主函數(shù)main()外，其他各個(gè)函數(shù)相對(duì)數(shù)main()調(diào)用使用的，可以簡(jiǎn)單的說(shuō)，各個(gè)函1、在起初設(shè)計(jì)上，針對(duì)前綴表達(dá)式的要求在這個(gè)構(gòu)造表達(dá)式的架構(gòu)上逐個(gè)逐個(gè)實(shí)現(xiàn)對(duì)表本來(lái)以為使用遞歸構(gòu)造表達(dá)式會(huì)很難做到出錯(cuò)3、在對(duì)各個(gè)功能操作的實(shí)現(xiàn)上，時(shí)間復(fù)雜復(fù)雜度為O(n+s)。而在以原表達(dá)式形式輸入操間復(fù)雜度取決于輸入的字符串的長(zhǎng)度n，即4、在調(diào)試的過(guò)程中，花費(fèi)時(shí)間最為多的是2、進(jìn)入演示程序后首先出現(xiàn)一個(gè)主菜單，3、之后輸入你的選擇，進(jìn)入你所要進(jìn)行的《一》選擇‘1’進(jìn)入測(cè)試輸入正確的前綴表達(dá)‘8’3、輸入前綴表達(dá)式為一個(gè)簡(jiǎn)單的運(yùn)算表達(dá)4、輸入前綴表達(dá)式為一個(gè)較為復(fù)雜的、帶6、輸入錯(cuò)誤的前綴表達(dá)式：‘+999’和‘+*5^x2*8x&’《二》選擇‘3’進(jìn)入測(cè)試對(duì)變量的賦值《三》選擇‘4’進(jìn)入測(cè)試求算數(shù)表達(dá)式的值《四》選擇‘5’進(jìn)入構(gòu)造新的復(fù)合表達(dá)式《五》選擇‘6’進(jìn)入以原表達(dá)式形式輸入構(gòu)造1、構(gòu)造表達(dá)式‘6*a+9/b-(a+2^3)’BUG，程序的判定帶括弧輸出表達(dá)式時(shí)判斷兩個(gè)‘(((3+2)*9)-(6/3)*9+1)/8+18*3’4、構(gòu)造表達(dá)式‘6+-b+9*9’，出錯(cuò)處理《六》選擇‘7’進(jìn)入合并常數(shù)操作這個(gè)合并常數(shù)操作唯一的缺點(diǎn)就是要多次經(jīng)過(guò)對(duì)各個(gè)操作的測(cè)試，可以這樣總結(jié)的七、課程設(shè)計(jì)的心得和體會(huì)以及問(wèn)題C++6.0的調(diào)試器的操作的熟練度；而且，讓我在發(fā)現(xiàn)問(wèn)題解決問(wèn)題中深刻地理解到完善程序分析更加清晰，遞歸的思想更加深化！造表達(dá)式為架構(gòu)——其余的操作都是在這個(gè)架exprssion.c//包含主程序和表達(dá)式的基本/*頭文件以及存儲(chǔ)結(jié)構(gòu)*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0/*二叉樹結(jié)點(diǎn)類型*/typedefstructTElemT{ElemTagtag;/*{INT,CHAR}指示是整型還{/*二叉樹的二叉鏈表存儲(chǔ)表示*/typedefstructBiTNode{typedefcharSElemType1;/*棧/*棧的順序存儲(chǔ)表示*//*兩個(gè)順序棧*/{SElemType*base;/*在棧構(gòu)造之前和銷{SElemType1*top;/*棧頂指針*//*順序棧的基本操作*/StatusInitStack(SqStack*S)*)malloc(STACK_INIT_SIZE*sizeof(SElemTypeexit(OVERFLOW);/*存儲(chǔ)分配失敗*/returnOK;}StatusStackEmpty(SqStackS)if(S.top==S.base)returnTRUE;}StatusPush(SqStack*S,SElemTypee)if((*S).top-(*S).base>=(*S).stacksize)/*棧滿，追加存儲(chǔ)空間*/{*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/}*((*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);/*存儲(chǔ)分配失敗*/returnOK;}StatusStackEmpty1(SqStack1S)if(S.top==S.base)returnTRUE;}StatusPush1(SqStack1*S,SElemType1e)if((*S).top-(*S).base>=(*S).stacksize)/*棧滿，追加存儲(chǔ)空間*/{*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1));if(!(*S).base)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/}*((*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];/*在按原表達(dá)式輸入形式中，輸入的常量保存到數(shù)組save_numbercharExpr_String[30];/*存放表達(dá)式的字符/*以字符序列的形式輸入語(yǔ)法正確的前綴表/*參數(shù)flag=0表示輸出的提示信息是"請(qǐng)輸/*flag=1表示輸出的提示信息為"請(qǐng)以表達(dá)式{if(flag==0)printf("\n請(qǐng)輸入正確的前flushall();/*清理緩沖區(qū)*/gets(string);/*從鍵盤輸入一串字符串作if(strlen(string)==1)/*輸入的表達(dá)式字if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*輸入的表達(dá)式只有一個(gè)運(yùn)算符*/if((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z'))/*輸入的表達(dá)式只有一個(gè)數(shù)字或字符}/*判斷字符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]];}}/*以正確的前綴表示式并構(gòu)造表達(dá)式E*/*exprstring){BiTreep,q;len=strlen(exprstring);/*len賦值為表judge_value(E,exprstring,0);/*將exprstring[0]存入二叉樹的結(jié)點(diǎn)中*/{judge_value(E,exprstring,0);/*將exprstring[0]存入二叉樹的結(jié)點(diǎn)中*/Push(&S,q);/*入棧*/Push(&S,q);/*入棧，根結(jié)點(diǎn)入棧兩次是為判斷先序輸入的表達(dá)式是不是正確的表達(dá)式for(i=1;i<len&&!StackEmpty(S);i++){p=(BiTree)malloc(sizeof(BiTNode));judge_value(&p,exprstring,i);/*將exprstring[i]存入二叉樹的結(jié)點(diǎn)中*/p->lchild=NULL;p->rchild=NULL;if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^')}else/*不是運(yùn)算符，運(yùn)算符出棧*/{else{q->rchild=p;Pop(&S,&q);}}}if(StackEmpty(S)&&i>=len)returnelse/*輸入的表達(dá)式是錯(cuò)誤的*/{returnERROR;}}}StatusPri_Compare(charc1,charc2){if((c1=='^'||c1=='*'||c1=='-'||c1=='+'|=='+'||c2=='/')){elsereturnERROR;}{if(c2=='^'||c2=='*'||c2=='/')returnERROR;}}}/*用帶括弧的中綴表達(dá)式輸入表達(dá)式*/voidWriteExpr(BiTreeE){if(E->lchild&&E->lchild->data.tag==CHAR{if(Pri_Compare(E->data.c,E->lchild->datf(")");}/*帶括弧輸出左子樹*/}/*訪問(wèn)輸出根結(jié)點(diǎn)的值*/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(")");}/*帶括弧輸出右子樹*/}}}/*實(shí)現(xiàn)對(duì)表達(dá)式中的所有變量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;}運(yùn)算，返回運(yùn)算結(jié)果*/{{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'^':/*指數(shù)運(yùn)算*/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表達(dá)式中仍存在變量沒有賦值！沒法求出表達(dá)式的值！");returnif(Check(E->lchild))/*遞歸左子樹*/Check(E->rchild);/*遞歸右子樹*/}}/*對(duì)算術(shù)表達(dá)式求值*/{{if(!E->lchild&&!E->rchild&&E->data.tag=Operate(Value(E->lchild),E->data.c,Value(E->rchild));}}/*構(gòu)造一個(gè)新的復(fù)合表達(dá)式*/voidCompoundExpr(charP,BiTree*E1,BiTreeE2){BiTreeE;E=(BiTree)malloc(sizeof(BiTNode));/*E->data.tag=CHAR;E->data.c=P;/*申請(qǐng)到的結(jié)點(diǎn)值為P*/E->lchild=(*E1);/*結(jié)點(diǎn)的左孩子為E1*/E->rchild=E2;/*結(jié)點(diǎn)的右孩子為E2*/WriteExpr(E);/*輸出復(fù)合好的表達(dá)式*/}/*后調(diào)用reversal_string()函數(shù)反轉(zhuǎn)得到StatusRead_Inorder_Expr(char*string,char*pre_expr){SqStack1S;/*棧定義*/Push1(&S,'#');/*先將字符'#'入棧，用來(lái)表示作為棧的最底一個(gè)元素*/c=string[len-1];/*從字符串的最后一個(gè){{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為第一個(gè)常量for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循環(huán)掃描string前一個(gè){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下一個(gè)字符不能為常量或變if((string[i-1]>='0'&&string[i-1]<='9')string[i-1]>='a'&&string[i-1]<='z')){printf("\n輸入的表達(dá)式有誤！else*pre_expr++=c;}elseif(c=='*'||c=='/')/*字符為運(yùn)算{while(GetTop1(S,&c1)&&(c1=='^'))/*將c{Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1Push1(&S,c);/*入棧字符c*/}elseif(c=='+'||c=='-')/*字符為運(yùn)算{while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'{Pop1(&S,&c1);*pre_expr++=c1;}/*如果c1Push1(&S,c);/*入棧運(yùn)算符c*/}elseif(c=='^')/*字符為運(yùn)算符'^'*/{Push1(&S,c);/*入棧運(yùn)算符'^'*/}");returnERROR;}/*其他字符，錯(cuò)誤，返回c=string[i]循環(huán)下一個(gè)字符*/else/*否則，將清空棧*/while(!StackEmpty1(S)&&GetTop1(S,&c1)&&}Pop1(&S,&c);/*將'#'出棧*/*pre_expr='\0';/*字符串結(jié)束符*/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()函數(shù)求值*/t;/*修改之前的運(yùn)算符為常量*/(*E)->lchild=(*E)->rchild=NULL;/*左右孩}{MergeConst(&((*E)->lchild));/*遞MergeConst(&((*E)->rchild));/*遞}}}{printf("\n\t****************************************");printf("\n\t計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與printf("\n\t****************************************");printf("\n\t***********表達(dá)式類型的實(shí)現(xiàn)*************");printf("\n\tprintf("\n\tprintf("\n\tprintf("\n\tprintf("\n\tprintf("\n\t1>>>輸入正確的前綴2>>>帶括弧的中綴表3>>>對(duì)變量進(jìn)行賦值4>>>對(duì)算數(shù)表達(dá)式求5>>>構(gòu)造一個(gè)新的復(fù)6>>>以表達(dá)式的原書printf("\n\tprintf("\n\t7>>>合并表達(dá)式中所printf("\n\t****************************************");printf("\n\t請(qǐng)輸入你的選擇>>>>>");choice=getche();}voidmain(){longresult;/*保存算數(shù)表達(dá)式運(yùn)算結(jié)果while(1){case'1':/*1>>>輸入正確的前綴表printf("\n\t*************************輸入提示信息************************");printf("\n\t輸入正確的前綴表達(dá)A-Z");+,-,*,/,^(乘冪)");printf("\n\t請(qǐng)輸入正確的前printf("\n\t*************************************************************");if(Input_Expr(Expr_String,0))if(ReadExpr(&E,Expr_String))造成功！\n輸入的帶括弧的中綴表達(dá)式：case'2':/*2>>>帶括弧的中綴表示***********************************");printf("\n\t輸出帶括弧的中綴表printf("\n\t【注】其中要注意的printf("\n\t如果輸出不是printf("\n\t********************************************************************elseprintf("\n表達(dá)式未構(gòu)造成case'3':/*3>>>對(duì)變量進(jìn)行賦值*/printf("\n\t***********************************************");printf("\n\t賦值操作：實(shí)現(xiàn)printf("\n\t未構(gòu)造，請(qǐng)回到主菜單選擇構(gòu)造表達(dá)式");printf("\n\t********************************************************************{flushall();/*清理緩沖區(qū)*/V=getchar();Assign(&E,V,c,&Assign_flag);elseprintf("\n表達(dá)式里沒有%c}elseprintf("\n表達(dá)式未構(gòu)造成case'4':/*4>>>對(duì)算數(shù)表達(dá)式求值printf("\n\t********************************");有變量未賦值，即表達(dá)式不是算數(shù)表達(dá)式");printf("\n\t不能求出表printf("\n\t******************************************************************");{{result=Value(E);printf("\n求算數(shù)表達(dá)