課程設(shè)計報告-表達式類型的實現(xiàn)-方銳洲

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