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

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