算術(shù)表達(dá)式求值..docx

1、算術(shù)表達(dá)式求值演示一、需求分析(1) 輸入的形式：語法正確的、不含變量的字符序列形式的整數(shù)表達(dá)式輸入值的范圍：整數(shù)的范圍是 (2 15-l)(2 15-1) 運算符： +，- ，* ，/ ，（，）表達(dá)式結(jié)束運算符 #(2) 輸出的形式：范圍是 (2 15-l)(2 15-1) 的整數(shù)(3) 程序所能達(dá)到的功能：實現(xiàn)對算術(shù)四則混合運算表達(dá)式的求值;程序執(zhí)行命令包括：1)Calculate計算表達(dá)式的值2)Exit退出(4) 測試數(shù)據(jù)1) 82) 2-2-2-3;3) 4+26/12-2*7;4) 18-3*7-15/6;5) 2*(6+2*(3+6*(6+6) ；演示程序以用戶與計算機(jī)交互方式執(zhí)

2、行，即在計算機(jī)終端上顯示提示信息 之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)據(jù) ( 濾去輸入中的 非法字符 ) 和運算結(jié)果顯示在其后。二、概要設(shè)計(1) 為實現(xiàn)上述程序功能需要的抽象數(shù)據(jù)類型：1) 棧的抽象數(shù)據(jù)類型：ADT Stack數(shù)據(jù)對象： D= |ai|aielemset, i=1,2,n ，n0 第1頁數(shù)據(jù)關(guān)系： R1=| ai-1，ai D, i=2 ， ， n 基本操作：InitStack()操作結(jié)果：構(gòu)造一個空棧。GetTop（S，&e）初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。Push(&S，e)初始條件：棧 S 已存在。操作結(jié)

3、果：插入元素e 為新的棧頂元素。Pop(&S,&e)初始條件：棧 S 已存在且非空。操作結(jié)果：刪除S 的棧頂元素，并且用e 返回其值。ADT Stack2) 系統(tǒng)中子程序及功能要求：Precede(char c1,char c2):比較兩個字符的優(yōu)先級，并返回比較結(jié)果。Operate(SElemType a,char op,SElemType b):函數(shù)進(jìn)行四則運算，并返回運算結(jié)果。judge(char op):判斷是否為運算符。EvaluateExpression()：進(jìn)行四則混合運算，并返回運算結(jié)果。(2) 本次程序設(shè)計中一共有三個模塊，一個是由主函數(shù)構(gòu)成的模塊，一個是由各個子功能函數(shù)構(gòu)成

4、的棧模塊 , 第三個是由運算等函數(shù)構(gòu)成的運算模塊。(3) 主模塊可以對子模塊中的函數(shù)進(jìn)行調(diào)用，但子模塊不能對主模塊中的內(nèi)容進(jìn)行調(diào)用；子模塊中的函數(shù)可相互調(diào)用。具體函數(shù)調(diào)用關(guān)系如下：main調(diào)用 EvaluateExpression()EvaluateExpression()調(diào) 用Precede 、 Operate 、 judge 、 InitStack()、GetTop、 Push 、Pop。第2頁三、詳細(xì)設(shè)計(1) 程序流程圖：脫括號（接受下一個字符）Operate 求值最終結(jié)果出棧結(jié)束(2) 元素類型、結(jié)點類型和指針類型typedef intStatus;typedef intSElemT

5、ype; /元素類型typedef structSElemType*base;SElemType*top;intstacksize;SqStack;/結(jié)點類型和指針類型第3頁(3) 棧的基本操作定義如下：Status InitStack(SqStack *S);/ 構(gòu)造一個空棧 S Status GetTop(SqStack S)/ 若棧不空，則返回棧頂元素，否則返回 ERRORStatus Push(SqStack *S,SElemType e);/ 插入 e 為新的棧頂元素Status Pop(SqStack *S,SElemType *e);/ 若棧不空，則刪除 S 的棧頂元素，用 e

6、返回其值，返回 OK，否則返回 ERROR(4) 系統(tǒng)中子程序的基本操作定義：Char Precede(char c1,char c2);/ 進(jìn)行運算符的優(yōu)先級比較，并返回比較結(jié)果。SElemType Operate(SElemType a,char op,SElemType b);/ 進(jìn)行兩個整數(shù)數(shù)的四則運算，并返回運算結(jié)果。Status judge(char op)/ 判斷是否為運算符。SElemType EvaluateExpression()/ 進(jìn)行四則混合運算，并返回運算結(jié)果。(5) 部分基本操作的源程序如下：Status Push(SqStack *S,SElemType e)*(

7、S-top)+=e;return OK;/插入元素 e 為新的棧頂元素Status Pop(SqStack *S,SElemType *e)第4頁if(S-top=S-base)return ERROR;/若棧為空，返回 ERROR*e=*(-(S-top);returnOK; /棧不為空，刪除S 的棧頂元素，用e 返回其值，并返回OKchar Precede(char a,char b)/ 根據(jù)課本 P53, 表 3-1 算符間優(yōu)先關(guān)系編寫程序?qū)崿F(xiàn)算符間的優(yōu)先級比較 SElemType r;switch(a)case+:case-:/+, - 運算符優(yōu)先級相同， 故放在一起進(jìn)行比較if(b=

8、*|b=/|b=()r=;break;case*:/* , / 運算符優(yōu)先級相同，故放在一起進(jìn)行比較case/:if(b=() r=;break;case(:if(b=#)printf(nLogicexpressionerror ！ There is no rightbracket！ );return( 0 ) ; / 邏輯錯誤，只有左括號，缺少右括號第5頁else if(b=)r=;else r=;break;case#:if(b=)printf(nLogic expression error!There is no leftbracket!);return(0) ;/邏輯錯誤，只有右括號，

9、缺少左括號elseif(b=#)r=;else r=0&c=9)sum=(sum*10+(c-0);c=getchar();Push(&OPND,sum);/不是運算符進(jìn)棧sum=0;elseswitch(Precede(GetTop(OPTR)+0),c)case:/棧頂元素優(yōu)先級高，退棧并將運算結(jié)果進(jìn)棧Pop(&OPTR,&theta);Pop(&OPND,&b);Pop(&OPND,&a);e=Operate(a,(theta+0),b);Push(&OPND,e);break;case0:Push(&OPND,0);c=#;/邏輯錯誤， 0 進(jìn)棧 ，并結(jié)束運算break;第8頁retu

10、rn (GetTop(OPND);四、調(diào)試分析(1) 在調(diào)試過程中遇到的兩大問題：1）如何進(jìn)行超過一位的數(shù)的存儲原因分析：按照預(yù)想的想法，對表達(dá)式進(jìn)行實際操作時發(fā)現(xiàn)，當(dāng)輸入超過一位的數(shù)時，在程序的運行過程中，只進(jìn)行了數(shù)的最低位的運算：例如 1+15#，由于系統(tǒng)將 15 進(jìn)行兩個字符處理后仍按兩個字符進(jìn)行進(jìn)棧存儲，使得實際運行結(jié)果為 6，顯然是錯誤的解決方案：對操作數(shù)的進(jìn)棧存儲程序進(jìn)行優(yōu)化，使其能將多位數(shù)視為單個字符進(jìn)行進(jìn)棧存儲具體程序由原來的if(!judge(c)Push(&OPND,sum);c=getchar();優(yōu)化如下：if(!judge(c)while(c=0&c=9)sum=(s

11、um*10+(c-0);c=getchar();Push(&OPND,sum);sum=0;當(dāng)然，在聲明變量時已經(jīng)對sum進(jìn)行了初始化： sum=0。2) 如何進(jìn)行數(shù)的轉(zhuǎn)換原因分析：最初對站內(nèi)元素類型的定義為char ，但進(jìn)行運算時發(fā)現(xiàn)其運算或則是運算的結(jié)果均不能超過128，這是由 char 類型本身的性決定的解決方案：將棧內(nèi)元素的類型定義為int ，無論是運算符，還是數(shù)字字符，在第9頁進(jìn)棧之前都進(jìn)行（ - 0）操作，對于已經(jīng)整型化的數(shù)字字符在進(jìn)行其后的運算或進(jìn)棧時不用在進(jìn)行數(shù)的轉(zhuǎn)換， 但是由于個人程序的編制要求，運算符在出棧時仍需要進(jìn)行相關(guān)的操作（ +0），即將運算符重新字符化(2) 實驗總

12、結(jié)：經(jīng)過本次課程設(shè)計，我深刻地感受到數(shù)據(jù)結(jié)構(gòu)的重要性， 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)很重要的一門課程，也是必須要熟練掌握的課程。本次課程設(shè)計， 我選擇的項目是算術(shù)表達(dá)式的求值 , 它的實現(xiàn)主要是棧的應(yīng)用， 所以，通過這次的實習(xí)，特別加深了我對棧這一數(shù)據(jù)類型的理解，在實際應(yīng)用中也比以前更加得心應(yīng)手。另外，在本次的程序設(shè)計中，我還切身的體會到不同的類型的數(shù)據(jù)的實際意義，一個程序可能會因為元素類型定義不當(dāng)而永遠(yuǎn)得不到預(yù)期得結(jié)果。在本次課程設(shè)計當(dāng)中，在做完需求分析和概要設(shè)計后，我又進(jìn)行了詳細(xì)設(shè)計，經(jīng)過一番分析之后，我首先對自己需要的模塊進(jìn)行了詳細(xì)的編寫，在確保各個功能模塊的可行性以及正確性后，進(jìn)行了與主函數(shù)、

13、函數(shù)與函數(shù)之間的連接，調(diào)試后又進(jìn)行了數(shù)據(jù)測試，并對結(jié)果進(jìn)行分析，并做了多次改進(jìn)和調(diào)試。在調(diào)試的過程中，我深刻的認(rèn)識到，對于計算機(jī)專業(yè)的學(xué)生來說，應(yīng)更好的掌握應(yīng)用軟件的分析方法和調(diào)試方法，應(yīng)該能夠熟練運用高級語言的程序調(diào)試器 DEBUG 調(diào)試程序。經(jīng)過這次課程設(shè)計，我真的學(xué)到了很多東西，一方面鞏固和加深了我對數(shù)據(jù)結(jié)構(gòu)這門課程的理解，在實際應(yīng)用方面也較以前有了很大的進(jìn)步。在設(shè)計的過程難免會遇到很多問題，此時千萬不要氣餒，解決問題的方法可以有很多，可以通過網(wǎng)絡(luò)、書籍等方法進(jìn)行需求信息的查找，尋求他人幫助自然也是一個好辦法，但我個人覺得更多的應(yīng)該是自己獨立思考，才能達(dá)到提升自己分析問題、解決問題的能力

14、作用。此次課程設(shè)計將我們所學(xué)的理論知識和實際運用進(jìn)行了一次很好的連接，有利于加強(qiáng)我們用理論知識來分析實際問題的能力，進(jìn)而加強(qiáng)了我們對知識認(rèn)識的實踐度，鞏固了我們的理論知識，深化了對知識的認(rèn)識，并為走向社會打下一個良好的基礎(chǔ)。當(dāng)然在這次課程設(shè)計中除了程序本身的問題外，我也發(fā)現(xiàn)了很多別的問題，發(fā)現(xiàn)自己的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)還不是很扎實，還有很多需要改進(jìn)和努力的地方，在今后的學(xué)習(xí)中，我一定會努力地去鞏固我的基礎(chǔ)知識，并在實踐中加強(qiáng)應(yīng)用。在這次課程設(shè)計中我遇到不少問題和麻煩，在老師們和同學(xué)們的幫助和提示下，才能夠如此順利地完成了設(shè)計，在次對老師們表示真誠的感謝！五、用戶使用說明(1) 進(jìn)入程序運行界面后，出現(xiàn)

15、歡迎語并顯示執(zhí)行命令項(2) 用戶按程序提示進(jìn)行命令項的選擇(3) 按提示要求輸入待運算的表達(dá)式 ( 必須輸入合法的，不含變量并且以 #結(jié)束的表達(dá)第10頁式 )(4) 系統(tǒng)輸出運算結(jié)果，并重復(fù)（ 1）（ 3）的操作，需要退出時，可在（ 2）中進(jìn)行選擇六、測試結(jié)果(1) 輸入： 8#輸出 : The value of expression：8運行結(jié)果截圖為(2)輸入： 2-2-2-3#輸出： The value of expression：-5運行結(jié)果截圖為第11頁(3)輸入： 4+26/12-2*7#輸出： The value of expression：-8運行結(jié)果截圖為(4) 輸入： 18

16、-3*7-15/6#輸出： The value of expression：-5第12頁運行結(jié)果截圖為(5) 輸入： 2*(6+2*(3+6*(6+6)#輸出： The value of expression：312運行結(jié)果截圖為第13頁七、附錄源代碼#include #include #defineSTACK_INIT_SIZE 100/* 棧的存儲空間初始分配量 */#defineMAX100/* 字符存儲空間分配量 */#defineTURE1#defineERROR 0#defineOK1#defineFALSE 0#defineOVERFLOW -2typedefint SElemT

17、ype;/* 元素類型 */typedefint Status;typedef structSElemType *base;/* 在構(gòu)造之前和銷毀之后，base的值為 NULL*/SElemType *top;/* 棧頂指針 */int stacksize;/* 當(dāng)前已分配的存儲空間，以元素為單位*/SqStack;/* 結(jié)點類型和指針類型 */Status InitStack(SqStack *S)/* 構(gòu)造一個空棧 S*/S-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(S-base)exit(OVERFLO

18、W);/* 存儲空間分配失敗 */S-top=S-base;S-stacksize=STACK_INIT_SIZE;第14頁return OK;Status GetTop(SqStack S)if(S.topS.base)return(*(S.top-1);/* 棧不為空，返回棧頂元素*/elsereturn ERROR;/* 棧為空，返回 ERROR*/Status Push(SqStack *S,SElemType e) /* 插入元素 e*/*(S-top)+=e;return OK;/* 插入成功，返回 OK*/Status Pop(SqStack *S,SElemType *e)/*

19、 刪除棧頂元素，并用e 返回 */if(S-top=S-base)return ERROR;/* 棧為空，返回 ERROR*/*e=*(-(S-top);return OK;/* 棧不為空，刪除棧頂元素，返回OK*/第15頁Status judge(char op)/* 判斷是否為運算符 */ switch(op)case+: case-: case*: case/:case(:case):case#:return TURE;/* 是運算符，返回TURE*/default:return FALSE;/* 不是運算符，返回ERROR*/SElemType Operate(SElemType a,

20、char op,SElemType b)/* 對兩個整型數(shù)進(jìn)行算術(shù)運算op 為運算符 */switch(op)case+:return(a+b);/* 若為 + , 返回進(jìn)行加法運算的運算結(jié)果*/break;case-:return(a-b);/* 若為 - , 返回進(jìn)行減法運算的運算結(jié)果*/break;case*:return(a*b);/* 若為 * , 返回進(jìn)行乘法運算的運算結(jié)果*/break;第16頁case/:if(b!=0)return(a/b);/* 若為/,且除數(shù)不為 0 返回進(jìn)行除法運算的運算結(jié)果 */elseprintf(n0 can not do Divisor); /*

21、 除數(shù)為 0，提示錯誤 */ exit(0);char Precede(char a,char b) /* 比較運算符的優(yōu)先級 */ SElemType r;switch(a)case+:case-:/* +,-運算符的優(yōu)先級相同，故放在一起進(jìn)行比較 */if(b=*|b=/|b=()r=;break;case*:case/:/* , /運算符的優(yōu)先級相同，故放在一起進(jìn)行比較 */if(b=()r=;break;case(:if(b=#)printf(nLogic expression error！There is no right bracket！ );/* 邏輯錯誤，只有左括號，缺少右括號

22、*/return(0);elseif(b=)r=;else r=;break;case#:if(b=)printf(nLogic expression error!There is no left bracket!);/* 邏第18頁輯錯誤，只有右括號，缺少左括號*/return(0);elseif(b=#)r=;/* 運算結(jié)束標(biāo)志 */else r=0&c=9)第19頁sum=(sum*10+(c-0);c=getchar();Push(&OPND,sum);/* 不是運算符進(jìn)棧 */sum=0;elseswitch(Precede(GetTop(OPTR)+0),c)/* 算符優(yōu)先級比較 */case:/* 棧頂元素