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

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

2、行，即在計(jì)算機(jī)終端上顯示提示信息 之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令；相應(yīng)的輸入數(shù)據(jù) ( 濾去輸入中的 非法字符 ) 和運(yùn)算結(jié)果顯示在其后。二、概要設(shè)計(jì)(1) 為實(shí)現(xiàn)上述程序功能需要的抽象數(shù)據(jù)類型：1) 棧的抽象數(shù)據(jù)類型：ADT Stack數(shù)據(jù)對(duì)象： 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)造一個(gè)空棧。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):比較兩個(gè)字符的優(yōu)先級(jí)，并返回比較結(jié)果。Operate(SElemType a,char op,SElemType b):函數(shù)進(jìn)行四則運(yùn)算，并返回運(yùn)算結(jié)果。judge(char op):判斷是否為運(yùn)算符。EvaluateExpression()：進(jìn)行四則混合運(yùn)算，并返回運(yùn)算結(jié)果。(2) 本次程序設(shè)計(jì)中一共有三個(gè)模塊，一個(gè)是由主函數(shù)構(gòu)成的模塊，一個(gè)是由各個(gè)子功能函數(shù)構(gòu)成

4、的棧模塊 , 第三個(gè)是由運(yùn)算等函數(shù)構(gòu)成的運(yùn)算模塊。(3) 主模塊可以對(duì)子模塊中的函數(shù)進(jìn)行調(diào)用，但子模塊不能對(duì)主模塊中的內(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è)計(jì)(1) 程序流程圖：脫括號(hào)（接受下一個(gè)字符）Operate 求值最終結(jié)果出棧結(jié)束(2) 元素類型、結(jié)點(diǎn)類型和指針類型typedef intStatus;typedef intSElemT

5、ype; /元素類型typedef structSElemType*base;SElemType*top;intstacksize;SqStack;/結(jié)點(diǎn)類型和指針類型第3頁(3) 棧的基本操作定義如下：Status InitStack(SqStack *S);/ 構(gòu)造一個(gè)空棧 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ùn)算符的優(yōu)先級(jí)比較，并返回比較結(jié)果。SElemType Operate(SElemType a,char op,SElemType b);/ 進(jìn)行兩個(gè)整數(shù)數(shù)的四則運(yùn)算，并返回運(yùn)算結(jié)果。Status judge(char op)/ 判斷是否為運(yùn)算符。SElemType EvaluateExpression()/ 進(jìn)行四則混合運(yùn)算，并返回運(yù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)先級(jí)比較 SElemType r;switch(a)case+:case-:/+, - 運(yùn)算符優(yōu)先級(jí)相同， 故放在一起進(jìn)行比較if(b=

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

9、缺少左括號(hào)elseif(b=#)r=;else r=0&c=9)sum=(sum*10+(c-0);c=getchar();Push(&OPND,sum);/不是運(yùn)算符進(jìn)棧sum=0;elseswitch(Precede(GetTop(OPTR)+0),c)case:/棧頂元素優(yōu)先級(jí)高，退棧并將運(yùn)算結(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=#;/邏輯錯(cuò)誤， 0 進(jìn)棧 ，并結(jié)束運(yùn)算break;第8頁retu

10、rn (GetTop(OPND);四、調(diào)試分析(1) 在調(diào)試過程中遇到的兩大問題：1）如何進(jìn)行超過一位的數(shù)的存儲(chǔ)原因分析：按照預(yù)想的想法，對(duì)表達(dá)式進(jìn)行實(shí)際操作時(shí)發(fā)現(xiàn)，當(dāng)輸入超過一位的數(shù)時(shí)，在程序的運(yùn)行過程中，只進(jìn)行了數(shù)的最低位的運(yùn)算：例如 1+15#，由于系統(tǒng)將 15 進(jìn)行兩個(gè)字符處理后仍按兩個(gè)字符進(jìn)行進(jìn)棧存儲(chǔ)，使得實(shí)際運(yùn)行結(jié)果為 6，顯然是錯(cuò)誤的解決方案：對(duì)操作數(shù)的進(jìn)棧存儲(chǔ)程序進(jìn)行優(yōu)化，使其能將多位數(shù)視為單個(gè)字符進(jìn)行進(jìn)棧存儲(chǔ)具體程序由原來的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)然，在聲明變量時(shí)已經(jīng)對(duì)sum進(jìn)行了初始化： sum=0。2) 如何進(jìn)行數(shù)的轉(zhuǎn)換原因分析：最初對(duì)站內(nèi)元素類型的定義為char ，但進(jìn)行運(yùn)算時(shí)發(fā)現(xiàn)其運(yùn)算或則是運(yùn)算的結(jié)果均不能超過128，這是由 char 類型本身的性決定的解決方案：將棧內(nèi)元素的類型定義為int ，無論是運(yùn)算符，還是數(shù)字字符，在第9頁進(jìn)棧之前都進(jìn)行（ - 0）操作，對(duì)于已經(jīng)整型化的數(shù)字字符在進(jìn)行其后的運(yùn)算或進(jìn)棧時(shí)不用在進(jìn)行數(shù)的轉(zhuǎn)換， 但是由于個(gè)人程序的編制要求，運(yùn)算符在出棧時(shí)仍需要進(jìn)行相關(guān)的操作（ +0），即將運(yùn)算符重新字符化(2) 實(shí)驗(yàn)總

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

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

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

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

16、-3*7-15/6#輸出： The value of expression：-5第12頁運(yùn)行結(jié)果截圖為(5) 輸入： 2*(6+2*(3+6*(6+6)#輸出： The value of expression：312運(yùn)行結(jié)果截圖為第13頁七、附錄源代碼#include #include #defineSTACK_INIT_SIZE 100/* 棧的存儲(chǔ)空間初始分配量 */#defineMAX100/* 字符存儲(chǔ)空間分配量 */#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)前已分配的存儲(chǔ)空間，以元素為單位*/SqStack;/* 結(jié)點(diǎn)類型和指針類型 */Status InitStack(SqStack *S)/* 構(gòu)造一個(gè)空棧 S*/S-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(S-base)exit(OVERFLO

18、W);/* 存儲(chǔ)空間分配失敗 */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)/* 判斷是否為運(yùn)算符 */ switch(op)case+: case-: case*: case/:case(:case):case#:return TURE;/* 是運(yùn)算符，返回TURE*/default:return FALSE;/* 不是運(yùn)算符，返回ERROR*/SElemType Operate(SElemType a,

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

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

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