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

1、軟件學(xué)院課程設(shè)計報告書課程名稱 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目 算術(shù)表達(dá)式求值演示程序?qū)I(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詳細(xì)設(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參考文獻(xiàn)17成績評定171 設(shè)計時間2010.12.272011

2、。1.32 設(shè)計目的掌握棧的使用和把一個表達(dá)式翻譯成能夠正確求值的一個機(jī)器指令序列的原理。3設(shè)計任務(wù)設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。4 設(shè)計內(nèi)容4。1需求分析1、程序所能達(dá)到的功能：能夠處理以字符序列的形式輸入的不含變量的實數(shù)表達(dá)式，正確處理負(fù)數(shù)與小數(shù),判斷表達(dá)式是還語法正確（包含分母不能為零的情況），正確實現(xiàn)對算術(shù)四則混合運算表達(dá)式的求值，能夠?qū)⒂嬎阒杏龅降膯栴}和結(jié)果以文件的形式予以存儲.2、輸入的形式和輸入值的范圍：以字符串的形式輸入表達(dá)式,以“"結(jié)束。3、輸出的形式:在計算過程中遇到的問題或最終的答案將顯示在屏幕上，同時所計算的表達(dá)式的最終的結(jié)果也將保存在

3、文件中.4、測試數(shù)據(jù):輸入“3*(7-2)#”時，輸出“15.000000”，測試正確；輸入“?。?-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約定端為棧頂，端為棧底。基本操作：InitStack（&S)操作結(jié)果：構(gòu)造一個空棧S。GetTop（S）初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push（S，ch)初始條件：棧S已存在。操作結(jié)果：插入元素ch為新的棧頂元素。Pop（S)初始條件：棧S已存在.操作結(jié)果：刪除S的棧頂

4、元素.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進(jìn)行運算，op為運算符，返回其值。num(n）操作結(jié)果:返回操作數(shù)的長度。EvalExpr（）初始條件：輸入表達(dá)式合法.操作結(jié)果:返回表達(dá)式的最終結(jié)果。ADT Stack4。2。2函數(shù)模塊說明為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧。一個稱做OPTR，用以寄存運算符；另一個稱做OPND，用以寄存操作數(shù)或運算結(jié)果.算法的基本思想是：（1)首先置操作

5、數(shù)棧為空棧，表達(dá)式起始符“"為運算符棧底元素（2)依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達(dá)式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”).算法中還調(diào)用了兩個函數(shù)。其中Precede是判定運算符棧頂運算符1與讀入的運算符2之間優(yōu)先關(guān)系的函數(shù);Operateo為進(jìn)行二元運算ab的函數(shù)，如果是編譯表達(dá)式，則產(chǎn)生這個運算的一組相應(yīng)指令并返回存放結(jié)果的中間變量名;如果是解釋執(zhí)行表達(dá)式，則直接進(jìn)行該運算，并返回運算結(jié)果.4.2。3主函數(shù)流程圖4.2.4函數(shù)模塊調(diào)用關(guān)系4。2。5運算符間的優(yōu)先關(guān)系1

6、 2+-/（)+><>->/><（<<=）><<=4。3詳細(xì)設(shè)計4。3。1數(shù)據(jù)類型的定義及基本操作/= ADT Stack的表示與實現(xiàn) = /- 棧的順序存儲表示 -define STACK_INIT_SIZT 100;define STACKINCREMENT 10typedef structSElemType base；SElemType *top；int stacksize；SqStack;/- 基本操作的算法描述 -Status InitStack（SqStack &S）S。base=(SElemType )ma

7、lloc（STACK_INIT_SIZE * sizeof（SElemType）)；if(!S。base） exit (OVERFLOW)；S。top=S。base;S。stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack S,SElemType e)if（S。top=S。base） return ERROR;e=（S。top1）;return OK;Status Push(SqStack &S，SElemType e)if（S。topS.base=S。stacksize) S。base=（SElemType)realloc

8、（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）；

9、Push(OPTR，#);InitStack（OPND）； c = getchar（）；while（c！|GetTop（OPTR）！='#）if(!In(c,OP）)Push(（OPND，c）; c = getchar();）elseswitch（Precede(GetTop(OPTR），c）)case：Push（OPTR,c）； c = getchar(）； break；case=：Pop（OPTR,x）； c = getchar（）； break;case'：Pop（OPTR，theta）； Pop（OPND,b）; Pop(OPND，a）； Push（OPND，Opera

10、te(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（“請輸入表達(dá)式關(guān)以'#結(jié)尾：n”)；c=getchar（）；if（c=35（c=40&&c=43)c=45|(c=47c=57)）while(c！='|GetTop_T(OPTR）!=)if(c=48&a

11、mp;c<=57) i=（float)c48； Push_N（OPND，i)； c=getchar（）; else switch（Precede（GetTop_T（OPND），c） case'：Push_T(OPTR,c）;c=getchar（)；break；case'=:x=Pop_T（&OPTR）;c=getchar(）;break;case''：theat=Pop_T（OPTR）；b=Pop_N（OPND）；a=Pop_N（OPND）；Push_N(OPND，Operate（a，theta，b）；break； printf（“結(jié)果是%fn”，

12、GetTop_N（&OPND);else printf(“輸入錯誤！n”）；4。4測試與分析4.4.1測試加法測試,輸入正確，輸出正確,測試正確：減法測試，輸入正確，輸出正確，測試正確：乘法測試，輸入正確，輸出正確，測試正確：除法測試，輸入正確，輸出正確，測試正確:輸入表達(dá)式正確，輸出正確，測試正確:輸入表達(dá)式錯誤,能正確判斷,測試正確:4。4。2分析內(nèi)容包括：1、調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析:遇到的問題：調(diào)試過程中遇到了輸入非法字符不輸出“錯誤!”的情況。解決的辦法：查ASCII碼表得知運算符'+'，'/，'(,&#

13、39;）,'和運算數(shù)'0，1',2，3，'4，5，6'，7',8'，9相應(yīng)的ASCII值。在主程序中加入了判斷語句,判斷輸入的是否為運算符或運算數(shù)。如果是，則進(jìn)行正常運算;如果不是，則返回錯誤。2、算法的時間復(fù)雜度和空間復(fù)雜度的分析：中綴表達(dá)式運算時間主要用在字符串掃描和算符優(yōu)先權(quán)的比較上.把#看作運算符，操作數(shù)與運算符個數(shù)相同，最壞情況下優(yōu)先級比較是n/2次,即運算順序完全是逆序的，每個字符掃描一遍是O(n）的,所以整個算法復(fù)雜度是O（n2）的。算法中用到兩個棧，分別為O（n/2),其算法空間復(fù)雜度是O（n）。4.5附錄include”

14、stdio。h”include”stdlib。h”define OK 1define ERROR 0define OVERFLOW 0define STACK_INIT_SIZE 100define STACKINCREMENT 10typedefstructchar*base；char*top；int stacksize；SqStack_T;typedefstructfloat*base；floattop;int stacksize；SqStack_N；void InitStack_T（SqStack_T S）（S）。base=（char*)malloc（STACK_INIT_SIZE*si

15、zeof(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_SIZEsizeof(float)）;if(?。⊿).base) exit（OVERFLOW）;（S）。top=(S）。base;（S).stacksize=STACK_INIT_SIZE；char GetTop_T(SqStack_T S）char e；if（(S）。top=（S）.bas

16、e) 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（OVERF

17、LOW)；（*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(?。⊿).base） exit（OVERFLOW）;（S)。top=（S）。base+（*S)。stacksize；(*S

18、)。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=”><>”，”<<<>”，”，”>><

19、;>>”，”= ",">>>> >>”,"<< =”；char Precede(char a,char b）int i=0，j=0;while（mi！=a)i+；while(mj!=b)j+;return(nij）；float Operate（float a,char theta,float b)float r;switch(theta）case+：r=a+b;break;case'：r=ab;break；case*：r=ab；break;case/：if（b！=0）r=a/b；else prin

20、tf（”輸入錯誤!");break；return r;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(”請輸入表達(dá)式并以''結(jié)尾：n”)；c=getchar（）;if（c=35（c=40c=43）c=45|（c=47&c<=57）while（c!=GetTop_T（OPTR）!='#）if（c=48&c=57）i=（float）c48;Push_N（&OPND,i）;c=getchar(）;elseswitch（Precede(GetTop_T(&OPTR),c）)case：Push_T(&OPTR，c）；c=getchar（）；break;case'='：x=Pop_T（OPTR）；c=getchar()；break；case>：theta=Pop_T