算術(shù)表達式求值

1、第 1 頁算術(shù)表達式求值演示、需求分析(1) 輸入的形式：語法正確的、不含變量的字符序列形式的整數(shù)表達式 輸入值的范圍：整數(shù)的范圍是 (2 15-l)(2 15-1)運算符： +，-，*，/ ，(，)表達式結(jié)束運算符 #(2) 輸出的形式：范圍是 (2 15-l)(2 15-1) 的整數(shù)(3) 程序所能達到的功能：實現(xiàn)對算術(shù)四則混合運算表達式的求值 ; 程序執(zhí)行命令包括：1) Calculate計算表達式的值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

2、*(6+2*(3+6*(6+6) ；演示程序以用戶與計算機交互方式執(zhí)行，即在計算機終端上顯示 后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)據(jù) 的 非法字符 ) 和運算結(jié)果顯示在其后。、概要設(shè)計(1) 為實現(xiàn)上述程序功能需要的抽象數(shù)據(jù)類型：1) 棧的抽象數(shù)據(jù)類型：ADT Stack數(shù)據(jù)對象：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)造一個空棧。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):比較兩個字符的優(yōu)先級，并返回比較結(jié)果。Operate(SElemType a,char op,SElemType b):函數(shù)進行四則運算，并返回運算結(jié)果。judge(char op):判斷是否為運算符。EvaluateExpression() ：進行四則混合運算，并返回運算結(jié)

4、果。(2) 本次程序設(shè)計中一共有三個模塊，一個是由主函數(shù)構(gòu)成的模塊，一個是由各個子 功能函數(shù)構(gòu)成的棧模塊 , 第三個是由運算等函數(shù)構(gòu)成的運算模塊。(3) 主模塊可以對子模塊中的函數(shù)進行調(diào)用，但子模塊不能對主模塊中的內(nèi)容進行調(diào) 用；子模塊中的函數(shù)可相互調(diào)用。具體函數(shù)調(diào)用關(guān)系如下：main 調(diào)用 EvaluateExpression()EvaluateExpression() 調(diào) 用 Precede 、 Operate 、 judge 、 InitStack()GetTop、 Push 、Pop。三、詳細設(shè)計typedef int Status;typedef int SEIemType; /元素

5、類型typedef structSEIemType *base;SEIemType *top;int stacksize;SqStack; /結(jié)點類型和指針類型第 3頁(3) 棧的基本操作定義如下： Status InitStack(SqStack *S);/ 構(gòu)造一個空棧 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);/進行運算符的優(yōu)先級比較，并返回比較結(jié)果。SElemType Operate(SElemType a,char op,SElemType b);/進行兩個整數(shù)數(shù)的四則運算，并返回運算結(jié)果。Status judge(char op)/判斷是否為運算符。SElemType EvaluateExpression()/進行四則混合運算，并返回運算結(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)先級比較SElemType r;switch(a)case'+':case'-': /+', '-&

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

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

10、#39;)printf("nLogic expression error!There is no left bracket!");return( 0' ) ; / 邏輯錯誤，只有右括號，缺少左括號else if(b='#')r='=' else r='<'break; return(r);SElemType Operate(SElemType a,char op,SElemType b) / 進行算數(shù)運算 op 為運算符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;聲明各個變量初始化創(chuàng)建運算符棧'#'所對的整型量進運算符棧創(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); / 不是運算符進棧sum

13、=0;elseswitch(Precede(GetTop(OPTR)+'0'),c)case'<': / 棧頂元素優(yōu)先級低Push(&OPTR,(c-'0');c=getchar();break;case'=': /托括號并接受下一個字符Pop(&OPTR,&x);c=getchar();break;case'>': /棧頂元素優(yōu)先級高，退棧并將運算結(jié)果進棧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='#' / 邏輯錯誤， 0 進棧 ，并結(jié)束運算 break;return (GetTop(OPND);四、調(diào)試分析(1) 在調(diào)試過程中遇到的兩大問題：1)如何進行超過一位的數(shù)的存儲 原因分析：按照預(yù)想的想法，對表達式進行實際操作時發(fā)現(xiàn)，當(dāng)輸入超過一 位的數(shù)時，在程序的運行過程中，只進行了數(shù)的最低位的運算： 例如 1+15#，由于系統(tǒng)將 15 進行兩個字符處理后仍按兩個字符進

15、行進棧存儲，使得實際運行結(jié)果為 6，顯然是錯誤的 解決方案：對操作數(shù)的進棧存儲程序進行優(yōu)化，使其能將多位數(shù)視為單個字 符進行進棧存儲 具體程序由原來的 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)然，在聲明變量時已經(jīng)對sum進行了初始化：sum=02) 如何進行數(shù)的轉(zhuǎn)換原因分析：最

16、初對站內(nèi)元素類型的定義為 char ，但進行運算時發(fā)現(xiàn)其運算 或則是運算的結(jié)果均不能超過 128，這是由 char 類型本身的性 決定的解決方案：將棧內(nèi)元素的類型定義為 int ，無論是運算符，還是數(shù)字字符，在 進棧之前都進行( - 0')操作，對于已經(jīng)整型化的數(shù)字字符在進 行其后的運算或進棧時不用在進行數(shù)的轉(zhuǎn)換， 但是由于個人程序的 編制要求，運算符在出棧時仍需要進行相關(guān)的操作( +0')，即將 運算符重新字符化(2) 實驗總結(jié)：經(jīng)過本次課程設(shè)計，我深刻地感受到數(shù)據(jù)結(jié)構(gòu)的重要性， 數(shù)據(jù)結(jié)構(gòu)是計算機專 業(yè)很重要的一門課程，也是必須要熟練掌握的課程。本次課程設(shè)計， 我選擇的項目是

17、算術(shù)表達式的求值 , 它的實現(xiàn)主要是棧的應(yīng)用， 所 以，通過這次的實習(xí)，特別加深了我對棧這一數(shù)據(jù)類型的理解，在實際應(yīng)用中也比以 前更加得心應(yīng)手。另外，在本次的程序設(shè)計中，我還切身的體會到不同的類型的數(shù)據(jù) 的實際意義，一個程序可能會因為元素類型定義不當(dāng)而永遠得不到預(yù)期得結(jié)果。在本 次課程設(shè)計當(dāng)中，在做完需求分析和概要設(shè)計后，我又進行了詳細設(shè)計，經(jīng)過一番分 析之后，我首先對自己需要的模塊進行了詳細的編寫，在確保各個功能模塊的可行性 以及正確性后，進行了與主函數(shù)、函數(shù)與函數(shù)之間的連接，調(diào)試后又進行了數(shù)據(jù)測試， 并對結(jié)果進行分析，并做了多次改進和調(diào)試。在調(diào)試的過程中，我深刻的認識到，對 于計算機專業(yè)的

18、學(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)用方面也較以前有了很大的進步。在設(shè)計的過程難免會遇 到很多問題，此時千萬不要氣餒，解決問題的方法可以有很多，可以通過網(wǎng)絡(luò)、書籍 等方法進行需求信息的查找，尋求他人幫助自然也是一個好辦法，但我個人覺得更多 的應(yīng)該是自己獨立思考，才能達到提升自己分析問題、解決問題的能力作用。此次課程設(shè)計將我們所學(xué)的理論知識和實際運用進行了一次很好的連接，有利于 加強我們用理論知識來分析實際問題的能力，進而加

19、強了我們對知識認識的實踐度， 鞏固了我們的理論知識，深化了對知識的認識，并為走向社會打下一個良好的基礎(chǔ)。 當(dāng)然在這次課程設(shè)計中除了程序本身的問題外，我也發(fā)現(xiàn)了很多別的問題，發(fā)現(xiàn)自己 的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)還不是很扎實，還有很多需要改進和努力的地方，在今后的學(xué)習(xí)中， 我一定會努力地去鞏固我的基礎(chǔ)知識，并在實踐中加強應(yīng)用。在這次課程設(shè)計中我遇到不少問題和麻煩，在老師們和同學(xué)們的幫助和提示下， 才能夠如此順利地完成了設(shè)計，在次對老師們表示真誠的感謝！五、用戶使用說明(1) 進入程序運行界面后，出現(xiàn)歡迎語并顯示執(zhí)行命令項(2) 用戶按程序提示進行命令項的選擇(3) 按提示要求輸入待運算的表達式 ( 必須輸入合

20、法的，不含變量并且以 #結(jié)束的表達第 9 頁式）（4）系統(tǒng)輸出運算結(jié)果，并重復(fù)（1）（3）的操作，需要退出時，可在（2）中進行 選擇六、測試結(jié)果（1）輸入：8#輸出：The value of expression: 8運行結(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運行結(jié)果截圖為第13頁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運行結(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運行結(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運行結(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;/* 棧的存儲空間初始分配量 */*元素類型 */* 字符存儲空間分配量 */SElemType *top;/*棧頂指針 */int stacksize;/*當(dāng)前已分配的存儲空間，以元素為單位 */SqStack;/*結(jié)點類型和指針類型 */*在構(gòu)造之前和銷毀之后，base的值為NULL*/Status InitStack(SqStack *S)/*構(gòu)造一個空棧 S*/S->base=

28、(SElemType *)malloc(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)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) /* 判斷是否為運算符 */switch(op)case'+':case'-'

30、;:case'*':case'/':case'(':case')':case'#':return TURE;/* 是運算符，返回 TURE*/default:return FALSE;/* 不是運算符，返回 ERROR*/SElemType Operate(SElemType a,char op,SElemType b) /*對兩個整型數(shù)進行算術(shù)運算op為運算符*/switch(op)case'+':return(a+b);/*若為' +', 返回進行加法運算的運算結(jié)果 */brea

31、k;case'-':return(a-b);/*若為' -', 返回進行減法運算的運算結(jié)果 */break;case'*':return(a*b);/* 若為' *', 返回進行乘法運算的運算結(jié)果 */ break;case'/':if(b!=0)return(a/b);/* 若為'/',且除數(shù)不為 0 返回進行除法運算的運算結(jié)果*/elseprintf("n0 can not do Divisor"); /* 除數(shù)為 0，提示錯誤 */exit(0);char Precede(

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

33、f(b='(') r='<'第 17 頁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曰輯錯誤，只有右括號，缺少左括號 */return('0');elseif(b='#')r='='/* 運算結(jié)束標(biāo)志 */else r='<'break;return(r);/* 返回比較結(jié)果 */SElemType EvaluateExpression()/* 算術(shù)表達式求值的算符優(yōu)先級運算 */SqStack OPTR,OPND;SElemType a,b,e,m,n,sum,theta,x;char c;/* 聲明函數(shù)

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