數(shù)據(jù)結構課程設計報告-表達式求值

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：12 大小：88.00KB 人氣指數(shù)：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數(shù)據(jù)結構》課程設計　　表達式求值　　班級： 　　學號： 　　姓名： </p&

2、gt;　　指導老師： 　　表達式求值　　問題描述　　要求對包含加、減、乘、除、括號運算符的任意整型表達式進行求解。

3、設計思路　　這個程序的關鍵是對數(shù)字與運算符的判斷和運算符優(yōu)先級的判斷，以及出棧的運算。建立兩個棧，分別存儲數(shù)字與運算符，棧1存運算符，棧2存數(shù)字。依次讀取表達式的字符串，先判斷是數(shù)字還是運算符，如果是數(shù)字不能馬上壓入棧2，因為可能是大于10的數(shù)字，應該繼續(xù)循環(huán)，如果還是數(shù)字，則利用計算保存數(shù)值，直到指到運算符時停止，將計算后的數(shù)字壓入棧2。壓入運算符之前先將要壓入的與棧頂?shù)倪\

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

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

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

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

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

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

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

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

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

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; /*定義棧，兩個不同的存儲類型*/　　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ōu)先級*/　　{　　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) /*表達式求值函數(shù)，infix為表達式字符串*/　　{　　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,'#'); /*先將‘#’壓入算符棧，便于判斷結束*/　　w=*infix; /*讀表達式字符*/　　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); /*兩括號相遇，銷毀，讀下一個字符*/　　}　　else if((

56、charGetTop_SeqStack(S1,&c),c)=='('||　　priority((charGetTop_SeqStack(S1,&c),c))<priority(w))/*比較運算符*/　　{　　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; /*彈出運

60、算符的同時進行運算*/　　}　　Push_SeqStack(S2,num); /*將運算結果重新壓入棧2*/　　}　　} /*while((charGetTop_SeqStack(S1

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

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

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

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

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

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

溫馨提示

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

數(shù)據(jù)結構課程設計報告-表達式求值

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計報告-表達式求值

文檔簡介

溫馨提示

最新文檔

評論

免費下載