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

1、第 1 頁(yè)算術(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

2、*(6+2*(3+6*(6+6) ；演示程序以用戶與計(jì)算機(jī)交互方式執(zhí)行，即在計(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|ai elemset, i=1,2,n , n0 數(shù)據(jù)關(guān)系：R1=<ai-1 , ai >| ai-1 , ai D, i=2，n 基本操作：InitStack() 操作結(jié)果：構(gòu)造一個(gè)空棧。GetTop(S， &e) 初始條件：棧 S 已存在且非空。操作結(jié)果：

3、用e返回S的棧頂元素。Push(&S ， e)初始條件：棧S已存在。操作結(jié)果：插入元素 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é)

4、果。(2) 本次程序設(shè)計(jì)中一共有三個(gè)模塊，一個(gè)是由主函數(shù)構(gòu)成的模塊，一個(gè)是由各個(gè)子 功能函數(shù)構(gòu)成的棧模塊 , 第三個(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。三、詳細(xì)設(shè)計(jì)typedef int Status;typedef int SEIemType; /元素

5、類型typedef structSEIemType *base;SEIemType *top;int stacksize;SqStack; /結(jié)點(diǎn)類型和指針類型第 3頁(yè)(3) 棧的基本操作定義如下： Status InitStack(SqStack *S);/ 構(gòu)造一個(gè)空棧 SStatus GetTop(SqStack S)/若棧不空，則返回棧頂元素，否則返回ERRORStatus Push(SqStack *S,SElemType e);/插入 e 為新的棧頂元素Status Pop(SqStack *S,SElemType *e);/若棧不空，貝U刪除S的棧頂元素，用e返回其值，返回0K否

6、則返回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)*(S->top)+=e;ret

7、urn OK; /插入元素 e 為新的棧頂元素Status Pop(SqStack *S,SElemType *e)if(S->top=S->base)return ERROR; / 若棧為空，返回 ERROR*e=*(-(S->top);return OK; /棧不為空，刪除S的棧頂元素，用e返回其值，并返回OK char 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'-': /+', '-&

8、#39;運(yùn)算符優(yōu)先級(jí)相同， 故放在一起進(jìn)行比較if(b='*'|b='/'|b='(')r='<' else r='>'/ '運(yùn)算符優(yōu)先級(jí)相同，故放在一起進(jìn)行比較break;case'*': /case'/':if(b='(') r='<' else r='>'case'(':if(b='#')printf("nLogicbracket！");retur

9、n(0')break;expression error ！There is no right/ 邏輯錯(cuò)誤，只有左括號(hào)，缺少右括號(hào)else if(b=')')r='=' else r='<'break; case')':if(b='(') printf("nMatching errors in brackets! "); return( 0' ) ; / 括號(hào)匹配錯(cuò)誤else r='>'break;case'#':if(b=')&

10、#39;)printf("nLogic expression error!There is no left bracket!");return( 0' ) ; / 邏輯錯(cuò)誤，只有右括號(hào)，缺少左括號(hào)else if(b='#')r='=' else r='<'break; return(r);SElemType Operate(SElemType a,char op,SElemType b) / 進(jìn)行算數(shù)運(yùn)算 op 為運(yùn)算符switch(op)case'+':return(a+b);break;cas

11、e'-':return(a-b);break;case'*':return(a*b);break;case'/':if(b!=0) return(a/b);elseprintf("n0 can not do Divisor");return( 0' ) ;SElemType EvaluateExpression()SqStack OPTR,OPND;聲明各個(gè)變量初始化創(chuàng)建運(yùn)算符棧'#'所對(duì)的整型量進(jìn)運(yùn)算符棧創(chuàng)建操作數(shù)棧SElemType a,b,e,sum,theta,x; char c; / sum=

12、0; / InitStack(&OPTR);/Push(&OPTR,('#'-'0');/InitStack(&OPND);/c=getchar();while(c!='#'|GetTop(OPTR)!=('#'-'0') if(!judge(c)while(c>='0'&&c<='9')sum=(sum*10+(c-'0');c=getchar();Push(&OPND,sum); / 不是運(yùn)算符進(jìn)棧sum

13、=0;elseswitch(Precede(GetTop(OPTR)+'0'),c)case'<': / 棧頂元素優(yōu)先級(jí)低Push(&OPTR,(c-'0');c=getchar();break;case'=': /托括號(hào)并接受下一個(gè)字符Pop(&OPTR,&x);c=getchar();break;case'>': /棧頂元素優(yōu)先級(jí)高，退棧并將運(yùn)算結(jié)果進(jìn)棧Pop(&OPTR,&theta);Pop(&OPND,&b);Pop(&OPND,

14、&a);e=Operate(a,(theta+'0'),b);Push(&OPND,e);break;case'0':Push(&OPND,0);c='#' / 邏輯錯(cuò)誤， 0 進(jìn)棧 ，并結(jié)束運(yùn)算 break;return (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)

15、行進(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=(sum*10+(c-'0'); c=getchar();Push(&OPND,sum);sum=0;當(dāng)然，在聲明變量時(shí)已經(jīng)對(duì)sum進(jìn)行了初始化：sum=02) 如何進(jìn)行數(shù)的轉(zhuǎn)換原因分析：最

16、初對(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ù)字字符，在 進(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)總結(jié)：經(jīng)過本次課程設(shè)計(jì)，我深刻地感受到數(shù)據(jù)結(jié)構(gòu)的重要性， 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專 業(yè)很重要的一門課程，也是必須要熟練掌握的課程。本次課程設(shè)計(jì)， 我選擇的項(xiàng)目是

17、算術(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ù)、函數(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è)的

18、學(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á)到提升自己分析問題、解決問題的能力作用。此次課程設(shè)計(jì)將我們所學(xué)的理論知識(shí)和實(shí)際運(yùn)用進(jìn)行了一次很好的連接，有利于 加強(qiáng)我們用理論知識(shí)來分析實(shí)際問題的能力，進(jìn)而加

19、強(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)歡迎語并顯示執(zhí)行命令項(xiàng)(2) 用戶按程序提示進(jìn)行命令項(xiàng)的選擇(3) 按提示要求輸入待運(yùn)算的表達(dá)式 ( 必須輸入合

20、法的，不含變量并且以 #結(jié)束的表達(dá)第 9 頁(yè)式）（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é)果截圖為WeIcome to th巴 expression fot* the vlue of smll procedure? I l.To calculate the expression2 . e x itPlease enter youl* choicePlease enter arithmet ic express ions to the end of the tt:

21、SttiThe ualue Qf express ion ：SlTo calculate the expressionPlea&e enter your choice =(2) 輸入：2-2-2-3#輸出：The value of expression : -5運(yùn)行結(jié)果截圖為第13頁(yè)2 exitPlease七咅¥ your choice：1Please enter ar it hmet ic express ions to the end of the tt:8ttThe value of expression:81. To calculate the expression2

22、-exitPlease enter youti* choice =1Please enter arithnetic expressions to the end of the tt =2-2-2-3ITThe value oF express ion：-5tTo calcuLate the express ion2. exitEntE於 atiuF choixE；(3) 輸入：4+26/12-2*7#輸出：The value of expression: -8運(yùn)行結(jié)果截圖為2 exitPlease enterchoice:1Please enter- arithmet ic express i

23、oto tlie end of tlie tt:2-2-2-3Uhe ualue of express ion:-51. .To calculate the expesiDn2 -exitPlease enter your choice：1Please entei arithmet ic express ions to the end of the tt:4+26zl2-2*7tthe ualue of express ion：-81_To calculate the expression2exitPlease entee vour choice = 輸入：18-3*7-15/6#輸出：The

24、 value of expression: -5運(yùn)行結(jié)果截圖為2.exitPlease enter your choice：1Please enter arithnetic expressionstotheend ofthett：4+26/12-2*7«The value of express ion-8Please enter your choice：1Please enter arithmetic expressionstheend oftheThe value of expression：-51 .To calculate the expression2. exitPlease

25、 entei* your clio ice -(5) 輸入：2*(6+2*(3+6*(6+6)#輸出：The value of expression: 312運(yùn)行結(jié)果截圖為2.exitPlease enter youti* cha ice : 1Please enter ar it hmetic expressions to the end of the It：18-3*715/611The value of expression J-5calculate the express ion2-exitPlease enter vauF clia ice -1Please enter arithe

26、tic expressions to the end of the 4 2*<6+2*C3+6*<6+6>>>#The value of expression：3121_To calculate the express ion2.exitPI儉辦s儘 entet-jrouF 右hujxE：七、附錄源代碼#include <stdio.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define MAX100#define TURE 1#define ERROR 0#define OK 1#d

27、efine FALSE 0#define OVERFLOW -2typedef int SElemType;typedef int Status;typedef structSElemType *base;/* 棧的存儲(chǔ)空間初始分配量 */*元素類型 */* 字符存儲(chǔ)空間分配量 */SElemType *top;/*棧頂指針 */int stacksize;/*當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 */SqStack;/*結(jié)點(diǎn)類型和指針類型 */*在構(gòu)造之前和銷毀之后，base的值為NULL*/Status InitStack(SqStack *S)/*構(gòu)造一個(gè)空棧 S*/S->base=

28、(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(S->base)exit(OVERFLOW); /*存儲(chǔ)空間分配失敗 */ S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;Status GetTop(SqStack S)if(S.top>S.base)return(*(S.top-1); /* 棧不為空，返回棧頂元素 */elsereturn ERROR;/* 棧為空，返回 ERROR*/Status Push(SqStack *S,

29、SElemType e) /* 插入元素 e*/*(S->top)+=e;return OK;/* 插入成功，返回 OK*/Status Pop(SqStack *S,SElemType *e) /* 刪除棧頂元素，并用 e 返回*/ /* 棧為空，返回 ERROR*/* 棧不為空，刪除棧頂元素，返回OK*/if(S->top=S->base) return ERROR;*e=*(-(S->top);return OK;Status judge(char op) /* 判斷是否為運(yùn)算符 */switch(op)case'+':case'-'

30、;:case'*':case'/':case'(':case')':case'#':return TURE;/* 是運(yùn)算符，返回 TURE*/default:return FALSE;/* 不是運(yùn)算符，返回 ERROR*/SElemType Operate(SElemType a,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é)果 */brea

31、k;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'/':if(b!=0)return(a/b);/* 若為'/',且除數(shù)不為 0 返回進(jìn)行除法運(yùn)算的運(yùn)算結(jié)果*/elseprintf("n0 can not do Divisor"); /* 除數(shù)為 0，提示錯(cuò)誤 */exit(0);char Precede(

32、char a,char b) /* 比較運(yùn)算符的優(yōu)先級(jí) */SElemType r;switch(a)case'+':/* '+','-'運(yùn)算符的優(yōu)先級(jí)相同，故放在/* '* ','/'運(yùn)算符的優(yōu)先級(jí)相同，故放在case'-':起進(jìn)行比較 */if(b='*'|b='/'|b='(') r='<'else r='>'break;case'*':case'/':起進(jìn)行比較 */i

33、f(b='(') r='<'第 17 頁(yè)break 八 case-?宀pinff(-VILOgic expression error 一 There is no righf bracked崩#>沛)n皿葉戰(zhàn)4n®eMnt4nrefuln(Q)八e-se宀if(bHHy)幾J1-e-se rHAr芒 2break 八=h(bHHd宀prinmvIMaohing errors in brackets-) -* 戰(zhàn)血目礙 *一refuln(Q)八e-se rHvrbreak 八casett.rif(bHy)宀pinff(-VILOgic expr

34、ession error一 There is no -eff bracked) 、*® w8曰輯錯(cuò)誤，只有右括號(hào)，缺少左括號(hào) */return('0');elseif(b='#')r='='/* 運(yùn)算結(jié)束標(biāo)志 */else r='<'break;return(r);/* 返回比較結(jié)果 */SElemType EvaluateExpression()/* 算術(shù)表達(dá)式求值的算符優(yōu)先級(jí)運(yùn)算 */SqStack OPTR,OPND;SElemType a,b,e,m,n,sum,theta,x;char c;/* 聲明函數(shù)

35、內(nèi)變量的類型 */sum=0;InitStack(&OPTR);/* 建立運(yùn)算符棧 */Push(&OPTR,('#'-'0');/* '#'所對(duì)的整型量進(jìn)運(yùn)算符棧 */InitStack(&OPND);/* 建立操作數(shù)棧 */c=getchar();while(c!='#'|GetTop(OPTR)!=('#'-'0')if(!judge(c) while(c>='0'&&c<='9')第 21 頁(yè)sum=(sum*10+(c-'0');c=getchar();Push(&OPND,sum)