數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-算術(shù)表達(dá)式求值演示程序.doc

軟 件 學(xué) 院課程設(shè)計(jì)報(bào)告書(shū)課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目 算術(shù)表達(dá)式求值演示程序 專(zhuān)業(yè)班級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2010年 12月目錄1.設(shè)計(jì)時(shí)間22.設(shè)計(jì)目的23.設(shè)計(jì)任務(wù)24.設(shè)計(jì)內(nèi)容24.1需求分析24.2總體設(shè)計(jì)24.2.1抽象數(shù)據(jù)類(lèi)型定義24.2.2函數(shù)模塊說(shuō)明34.2.3主函數(shù)流程圖44.2.4函數(shù)模塊調(diào)用關(guān)系54.2.5運(yùn)算符間的優(yōu)先關(guān)系54.3詳細(xì)設(shè)計(jì)64.3.1數(shù)據(jù)類(lèi)型的定義64.3.2函數(shù)調(diào)用關(guān)系84.3.3主要模塊的算法描述84.4測(cè)試與分析104.4.1測(cè)試104.4.2分析114.5附錄115.總結(jié)與展望16參考文獻(xiàn)17成績(jī)?cè)u(píng)定171 設(shè)計(jì)時(shí)間2010.12.27-2011.1.32 設(shè)計(jì)目的掌握棧的使用和把一個(gè)表達(dá)式翻譯成能夠正確求值的一個(gè)機(jī)器指令序列的原理。3設(shè)計(jì)任務(wù)設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。4 設(shè)計(jì)內(nèi)容4.1需求分析1、程序所能達(dá)到的功能：能夠處理以字符序列的形式輸入的不含變量的實(shí)數(shù)表達(dá)式，正確處理負(fù)數(shù)與小數(shù)，判斷表達(dá)式是還語(yǔ)法正確（包含分母不能為零的情況），正確實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，能夠?qū)⒂?jì)算中遇到的問(wèn)題和結(jié)果以文件的形式予以存儲(chǔ)。2、輸入的形式和輸入值的范圍：以字符串的形式輸入表達(dá)式，以“#”結(jié)束。3、輸出的形式：在計(jì)算過(guò)程中遇到的問(wèn)題或最終的答案將顯示在屏幕上，同時(shí)所計(jì)算的表達(dá)式的最終的結(jié)果也將保存在文件中。4、測(cè)試數(shù)據(jù)：輸入“3*(7-2)#”時(shí)，輸出“15.000000”，測(cè)試正確；輸入“!(9-2)#”時(shí)，輸出“輸入錯(cuò)誤！”，測(cè)試正確。4.2總體設(shè)計(jì)4.2.1抽象數(shù)據(jù)類(lèi)型定義ADT Stack數(shù)據(jù)對(duì)象：D= |ElemSet,i=1,2,，n, n0數(shù)據(jù)對(duì)象：R1=|,i=2,，n約定端為棧頂，端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。GetTop(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S，ch)初始條件：棧S已存在。操作結(jié)果：插入元素ch為新的棧頂元素。Pop(&S)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回1。Precede(c1, c2) 初始條件：c1,c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長(zhǎng)度。EvalExpr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。ADT Stack4.2.2函數(shù)模塊說(shuō)明為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧。一個(gè)稱(chēng)做OPTR，用以寄存運(yùn)算符；另一個(gè)稱(chēng)做OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。算法的基本思想是：(1)首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧底元素(2)依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。算法中還調(diào)用了兩個(gè)函數(shù)。其中Precede是判定運(yùn)算符棧頂運(yùn)算符1與讀入的運(yùn)算符2之間優(yōu)先關(guān)系的函數(shù)；Operateo為進(jìn)行二元運(yùn)算ab的函數(shù)，如果是編譯表達(dá)式，則產(chǎn)生這個(gè)運(yùn)算的一組相應(yīng)指令并返回存放結(jié)果的中間變量名；如果是解釋執(zhí)行表達(dá)式，則直接進(jìn)行該運(yùn)算，并返回運(yùn)算結(jié)果。4.2.3主函數(shù)流程圖4.2.4函數(shù)模塊調(diào)用關(guān)系4.2.5運(yùn)算符間的優(yōu)先關(guān)系1 2+-*/()#+-*/(#=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;return OK;Status Pop(SqStack &S,SElemType &e)if(S.top = S.base) return ERROR;e = * -S.top;return OK;OperandType EvaluateExpession()InitStack(OPTR); Push(OPTR,#);InitStack(OPND); c = getchar();while(c!#|GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c); c = getchar();) else switch(Precede(GetTop(OPTR),c) case:Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; 4.3.2函數(shù)調(diào)用關(guān)系4.3.3主要模塊的算法描述void main()SqStack_T OPTR;SqStack_N OPND;float a,b,i; char theta,c,x;InitStack_T(&OPTR);Push_T(&OPTR,#);InitStack_N(&OPND);printf(“請(qǐng)輸入表達(dá)式關(guān)以#結(jié)尾：n”);c=getchar();if(c=35|(c=40&c=47&c=48&c=57) i=(float)c-48; Push_N(&OPND,i); c=getchar(); else switch(Precede(GetTop_T(&OPND),c) case:theat=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b);break; printf(“結(jié)果是%fn”,GetTop_N(&OPND);else printf(“輸入錯(cuò)誤！n”);4.4測(cè)試與分析4.4.1測(cè)試加法測(cè)試，輸入正確，輸出正確，測(cè)試正確：減法測(cè)試，輸入正確，輸出正確，測(cè)試正確：乘法測(cè)試，輸入正確，輸出正確，測(cè)試正確：除法測(cè)試，輸入正確，輸出正確，測(cè)試正確：輸入表達(dá)式正確，輸出正確，測(cè)試正確：輸入表達(dá)式錯(cuò)誤，能正確判斷，測(cè)試正確：4.4.2分析內(nèi)容包括：1、調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析:遇到的問(wèn)題：調(diào)試過(guò)程中遇到了輸入非法字符不輸出“錯(cuò)誤！”的情況。解決的辦法：查ASCII碼表得知運(yùn)算符+,-,*,/,(,),#和運(yùn)算數(shù)0,1,2,3,4,5,6,7,8,9相應(yīng)的ASCII值。在主程序中加入了判斷語(yǔ)句，判斷輸入的是否為運(yùn)算符或運(yùn)算數(shù)。如果是，則進(jìn)行正常運(yùn)算；如果不是，則返回錯(cuò)誤。2、算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析：中綴表達(dá)式運(yùn)算時(shí)間主要用在字符串掃描和算符優(yōu)先權(quán)的比較上。把#看作運(yùn)算符，操作數(shù)與運(yùn)算符個(gè)數(shù)相同，最壞情況下優(yōu)先級(jí)比較是n/2次，即運(yùn)算順序完全是逆序的，每個(gè)字符掃描一遍是O(n)的，所以整個(gè)算法復(fù)雜度是O(n2)的。算法中用到兩個(gè)棧，分別為O(n/2)，其算法空間復(fù)雜度是O(n)。4.5附錄#include stdio.h#include stdlib.h#define OK 1#define ERROR 0#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack_T;typedef structfloat *base;float *top;int stacksize;SqStack_N;void InitStack_T(SqStack_T *S)(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;void InitStack_N(SqStack_N *S)(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;char GetTop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;float GetTop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;char Push_T(SqStack_T *S,char e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(char*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Push_N(SqStack_N *S,float e)if(*S).top-(*S).base=(*S).stacksize)(*S).base=(float*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;char Pop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;float Pop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;char m7=+-*/()#;char n77=, ,=40&c=47&c=48&c=57)i=(float)c-48;Push_N(&OPND,i);c=getchar();elseswitch(Precede(GetTop_T(&OPTR),c)case:theta=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b);break;printf(結(jié)果是%fn,GetTop_N(&OPND);else printf(輸入錯(cuò)誤!n);5 總結(jié)與展望通過(guò)這段時(shí)間的課程設(shè)計(jì)，本人對(duì)計(jì)算機(jī)的應(yīng)用、數(shù)據(jù)結(jié)構(gòu)的作用以及C語(yǔ)言的使用都有了更深的了解。當(dāng)然也遇到不少問(wèn)題，也正是國(guó)為這些問(wèn)題引發(fā)的思考給我?guī)?lái)了收獲。從當(dāng)初不喜歡上機(jī)寫(xiě)程序到現(xiàn)在能主動(dòng)寫(xiě)程序，從當(dāng)初拿著程序不知從何下手到現(xiàn)在知道如何分析問(wèn)題，如何用專(zhuān)業(yè)知識(shí)解決實(shí)際問(wèn)題的轉(zhuǎn)變。我發(fā)現(xiàn)無(wú)論是專(zhuān)業(yè)知識(shí)還是動(dòng)手能力，自己都有很大程度的提高。在實(shí)際上機(jī)操作過(guò)程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的是培養(yǎng)解決實(shí)際問(wèn)題的能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。這次課程設(shè)計(jì)讓我更加了解大一學(xué)到的C和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)的緊密聯(lián)系。設(shè)計(jì)題目