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

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

2023年全國(guó)碩士研究生考試考研英語一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

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

文檔簡(jiǎn)介

1、　　目錄　　1概述3　　1.1目的及意義3　　2系統(tǒng)分析3　　2.1需求分析3</p&

2、gt;　　3概要設(shè)計(jì)3　　3.1系統(tǒng)總體結(jié)構(gòu)3　　3.2程序算法圖3　　4詳細(xì)設(shè)計(jì)4　　4.1中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式4

3、　　4.1.1求運(yùn)算符優(yōu)先級(jí)函數(shù)5　　4.1.2輸出隊(duì)列5　　4.2后綴表達(dá)式的求值5　　5運(yùn)行與測(cè)試6　　5.1 輸入表達(dá)式：6　　5.2 輸出結(jié)果：6&

4、lt;p>　　6總結(jié)和心得6　　6.1心得與問題6　　6.2總結(jié)6　　參考文獻(xiàn)7　　1概述</p&g

5、t;　　1.1目的及意義　　我們?cè)诤茉绲臅r(shí)候就開始學(xué)習(xí)書寫及計(jì)算表達(dá)式，可以說運(yùn)用起來很熟練了，但有時(shí)候并不想自己計(jì)算，交給計(jì)算器是時(shí)有的事，然而普通的計(jì)算器并不懂得優(yōu)先級(jí)，給計(jì)算帶來了一定的不便。　　本程序?qū)崿F(xiàn)的目的是將人們習(xí)慣的中綴表達(dá)式轉(zhuǎn)換為計(jì)算機(jī)所能理解的后綴表達(dá)式以方便計(jì)算，最終得出我

6、們所需要的正確的答案。　　2系統(tǒng)分析　　2.1需求分析　　當(dāng)我們需要進(jìn)行一長(zhǎng)串的計(jì)算時(shí)，各種運(yùn)算符夾雜在一起，通過筆算很容易得出結(jié)果。然而計(jì)算機(jī)并沒有人腦那么聰明，它并不懂得先乘除后加減，有括號(hào)要先計(jì)算括號(hào)里面的，它只知道從左到右的進(jìn)行

7、計(jì)算，這就造成了計(jì)算機(jī)計(jì)算的失誤，科學(xué)的計(jì)算是人們非常需要的計(jì)算工具。　　3概要設(shè)計(jì)　　3.1系統(tǒng)總體結(jié)構(gòu)　　整個(gè)系統(tǒng)結(jié)構(gòu)如圖3-1-1所示，結(jié)構(gòu)非常清楚，程序順序執(zhí)行，首先提示用戶輸入需要計(jì)算的表達(dá)式，經(jīng)過轉(zhuǎn)換得到后綴表達(dá)式，最后結(jié)果將

8、數(shù)據(jù)顯示到主屏幕上即可。　　圖3.1.1 系統(tǒng)總體結(jié)構(gòu)圖　　3.2程序算法圖　　本程序所用的數(shù)據(jù)結(jié)構(gòu)類型是棧和隊(duì)列。　　首先提示用戶輸入中綴表達(dá)式，再利用程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，其中數(shù)字入隊(duì)列，算術(shù)運(yùn)算符入棧。</p&

9、gt;　　圖3.2.1 程序算法圖　　4詳細(xì)設(shè)計(jì)　　4.1中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式　　將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式首先需要掃描中綴表達(dá)式，當(dāng)遇到數(shù)字時(shí)，將其入隊(duì)列，當(dāng)遇到運(yùn)算符時(shí)，若是低優(yōu)先級(jí)則直接入棧，若是高優(yōu)先級(jí)則將低優(yōu)先級(jí)運(yùn)算符彈出，并入隊(duì)列，再

10、將此次運(yùn)算符入棧，最終形成后綴表達(dá)式　　圖4.1.1后綴表達(dá)式的轉(zhuǎn)換　　其偽代碼算法如下：　　switch(c){　　case '0' to case '9' :EnQueue(Q,c)</p&g

11、t;　　case '(': Push(S,c)　　case ')' to case'#': t=Pop(S);　　if (t!='(' && t!='#')　　EnQueue(Q,t);</

12、p>　　} while (t!='(' && S->top!=-1);　　case '+' || case '-'|| case '*'|| case '/':　　while (Priority(c)<=Priority

13、(GetTop(S)))//比較優(yōu)先級(jí)　　EnQueue(Q, Pop(S))　　Push(S,c)　　}　　4.1.1求運(yùn)算符優(yōu)先級(jí)函數(shù)　　算術(shù)運(yùn)算符

14、入棧時(shí)必須考慮運(yùn)算符的優(yōu)先級(jí)，才能形成正確的后綴表達(dá)式，當(dāng)讀到運(yùn)算符時(shí)，將棧中所有優(yōu)先級(jí)高于或等于該運(yùn)算符的運(yùn)算符彈出，送至輸出隊(duì)列中，再將當(dāng)前運(yùn)算符入棧；當(dāng)讀入左括號(hào)時(shí)，即入棧；當(dāng)讀到右括號(hào)時(shí)，將靠近棧頂?shù)牡谝粋€(gè)左括號(hào)上面的運(yùn)算符全部依次彈出，送至輸出隊(duì)列中，再刪除棧中的左括號(hào)。　　通過返回值的大小代表優(yōu)先級(jí)的大小，其偽代碼算法如下：　　switch

15、(op){　　case '('||case '#': return 0;break;　　case '-'||case '+':return 1;break;　　case '*'|| case '/':return 2;

16、break;　　}　　4.1.2輸出隊(duì)列　　當(dāng)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式之后，需要輸出后綴表達(dá)式，也就是當(dāng)前隊(duì)列，只需要讓頭指針遍歷輸出數(shù)據(jù)即可。　　其偽代碼如下：</b&

17、gt;　　x=Q->data[Q->front++];　　4.2后綴表達(dá)式的求值　　由于在將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式時(shí)已經(jīng)將運(yùn)算符安排在了合適的位置，在后綴表達(dá)式中不僅不需要括號(hào)，而且還完全免除了運(yùn)算符優(yōu)先規(guī)則，僅需從左到右計(jì)算即可。

18、其偽代碼如下：　　while(!QueueEmpty(Q)){　　ch=DeQueue(Q)　　if (ch>='0' && ch<='9')　　Push(S,ch-'0';

19、)//數(shù)字字符到數(shù)值的轉(zhuǎn)換　　else{　　y=Pop(S),x=Pop(S)　　switch (ch){　　case '+':Push(S,x+y);break;　　case

20、 '-':Push(S,x-y);break;　　case '*':Push(S,x*y);break;　　case '/':Push(S,x/y);break;　　}

21、　　}　　5運(yùn)行與測(cè)試　　5.1 輸入表達(dá)式：　　輸入一個(gè)中綴表達(dá)式：　　5.2 輸出結(jié)果：　　輸出后綴表達(dá)式及其結(jié)果：</p&

22、gt;　　6總結(jié)和心得　　6.1心得與問題　　在本次實(shí)驗(yàn)中，遇到的心得：　　為什么有判空隊(duì)列不需要判空棧？因?yàn)楫?dāng)S->top=-1時(shí)棧變?yōu)榭?，不需要單?dú)寫一個(gè)函數(shù)出來判斷。<p&g

23、t;　　后綴表達(dá)式的求值中，Push(S,ch-'0')中的ch-‘0’是什么意思？因?yàn)檩斎氡磉_(dá)式時(shí)數(shù)字是以字符的形式存儲(chǔ)的，當(dāng)進(jìn)行計(jì)算式需要字符到數(shù)值的轉(zhuǎn)換。　　中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式時(shí)為什么要用Push(S,'#')將#壓入棧底？　　后綴表達(dá)式的求值中，SeqStack vs的作用是什么？為什么不用vs會(huì)出錯(cuò)？&l

24、t;/p>　　調(diào)用后綴表達(dá)式進(jìn)行計(jì)算時(shí)，最終計(jì)算結(jié)果是放在棧中的，但為什么返回棧頂元素時(shí)總是指向空？因?yàn)橹罢{(diào)用了Dequeue(Q)，導(dǎo)致front發(fā)生了改變，相當(dāng)于隊(duì)列被刪除了，所以再調(diào)用時(shí)就為空了，解決方法有多種，比如復(fù)制隊(duì)列，我采取了一個(gè)簡(jiǎn)單的方法，在調(diào)用了CTPostExp(Q)后不忙著輸出后綴表達(dá)式，繼續(xù)調(diào)用CPostExp(Q)，在CPostExp(Q)中使用Dequeue(Q)時(shí)順便就將后綴表

25、達(dá)式輸出，這樣就避免了隊(duì)列第二次調(diào)用時(shí)已經(jīng)被刪除的窘境。　　6.2總結(jié)　　本次試驗(yàn)中內(nèi)存出錯(cuò)的情況比較多，比如在輸出后綴表達(dá)式時(shí)雖然結(jié)果正確，但后面還有很多“燙燙…”，在計(jì)算后綴表達(dá)式時(shí)，返回值總是沒有，等等，但通過不斷地調(diào)試這些問題都得以解決。　　通過本次實(shí)驗(yàn)，加強(qiáng)了對(duì)棧和

26、隊(duì)列的存儲(chǔ)結(jié)構(gòu)的理解，尤其是棧的先進(jìn)后出的結(jié)構(gòu)有了更深的了解。　　參考文獻(xiàn)　　[1]蘇仕華等. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社.2005.05　　[2]嚴(yán)蔚敏，吳偉明. 數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.2007　　[3]譚浩強(qiáng)

27、. C程序設(shè)計(jì)(第三版). 清華大學(xué)出版社. 2005　　附加程序代碼：　　#include<stdio.h>　　#define StackSize 100　　#define QueueSize 100

28、　　typedef char DataType;　　typedef struct　　{　　char data[100];　　int front,rear;　　}SeqQu

29、eue;//定義隊(duì)列類型　　typedef struct　　{　　DataType data[100];　　int top;　　}SeqStack;//棧

30、類型的定義　　//初始化隊(duì)列　　void InitQueue(SeqQueue * Q)　　{　　Q->front=0;　　Q->rear=

31、0;//頭部和尾部分別賦值為0　　}　　//清空隊(duì)列　　int QueueEmpty(SeqQueue * Q)　　{<p&

32、gt;　　return Q->rear==Q->front;//隊(duì)列的頭指針等于尾指針　　}　　//入隊(duì)列　　void EnQueue(SeqQueue * Q,DataType x)

33、;　　{　　if((Q->rear+1) % QueueSize == Q->front)//判斷隊(duì)列是否裝滿　　printf("隊(duì)列溢出");　　else&

34、lt;b>　　{　　Q->data[Q->rear]=x;　　Q->rear=(Q->rear+1)%QueueSize;　　}　　}</p

35、>　　//輸出隊(duì)列　　char DeQueue(SeqQueue * Q)　　{　　char x;　　x=Q->data[Q

36、->front];　　Q->front++;　　return x;　　}　　//初始化棧　　void

37、InitStack(SeqStack * S)　　{　　S->top=-1;　　}　　//入棧　　void P

38、ush(SeqStack * S,DataType x)　　{　　if(S->top==StackSize-1)　　printf("棧溢出");　　else</p&

39、gt;　　{　　S->top=S->top+1;//棧頂指針指向新插入的數(shù)據(jù)　　S->data[S->top]=x;　　}　　}

40、　　//出棧　　DataType Pop(SeqStack * S)　　{　　if(S->top==-1)　　printf(&q

41、uot;空棧");　　else　　returnS->data[S->top--];　　}　　//取棧頂元素&l

42、t;p>　　DataType GetTop(SeqStack * S)　　{　　if(S->top==-1)　　printf("?？?quot;);　　else</p&

43、gt;　　returnS->data[S->top]; 　　}　　//求運(yùn)算符優(yōu)先級(jí)函數(shù)　　int Priority(DataType op)　　{</

44、p>　　switch (op)　　{　　case '(':　　case '#':return 0;break;　　ca

45、se '-':　　case '+':return 1;break;　　case '*':　　case '/':return 2;break;<b

46、>　　}　　}　　//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式　　void CTPostExp(SeqQueue * Q)　　{　　SeqSt

47、ack OS;//運(yùn)算符棧　　char c,t;　　SeqStack * S;　　S=&OS;　　InitStack(S);　　Push(S,&

48、#39;#');//壓入棧底元素#　　do//掃描中綴表達(dá)式　　{　　c=getchar();　　switch(c)　　{&

49、lt;/b>　　case ' ': break;//去除空格符　　case '0':　　case '1':　　case

50、'2':　　case '3':　　case '4':　　case '5':

51、　　case '6':　　case '7':　　case '8':　　case '9':</

52、p>　　EnQueue(Q,c);break;　　case '(':Push(S,c); break;　　case ')':　　case '#':<

53、/p>　　do 　　{　　t=Pop(S);　　if (t!='(' && t!='#')<p

54、>　　EnQueue(Q,t);　　} while (t!='(' && S->top!=-1); break;　　case '+':　　case '-':

55、　　case '*':　　case '/':　　while (Priority(c)<=Priority(GetTop(S)))//比較優(yōu)先級(jí)<b&g

56、t;　　{　　t=Pop(S);　　EnQueue(Q,t);　　}　　Push(S,c);　　break;<

57、/b>　　}　　}while(c!='#');　　}　　//后綴表達(dá)式的求值　　int CPostExp(SeqQueue * Q

58、)　　{　　SeqStack vs,*S;　　char ch;　　int x,y;　　S=&vs;/

59、/有什么用　　InitStack(S);　　while(!QueueEmpty(Q))　　{　　ch=DeQueue(Q);　　printf("%c",ch);//輸出后

60、綴表達(dá)式　　if (ch>='0' && ch<='9')　　Push(S,ch-'0');//數(shù)字字符到數(shù)值的轉(zhuǎn)換　　else　　{<

61、;/b>　　y=Pop(S);　　x=Pop(S);　　switch (ch)　　{　　case '+

62、':Push(S,x+y);break;　　case '-':Push(S,x-y);break;　　case '*':Push(S,x*y);break;　　case '/':Push(S,x/y);break;&

63、lt;b>　　}　　}　　}　　printf("\n");　　printf("最終結(jié)果為：");<p

64、>　　printf("%d\n",GetTop(S));　　return 0;　　}　　//主函數(shù)　　void main()<

65、/p>　　{　　printf("輸入一個(gè)中綴表達(dá)式并以“#”做結(jié)束符：");　　SeqQueue *Q;　　SeqQueue PostQ;//定義隊(duì)列，存放后綴表達(dá)式

66、　　Q=&PostQ;　　InitQueue(Q);//初始化隊(duì)列　　CTPostExp(Q);//調(diào)用函數(shù)將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式　　printf("后綴表達(dá)式為：");　　CPostExp(Q);//調(diào)用函數(shù)計(jì)算出后

眾賞文庫(kù)> 全部分類> 畢業(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)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(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ì)--表達(dá)式求值問題

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載