算術表達式求值課程設計

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

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

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

文檔簡介

1、　　學年論文（設計）　　（本科）　　學院 　　專業(yè) 　　年級

2、 　　姓名 　　論文（設計）題目算術表達式求值 　　指導教師職稱

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

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

5、　　六、流程圖………………………………………………………………………………………10　　七、程序代碼…………………………………………………………………………………10　　八、調試及運行結論……………………………………………………………………17　　九、總結…………………………………………………

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

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

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

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

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

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

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

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

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

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

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

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、主要算法　?、佟recede(char c1,char c2) 判斷運算符優(yōu)先權，返回優(yōu)先權高的。</p

20、>　　算符間的優(yōu)先關系如下：　　表一　　算法偽代碼如下：　　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]為對應的c1,c2優(yōu)先關系*/ 　　}<

31、p>　?、?、利用該算法對算術表達式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)先權底<

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

36、;/p>　　c = *ptr++; 　　break; 　　case '>'://退棧并將運算結果入棧 　　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型強制轉換成int型，雖然會造成精度缺失，但本身theta是一個符號，也算是整型　　switch(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)先算法。設OPTR和OPND分別為運算符棧和運算數(shù)棧　　SqStack OPTR,OPND;　　char c;

67、　　char Data[11];//定義此數(shù)組為了存放整數(shù)或小數(shù)　　SElemType a,b,d,e;　　InitStack(OPTR);//構造一個運算符棧　　InitStack(OPND);//構造一個運算數(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'>': //退棧并將運算結果入棧　　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ù)字沒有存滿,輸入字符串結束符　　d=atof(Data);//此處是把數(shù)組里的數(shù)字，實際上是按字符串；轉換為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("請輸入表達式，以#號結束\n");　　result=EvaluateExpression();　　printf("結果為:%f:\n",result);　　}　　八、調

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

81、oft visual c++運行程序并調試，步驟：（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、更改表達式　　九：總結</b

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

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

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

溫馨提示

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

算術表達式求值課程設計

文檔簡介

溫馨提示

最新文檔

評論

算術表達式求值課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載