數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-表達(dá)式求值

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：12 大?。?8.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-表達(dá)式求值_第1頁

已閱讀1頁，還剩11頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)　　表達(dá)式求值　　班級(jí)： 　　學(xué)號(hào)： 　　姓名： </p&

2、gt;　　指導(dǎo)老師： 　　表達(dá)式求值　　問題描述　　要求對(duì)包含加、減、乘、除、括號(hào)運(yùn)算符的任意整型表達(dá)式進(jìn)行求解。

3、設(shè)計(jì)思路　　這個(gè)程序的關(guān)鍵是對(duì)數(shù)字與運(yùn)算符的判斷和運(yùn)算符優(yōu)先級(jí)的判斷，以及出棧的運(yùn)算。建立兩個(gè)棧，分別存儲(chǔ)數(shù)字與運(yùn)算符，棧1存運(yùn)算符，棧2存數(shù)字。依次讀取表達(dá)式的字符串，先判斷是數(shù)字還是運(yùn)算符，如果是數(shù)字不能馬上壓入棧2，因?yàn)榭赡苁谴笥?0的數(shù)字，應(yīng)該繼續(xù)循環(huán)，如果還是數(shù)字，則利用計(jì)算保存數(shù)值，直到指到運(yùn)算符時(shí)停止，將計(jì)算后的數(shù)字壓入棧2。壓入運(yùn)算符之前先將要壓入的與棧頂?shù)倪\(yùn)

4、算符優(yōu)先級(jí)相比較，如果棧頂是‘（’而當(dāng)前不是‘）’，則不需比較優(yōu)先級(jí)，直接壓入；如果棧頂是‘（’，當(dāng)前是‘）’，則抵消（彈出‘（’，指向表達(dá)式下一個(gè)字符）；若當(dāng)前的運(yùn)算符優(yōu)先級(jí)大于棧頂?shù)?，則壓入；若當(dāng)前的運(yùn)算符優(yōu)先級(jí)小于棧內(nèi)時(shí)，彈出棧頂?shù)倪\(yùn)算符，同時(shí)彈出兩組數(shù)字，經(jīng)過運(yùn)算符的運(yùn)算后再重新壓到棧內(nèi)。為了方便判斷運(yùn)算結(jié)束，在存儲(chǔ)運(yùn)算符之前先將‘#’壓入棧1中，在輸入表達(dá)式時(shí)以“#”結(jié)束，所以可以以運(yùn)算符==‘#’并且棧1頂==‘#’來結(jié)束運(yùn)

5、算，彈出棧2的數(shù)值，即為表達(dá)式求值的最終結(jié)果。　　上述操作的算法步驟：　　初始化算符S1,數(shù)字棧S2;，將‘#’壓入算符棧S1中。　　讀表達(dá)式字符=>w。　　當(dāng)棧頂為‘#’并且w也是‘#’時(shí)結(jié)束；否則循環(huán)做下列步驟：　?。?

6、-1）如果w是數(shù)字，存儲(chǔ)到m，再經(jīng)過計(jì)算存儲(chǔ)到num中。m=w-‘0’;num=num*pow(10,n)+m;n++;讀下一個(gè)字符=>w，如果是運(yùn)算符，則跳出循環(huán)；轉(zhuǎn)3-2。　?。?-2）w若是運(yùn)算符，則：　?。?-2-1）如果棧頂為‘（’并且w為‘）’則‘（’出棧，讀下一個(gè)字符=>w；轉(zhuǎn)（3）。

7、　（3-2-2）如果棧頂為‘（’或者棧頂優(yōu)先級(jí)小于w優(yōu)先級(jí)，則w入棧，讀下一個(gè)字符=>w；轉(zhuǎn)（3）。否則：從算符棧中出棧，并從數(shù)字棧中彈出兩組數(shù)字進(jìn)行運(yùn)算，將結(jié)果重新壓入數(shù)字棧，轉(zhuǎn)（3）。　　數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)　　前面提到，要用棧存儲(chǔ)數(shù)據(jù)，由于一個(gè)數(shù)字一個(gè)運(yùn)算符，所以要定義兩個(gè)不同的棧，棧1的運(yùn)算符為字符型；棧2的數(shù)

8、字為浮點(diǎn)型，以便運(yùn)算大數(shù)字。再給存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)加個(gè)上制。具體結(jié)構(gòu)定義如下：　　#define MAXSIZE 100　　typedef struct{　　char data[MAXSIZE]; /*字符型，存儲(chǔ)運(yùn)算符*/　　in

9、t top;　　}charSeqStack,*charPSeqStack;　　typedef struct{　　double data[MAXSIZE]; /*浮點(diǎn)型，存儲(chǔ)數(shù)字*/　　int top;</b

10、>　　}SeqStack,*PSeqStack;　　功能函數(shù)設(shè)計(jì)　?。?）判斷操作數(shù)的函數(shù)isnum()　　判斷當(dāng)前所指字符是否屬于數(shù)字，是就返回‘1’，不是返回‘0’。　　（2）求運(yùn)算

11、符優(yōu)先級(jí)函數(shù)priority()　　為了方便判斷運(yùn)算符優(yōu)先級(jí)，先利用switch函數(shù)將不同的運(yùn)算符返回不同的整型數(shù)字，再根據(jù)數(shù)字的大小判斷優(yōu)先級(jí)?！?’、‘-’優(yōu)先級(jí)相同，返回相同數(shù)字，‘*’、‘/’也是。　?。?）表達(dá)式求值函數(shù)infix_value()　　此函數(shù)是直接按照設(shè)計(jì)思路完成問題要求的函數(shù)，其中要調(diào)用

12、到判斷操作符的函數(shù)isnum()和求運(yùn)算符優(yōu)先級(jí)的函數(shù)priority()。循環(huán)結(jié)束彈出棧2的數(shù)值，并返回。　　主函數(shù)main()　　定義一個(gè)數(shù)組存儲(chǔ)表達(dá)式整個(gè)字符串，將返回的數(shù)值直接賦到浮點(diǎn)型的result，輸出result。　　兩個(gè)棧的函數(shù)設(shè)計(jì)：<

13、/b>　　棧的初始化函數(shù)charInit_SeqStack()　　Init_SeqStack()　　判?？?Empty_SeqStack()　　charEmpty_SeqStack()　　入棧函數(shù)

14、Push_SeqStack()　　charPush_SeqStack()　　出棧函數(shù) Pop_SeqStack()　　charPop_SeqStack()　　取棧頂函數(shù) GetTop_SeqStack()　　c

15、harGetTop_SeqStack()　　銷毀棧 Destroy_SeqStack()　　charDestroy_SeqStack()　　程序代碼　　#include<stdio.h>

16、　　#include<stdlib.h>　　#include<math.h>　　#define MAXSIZE 100　　typedef struct{　　double data[MAXSIZE];<

17、;p>　　int top;　　}SeqStack,*PSeqStack;　　typedef struct{　　char data[MAXSIZE];　　int top;

18、　　}charSeqStack,*charPSeqStack; /*定義棧，兩個(gè)不同的存儲(chǔ)類型*/　　PSeqStack Init_SeqStack(void)　　{　　PSeqStack S;

19、S=(PSeqStack)malloc(sizeof(SeqStack));　　if(S)　　S->top=-1;　　return S;　　}</

20、p>　　charPSeqStack charInit_SeqStack(void)　　{　　charPSeqStack S;　　S=(charPSeqStack)malloc(sizeof(charSeqStack));&l

21、t;p>　　if(S)　　S->top=-1;　　return S;　　} /*棧的初始化函數(shù)*/　　int

22、 Empty_SeqStack(PSeqStack S)　　{　　if(S->top==-1)　　return 1;　　else

23、　　return 0;　　}　　int charEmpty_SeqStack(charPSeqStack S)　　{　　if(S->t

24、op==-1)　　return 1;　　else　　return 0;　　}

25、 /*判斷棧空函數(shù)*/　　int Push_SeqStack(PSeqStack S,double x)　　{　　if(S->top==MAXSIZE-1)　　return 0;</p

26、>　　else　　{　　S->top++;　　S->data[S->top]=x;　　retu

27、rn 1;　　}　　}　　int charPush_SeqStack(charPSeqStack S,char x)　　{</p&g

28、t;　　if(S->top==MAXSIZE-1)　　return 0;　　else　　{　　S->top

29、++;　　S->data[S->top]=x;　　return 1;　　}　　}

30、 /*入棧函數(shù)*/　　int Pop_SeqStack(PSeqStack S,double *x)　　{　　if(Empty_SeqStack(S))　　return 0;

31、　　else　　{　　*x=S->data[S->top];　　S->top--;　　return

32、1;　　}　　}　　int charPop_SeqStack(charPSeqStack S,char *x)　　{

33、　　if(charEmpty_SeqStack(S))　　return 0;　　else　　{　　*x=S->data[S->

34、top];　　S->top--;　　return 1;　　}　　}

35、/*出棧函數(shù)*/　　int GetTop_SeqStack(PSeqStack S,double *x)　　{　　if(Empty_SeqStack(S))　　return 0;

36、;　　else　　*x=S->data[S->top];　　return 1;　　}　　int charGetTop_Seq

37、Stack(charPSeqStack S,char *x)　　{　　if(charEmpty_SeqStack(S))　　return 0;　　else&l

38、t;/p>　　*x=S->data[S->top];　　return 1;　　} /*取棧頂函數(shù)*/　　void Destroy_SeqStack(P

39、SeqStack *S)　　{　　if(*S)　　free(*S);　　*S=NULL;<

40、p>　　return;　　}　　void charDestroy_SeqStack(charPSeqStack *S)　　{　　if(

41、*S)　　free(*S);　　*S=NULL;　　return;　　}

42、 /*銷毀棧*/　　int isnum(char c) /*判斷字符是否為操作符*/　　{　　if(c>='0'&&c<='9')

43、　　return 1;　　else 　　return 0;　　} 　　int priority(c

44、har op) /*求運(yùn)算符的優(yōu)先級(jí)*/　　{　　switch(op)　　{　　case'=':return 1;&l

45、t;p>　　case')':return 2;　　case'+':　　case'-':return 3;　　case'*':

46、　case'/':return 4;　　case'(':return 5;　　default:return 0;　　}　　}

47、;　　double infix_value(char *infix) /*表達(dá)式求值函數(shù)，infix為表達(dá)式字符串*/　　{　　charPSeqStack S1;　　PSeqStack S2; /*S1為算符棧，S2為

48、數(shù)字棧*/　　char c,w,tope;　　double n,num,m,result,s1,s2;　　S2=Init_SeqStack();　　S1=charInit_SeqStack(); /*初始化棧*/<p&

49、gt;　　if(!S1)　　{　　printf("棧初始化失敗");　　return 0;　　}&l

50、t;/p>　　if(!S2)　　{　　printf("棧初始化失敗");　　return 0;

51、;　　}　　charPush_SeqStack(S1,'#'); /*先將‘#’壓入算符棧，便于判斷結(jié)束*/　　w=*infix; /*讀表達(dá)式字符*/　　while((charGetTop_SeqStack(S1,&c),

52、c)!='#'||w!='#')　　{　　num=n=0;　　while(isnum(w)) 　　{</

53、p>　　m=w-'0';　　num=num*pow(10,n)+m; /*求出正確的數(shù)字*/　　w=*(++infix);　　n++; /*n要不斷自加*/<p

54、>　　}　　if(n!=0)Push_SeqStack(S2,num); /*若讀過數(shù)字，則將num值壓入數(shù)字棧*/　　if((charGetTop_SeqStack(S1,&c),c)=='('&&w==')')

55、;　　{　　charPop_SeqStack(S1,&tope);　　w=*(++infix); /*兩括號(hào)相遇，銷毀，讀下一個(gè)字符*/　　}　　else if((

56、charGetTop_SeqStack(S1,&c),c)=='('||　　priority((charGetTop_SeqStack(S1,&c),c))<priority(w))/*比較運(yùn)算符*/　　{　　charPush_SeqSt

57、ack(S1,w);　　w=*(++infix); 　　}　　else 　　{　　char

58、Pop_SeqStack(S1,&tope);　　Pop_SeqStack(S2,&s2);　　Pop_SeqStack(S2,&s1);　　switch(tope)　　{<p&g

59、t;　　case'+' : num=s1+s2;break;　　case'-' : num=s1-s2;break;　　case'*' : num=s1*s2;break;　　case'/' : num=s1/s2;break; /*彈出運(yùn)

60、算符的同時(shí)進(jìn)行運(yùn)算*/　　}　　Push_SeqStack(S2,num); /*將運(yùn)算結(jié)果重新壓入棧2*/　　}　　} /*while((charGetTop_SeqStack(S1

61、,&c),c)!='#'||w!='#')*/　　return result;　　}　　void main()　　{

62、;　　char number[MAXSIZE]; /*存儲(chǔ)表達(dá)式*/　　double result; /*表達(dá)式結(jié)果*/　　gets(number); /*輸入表達(dá)式*/　　result=infix_valu

63、e(number);　　printf("%lf\n",result); /*輸出結(jié)果*/　　getch();　　}　　運(yùn)行與測(cè)試

64、　　7、設(shè)計(jì)心得　　表達(dá)式求值是當(dāng)初老師在教棧這個(gè)內(nèi)容時(shí)經(jīng)常提到的問題，并且也在黑板上演示過，所以在設(shè)計(jì)思想上基本已經(jīng)有了框架，寫起來也就方便多了，但依然也有些問題不斷的出現(xiàn)。首先就是存運(yùn)算符和數(shù)字的問題了，我不知在入棧和出棧時(shí)如何能將它們的類型合理的轉(zhuǎn)化，所以只好定義兩個(gè)棧，以至于這個(gè)程序看起來

65、太“啰嗦”。在運(yùn)行調(diào)試時(shí)曾遇見一個(gè)大問題，程序讀不了10以上的數(shù)字，很快便找到了問題所在，在功能函數(shù)里，它每讀一個(gè)數(shù)字便直接入棧，下一個(gè)若是數(shù)字便存在棧的下一個(gè)地址內(nèi)了。于是我以while循環(huán)控制它何時(shí)入棧，將大數(shù)計(jì)算好了再入棧。在調(diào)試過程中還曾遇見了一個(gè)問題，就是出棧運(yùn)算時(shí)將兩個(gè)數(shù)字前后弄反了，應(yīng)該是后出棧的-‘運(yùn)算符’-前出棧的。　　寫完了表達(dá)式求值使我又加深了對(duì)棧的知識(shí)與運(yùn)用，也讓我意識(shí)到

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-表達(dá)式求值

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-表達(dá)式求值

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載