算術(shù)表達式求值課程設(shè)計

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

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

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

文檔簡介

1、　　學(xué)年論文（設(shè)計）　?。ū究疲?lt;/b>　　學(xué) 院 　　專業(yè) 　　年級

2、 　　姓名 　　論文（設(shè)計）題目算術(shù)表達式求值 　　指導(dǎo)教師職稱

3、　成績 　　2012 年月日　　目錄　　概述……………………………………………………………………………………………3　　設(shè)計目的…………

4、……………………………………………………………………….3　　三、設(shè)計功能分析…………………………………………………………………………3　　四、概要設(shè)計說明…………………………………………………………………………4　　五、詳細信息說明…………………………………………………………………………5

5、　　六、流程圖………………………………………………………………………………………10　　七、程序代碼…………………………………………………………………………………10　　八、調(diào)試及運行結(jié)論……………………………………………………………………17　　九、總結(jié)…………………………………………………

6、………………………………………19　　十、參考文獻…………………………………………………………………………………19　　一、概述　　數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學(xué)科的核心課程，而且已成為其它理工專業(yè)熱門選修課。而且它與計算機其他課程都有密切聯(lián)系，

7、具有獨特的承上啟下的重要位置。擁有《數(shù)據(jù)結(jié)構(gòu)》這門課程的知識準備，對于學(xué)習(xí)計算機專業(yè)的其他課程，如操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、軟件工程的都是有益的。　　二、設(shè)計目的　　1、了解算術(shù)表達式的不同表現(xiàn)形式及相應(yīng)算法實現(xiàn)的不同。　　2、深入了解棧的特性，并在實際問題背景下靈活運用。&

8、lt;/p>　　3、掌握字符串解釋為表達式的意義和數(shù)字轉(zhuǎn)化。　　三、設(shè)計功能分析　　算術(shù)表達式求值程序?qū)崿F(xiàn)以下功能：　　構(gòu)造一個空棧S,初始條件：棧S已存在　　用P返回S的棧頂元素&

9、lt;p>　　插入元素ch為新的棧頂元素　　刪除S的棧頂元素　　判斷字符是否是運算符，運算符即返回1　　判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的　　輸入表達式

10、;　　返回表達式的最終結(jié)果。　　四：概要設(shè)計說明　　在計算機中算術(shù)表達式由常量、變量、運算符和括號組成。由于不同的運算符優(yōu)先級不同，而且還要考慮括號；因此算術(shù)表達式不可能完全嚴格的從左到右執(zhí)行。因此在設(shè)計程序時，要借助棧的功能。　　算法輸入：一個算術(shù)表達式，由常量、變量、運算

11、符、括號組成（以字符串的形式輸入）。操作符為+、-、*、/，用#表示結(jié)束。　　算法輸出：表達式運算結(jié)果。　　算法要點：設(shè)置運算符棧和運算數(shù)棧輔助分析算術(shù)符優(yōu)先關(guān)系。在讀入表達式的字符序列的同時，完成運算符和運算數(shù)的識別處理，以及相應(yīng)運算。　　基本操作：

12、　　InitStack(&S)　　操作結(jié)果：構(gòu)造一個空棧S。　　GetTop(S)　　初始條件：棧S已存在.　　操作結(jié)果：用P返回S的棧頂元素。　　Push(*S,c

13、h)　　初始條件：棧S已存在。　　操作結(jié)果：插入元素ch為新的棧頂元素。　　Pop(&S)　　初始條件：棧S已存在。　　操作結(jié)果：刪除S的棧頂元素。<p&

14、gt;　　In(ch)　　操作結(jié)果：判斷字符是否是運算符，運算符即返回1。　　Precede(c1, c2) 　　初始條件：c1,c2為運算符。　　操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。

15、　　Operate(a,op,b)　　初始條件：a,b為整數(shù)，op為運算符。　　操作結(jié)果：a與b進行運算，op為運算符，返回其值。　　num(n)　　操作結(jié)果：返回操作數(shù)的長度。　　EvalE

16、xpr()　　初始條件：輸入表達式合法。　　操作結(jié)果：返回表達式的最終結(jié)果。　　}ADT Stack　　五、詳細設(shè)計說明　　1、數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計　　因

17、為表達式是由操作符，運算符和界限符組成的。如果只用一個char類型棧，不能滿足2位以上的整數(shù)，所以還要定義一個int類型的棧用來寄存操作數(shù)。　　/* 定義字符類型棧 */　　typedef struct{　　int stacksize;　　char *base;</

18、p>　　char *top;　　}Stack1　　/*定義整形棧*/　　typedef struct{　　int stacksize;<p

19、>　　int *base;　　int *top;　　}Stack2　　2、主要算法　?、?、Precede(char c1,char c2) 判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。</p

20、>　　算符間的優(yōu)先關(guān)系如下：　　表一　　算法偽代碼如下：　　char Precede(char c1,char c2) 　　{ &

21、lt;/p>　　static char array[49]={　　'>', '>', '<', '<', '<', '>', '>', 　　'>', &

22、#39;>', '<', '<', '<', '>', '>', 　　'>', '>', '>', '>', '<', '>', '&

23、gt;', 　　'>', '>', '>', '>', '<', '>', '>', 　　'<', '<', '<', '

24、;<', '<', '=', '!', 　　'>', '>', '>', '>', '!', '>', '>', 　　'<&#

25、39;, '<', '<', '<', '<', '!', '='}; //用一維數(shù)組存儲49種情況　　switch(c1) 　　{ 　　/* i為下面ar

26、ray的橫標 */ 　　case '+' : i=0;break; 　　case '-' : i=1;break; 　　case '*' : i=2;break; 　　case '/' : i=3;break

27、; 　　case '(' : i=4;break; 　　case ')' : i=5;break; 　　case '#' : i=6;break; 　　} <

28、;p>　　switch(c2) 　　{ 　　/* j為下面array的縱標 */ 　　case '+' : j=0;break; 　　case '-' : j=1;break;

29、;　　case '*' : j=2;break; 　　case '/' : j=3;break; 　　case '(' : j=4;break; 　　case ')' : j=5;break; <p

30、>　　case '#' : j=6;break; 　　}　　return (array[7*i+j]); /* 返回運算符array[7*i+j]為對應(yīng)的c1,c2優(yōu)先關(guān)系*/ 　　}<

31、p>　?、?、利用該算法對算術(shù)表達式3*(7-2)求值操作過程如下：　　表二　　算法偽代碼如下：　　int EvalExpr()//主要操作函數(shù) 　　{ c = *ptr++; </p&

32、gt;　　while(c!='#'||GetTop(OPTR)!='#') 　　{　　if(!In(c)) //不是運算符即進棧　　{ if(!In(*(ptr-1))) ptr=ptr-1;&l

33、t;p>　　m=atoi(ptr);//取字符串前面的數(shù)字段　　n=num(m); 　　Push2(&OPND,m); 　　ptr=ptr+n;　　c=*ptr++;<b&

34、gt;　　} 　　else 　　switch(Precede(GetTop(OPTR),c)) 　　{ 　　case '<': //棧頂元素優(yōu)先權(quán)底<

35、;/p>　　Push(&OPTR,c); 　　c = *ptr++; 　　break; 　　case '=': //脫括號并接收下一字符　　x=Pop(&OPTR); <

36、;/p>　　c = *ptr++; 　　break; 　　case '>'://退棧并將運算結(jié)果入棧 　　theta=Pop(&OPTR); 　　b=Pop2(&OPN

37、D); a=Pop2(&OPND); 　　Push2(&OPND,Operate(a,theta,b));　　break;　　} 　　}<

38、;/p>　　六、流程圖如下：　　七、程序代碼　　#include <stdio.h>　　#include <stdlib.h>　　#includ

39、e <process.h>　　#define STACK_INIT_SIZE 100 　　#define status int　　#define SElemType float　　#define ERROR 0　　#d

40、efine OK 1　　typedef struct{　　SElemType *base;　　SElemType *top;　　int stacksize;　　}SqStack;</p&

41、gt;　　void InitStack(SqStack &S)//初始化順序棧　　{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));　　if(!S.base) exit(1);　　S.top=S.base;

42、　　S.stacksize=STACK_INIT_SIZE;　　}　　status GetTop(SqStack S, SElemType &e)//取棧頂元素的值　　{ if(S.base==S.top) return E

43、RROR;　　else 　　e=*(S.top-1);　　return OK;　　}　　status Push(SqStack &S, SElem

44、Type e)//入棧操作　　{ if(S.top-S.base==S.stacksize)　　{ S.base=(SElemType *)realloc(S.base,(S.stacksize+10)*sizeof(SElemType));　　if(!S.base) return ERROR;</p&g

45、t;　　S.top=S.base+S.stacksize;}　　else *S.top++=e;　　return OK;　　}　　status Pop(SqStack &S, SElemType &

46、;e)//出棧操作　　{ if(S.base==S.top) return ERROR;　　else 　　e=*(--S.top);　　return OK;　　}</

47、b>　　status Empty(SqStack S)//判斷棧是否為空的操作　　{ if(S.base==S.top) return true;　　else return false;　　}<p&

48、gt;　　//此前全部為順序棧的基本操作　　char Precede(char c1 ,char c2)//判定運算符的優(yōu)先級　　{ 　　char r;　　switch(c2)<

49、/p>　　{　　case'+': 　　case'-':　　if(c1=='('||c1=='#') r='<

50、9;;　　else r='>';　　break;　　case'*': 　　case'/':<p

51、>　　if(c1=='*'||c1=='/'||c1==')') r='>';　　else r='<';　　break;　　case'(

52、':　　if(c1==')') { printf("括號匹配錯誤!\n"); exit(-1);}　　else r='<';　　break;<p&g

53、t;　　case')':　　if(c1=='(') r='=';　　else if(c1=='#') { printf("error!沒有左括號\n"); exit (-1);}

54、　　else r='>';　　break;　　case'#':　　switch(c1)　　{

55、　　case'#': r='=';　　break;　　case'(': {printf("error!沒有右括號!\n"); exit(-1);}<b&g

56、t;　　default:　　r='>';　　}//switch　　break;　　}//switc

57、h　　return r;　　}//Precede　　bool In(char d)//判斷c是否為七種運算符之一　　{

58、;　　switch(d)　　{　　case'+':　　case'-':　　case

59、9;*':　　case'/':　　case'(':　　case')':<b&

60、gt;　　case'#':　　return true;　　default:　　return false;　　}//switch<p

61、>　　}　　SElemType Operate( SElemType a, SElemType theta, SElemType b )//Operate為進行二元運算的a theta b的函數(shù)　　{　　char n=char(t

62、heta);//此處把double型強制轉(zhuǎn)換成int型，雖然會造成精度缺失，但本身theta是一個符號，也算是整型　　switch(n) //轉(zhuǎn)換后相當于和符號匹配ACSII碼　　{　　case'+':</p&

63、gt;　　return a+b;　　case'-':　　return a-b;　　case'*':　　return a*b;

64、;　　default:　　if(b!=0)　　return a/b;　　else　　{</p

65、>　　printf("error!除數(shù)不能為零\n");　　exit(-1);　　}　　}//switch&l

66、t;b>　　}　　SElemType EvaluateExpression()　　{ //算符表達式的優(yōu)先算法。設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧　　SqStack OPTR,OPND;　　char c;

67、　　char Data[11];//定義此數(shù)組為了存放整數(shù)或小數(shù)　　SElemType a,b,d,e;　　InitStack(OPTR);//構(gòu)造一個運算符棧　　InitStack(OPND);//構(gòu)造一個運算數(shù)棧<p&

68、gt;　　Push(OPTR,'#');//將#壓入棧底　　c=getchar();　　GetTop(OPTR,e);　　while(c!='#'||e!='#')//棧頂不是#號且輸入不是#號　　{<

69、;/b>　　if(In(c))//是符號則進棧　　{　　switch(Precede(e,c))　　{　　case'<':

70、 //棧頂元素優(yōu)先級低　　Push(OPTR,c);　　c=getchar();　　break;　　case'=': //脫括號并接受下一字符　　Pop(OPTR,e);

71、　　c=getchar();　　break;　　case'>': //退棧并將運算結(jié)果入棧　　Pop(OPTR,e);　　Pop(OPND,b);

72、;　　Pop(OPND,a);　　Push(OPND,Operate(a,e,b));　　break;　　}//switch　　}<

73、;/p>　　else if(c>='0'&&c<='9'||c=='.')　　{　　int i=0;　　while(c>=

74、9;0'&&c<='9'||c=='.')　　{　　Data[i]=c;　　i++;　　c=getchar();

75、　　}　　Data[i]='\0';//數(shù)字沒有存滿,輸入字符串結(jié)束符　　d=atof(Data);//此處是把數(shù)組里的數(shù)字，實際上是按字符串；轉(zhuǎn)換為double類型，然后把浮點型數(shù)字入棧　　Push(OPND,d);//atof函數(shù)的形參

76、是指針類型，故用數(shù)組名　　}　　else　　{　　printf("error!輸入錯誤!\n");

77、;　　exit(-1);　　}　　GetTop(OPTR,e);　　}//while　　GetTop(OPND,e);

78、;　　return e;　　}//EvaluateExpression　　void main()　　{　　SElemType result;　　prin

79、tf("請輸入表達式，以#號結(jié)束\n");　　result=EvaluateExpression();　　printf("結(jié)果為:%f:\n",result);　　}　　八、調(diào)

80、試及運行結(jié)果　　1、程序調(diào)試　　1）使用Microsoft visual c++ 編輯軟件進行源程序的編寫。　　2）使用Microsoft visual c++軟件進行編譯，步驟：按F7。 　　3）使用Micros

81、oft visual c++運行程序并調(diào)試，步驟：（1）按F7；（2）按Ctrl+F5。　　2、運行及程序界面　　1）編輯程序界面　　圖一　　2）執(zhí)行程序及

82、運行后界面　　圖二　　-------------------Configuration:0-Win32Debug--------------------　　Linking...　　exe - 0 error(s), 0 warning

83、(s)　　圖三　　3）運行過程　　1、輸入正確的表達式后　　2、更改表達式　　九：總結(jié)</b

84、>　　通過此次的課程設(shè)計，更加清楚了算術(shù)表達式求值的過程，同時也更加深刻的理解了棧的相關(guān)知識。更加深刻的知道程序設(shè)計者要有較強的思維和動手能力和更加了解編程思想和編程技巧，其次，設(shè)計界面與函數(shù)功能要劃分好，程序要一定的注釋以便于理解，程序要經(jīng)得起測試，要做出有價值的程序。所以在以后的學(xué)習(xí)中要更加注重對自己動手能力的練習(xí)。　　在課程設(shè)計的過程中，也有

85、模糊的知識，通過宿舍同學(xué)的幫助和討論，也都一點點的解決了。在這里謝謝他們的幫助。同時也要感謝辛勤的數(shù)據(jù)結(jié)構(gòu)老師的悉心教導(dǎo)和耐心講解。謝謝你們！　　總之：此次的課程設(shè)計我有很大的收獲！　　十、參考文獻　　1、《數(shù)據(jù)結(jié)構(gòu)（c語言版）》嚴蔚敏吳偉民清華大學(xué)出版社</p&

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

溫馨提示

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

算術(shù)表達式求值課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

算術(shù)表達式求值課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載