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

學號： 學年論文（設(shè)計）（本科）學 院 專 業(yè) 年 級 姓 名 論文（設(shè)計）題目 算術(shù)表達式求值 指導教師 職稱 成 績 2012 年 月 日目錄一、 概述3二、 設(shè)計目的.3三、設(shè)計功能分析3四、概要設(shè)計說明4五、詳細信息說明5六、流程圖10七、程序代碼10八、調(diào)試及運行結(jié)論17九、總結(jié)19十、參考文獻19一、概述數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學科的核心課程，而且已成為其它理工專業(yè)熱門選修課。而且它與計算機其他課程都有密切聯(lián)系，具有獨特的承上啟下的重要位置。擁有數(shù)據(jù)結(jié)構(gòu)這門課程的知識準備，對于學習計算機專業(yè)的其他課程，如操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、軟件工程的都是有益的。二、設(shè)計目的 1、了解算術(shù)表達式的不同表現(xiàn)形式及相應算法實現(xiàn)的不同。2、深入了解棧的特性，并在實際問題背景下靈活運用。3、掌握字符串解釋為表達式的意義和數(shù)字轉(zhuǎn)化。三、設(shè)計功能分析 算術(shù)表達式求值程序?qū)崿F(xiàn)以下功能：(1) 構(gòu)造一個空棧S,初始條件：棧S已存在(2) 用P返回S的棧頂元素(3) 插入元素ch為新的棧頂元素(4) 刪除S的棧頂元素(5) 判斷字符是否是運算符，運算符即返回1(6) 判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的(7) 輸入表達式(8) 返回表達式的最終結(jié)果。四：概要設(shè)計說明 在計算機中算術(shù)表達式由常量、變量、運算符和括號組成。由于不同的運算符優(yōu)先級不同，而且還要考慮括號；因此算術(shù)表達式不可能完全嚴格的從左到右執(zhí)行。因此在設(shè)計程序時，要借助棧的功能。算法輸入：一個算術(shù)表達式，由常量、變量、運算符、括號組成（以字符串的形式輸入）。操作符為+、-、*、/，用#表示結(jié)束。算法輸出：表達式運算結(jié)果。算法要點：設(shè)置運算符棧和運算數(shù)棧輔助分析算術(shù)符優(yōu)先關(guān)系。在讀入表達式的字符序列的同時，完成運算符和運算數(shù)的識別處理，以及相應運算。基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧S。 GetTop(S) 初始條件：棧S已存在. 操作結(jié)果：用P返回S的棧頂元素。 Push(*S,ch) 初始條件：棧S已存在。 操作結(jié)果：插入元素ch為新的棧頂元素。 Pop(&S) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運算符，運算符即返回1。 Precede(c1, c2) 初始條件：c1,c2為運算符。操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運算符。操作結(jié)果：a與b進行運算，op為運算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達式合法。操作結(jié)果：返回表達式的最終結(jié)果。ADT Stack五、詳細設(shè)計說明1、數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計 因為表達式是由操作符，運算符和界限符組成的。如果只用一個char類型棧，不能滿足2位以上的整數(shù)，所以還要定義一個int類型的棧用來寄存操作數(shù)。/* 定義字符類型棧 */typedef structint stacksize;char *base;char *top;Stack1/*定義整形棧*/typedef structint stacksize;int *base;int *top;Stack22、主要算法、Precede(char c1,char c2) 判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。 算符間的優(yōu)先關(guān)系如下：+- *、（）#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一維數(shù)組存儲49種情況switch(c1) /* i為下面array的橫標 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j為下面array的縱標 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回運算符array7*i+j為對應的c1,c2優(yōu)先關(guān)系*/ 、利用該算法對算術(shù)表達式3*(7-2)求值操作過程如下：步驟OPTR棧OPND棧輸入字符主要操作1#3*（72）#Push(OPND,3)2#3*（72）#Push(OPTR,*)3# *3（72）#Push(OPNR,()4# *（372）#Push(OPND,7)5# *（3 72）#Push(OPNR,-)6# *（3 72）#Push(OPND,2)7# *（3 7 2）#Operate(7,-,2)8# *（3 5）#Pop(OPTR)9# *3 5#Operate(3,*,5)10#15#Return GetTop2(OPND) 表二算法偽代碼如下：int EvalExpr()/主要操作函數(shù) c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) /不是運算符即進棧 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的數(shù)字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case :/退棧并將運算結(jié)果入棧 theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; 六、流程圖如下：c!=#|GetTop(OPTR)!=#!In（c）case :操作數(shù)棧頭兩個數(shù)進行運算進操作符棧c=*ptr+;Return GetTop2(OPND)char c=表達式首字符七、程序代碼#include #include #include #define STACK_INIT_SIZE 100 #define status int#define SElemType float#define ERROR 0#define OK 1typedef structSElemType *base;SElemType *top;int stacksize;SqStack;void InitStack(SqStack &S)/初始化順序棧 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(1); S.top=S.base; S.stacksize=STACK_INIT_SIZE;status GetTop(SqStack S, SElemType &e)/取棧頂元素的值 if(S.base=S.top) return ERROR; else e=*(S.top-1); return OK;status Push(SqStack &S, SElemType e)/入棧操作 if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+10)*sizeof(SElemType); if(!S.base) return ERROR; S.top=S.base+S.stacksize; else *S.top+=e; return OK;status Pop(SqStack &S, SElemType &e)/出棧操作 if(S.base=S.top) return ERROR; else e=*(-S.top); return OK;status Empty(SqStack S)/判斷棧是否為空的操作 if(S.base=S.top) return true; else return false;/此前全部為順序棧的基本操作char Precede(char c1 ,char c2)/判定運算符的優(yōu)先級 char r; switch(c2) case+: case-: if(c1=(|c1=#) r=; break; case*: case/: if(c1=*|c1=/|c1=) r=; else r=; break; case(: if(c1=) printf(括號匹配錯誤!n); exit(-1); else r=; break; case#: switch(c1) case#: r=; break; case(: printf(error!沒有右括號!n); exit(-1); default: r=; /switch break; /switch return r;/Precedebool In(char d)/判斷c是否為七種運算符之一 switch(d) case+: case-: case*: case/: case(: case): case#: return true; default: return false; /switchSElemType Operate( SElemType a, SElemType theta, SElemType b )/Operate為進行二元運算的a theta b的函數(shù) char n=char(theta);/此處把double型強制轉(zhuǎn)換成int型，雖然會造成精度缺失，但本身theta是一個符號，也算是整型 switch(n) /轉(zhuǎn)換后相當于和符號匹配ACSII碼 case+: return a+b; case-: return a-b; case*: return a*b; default: if(b!=0) return a/b; else printf(error!除數(shù)不能為零n); exit(-1); /switchSElemType EvaluateExpression() /算符表達式的優(yōu)先算法。設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧 SqStack OPTR,OPND; char c; char Data11;/定義此數(shù)組為了存放整數(shù)或小數(shù) SElemType a,b,d,e; InitStack(OPTR);/構(gòu)造一個運算符棧 InitStack(OPND);/構(gòu)造一個運算數(shù)棧 Push(OPTR,#);/將#壓入棧底 c=getchar(); GetTop(OPTR,e); while(c!=#|e!=#)/棧頂不是#號且輸入不是#號 if(In(c)/是符號則進棧 switch(Precede(e,c) case: /退棧并將運算結(jié)果入棧 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; /switch else if(c=0&c=0&c=9|c=.) Datai=c; i+; c=getchar(); Datai=0;/數(shù)字沒有存滿,輸入字符串結(jié)束符 d=atof(Data);/此處是把數(shù)組里的數(shù)字，實際上是按字符串；轉(zhuǎn)換為double類型，然后把浮點型數(shù)字入棧 Push(OPND,d);/atof函數(shù)的形參是指針類型，故用數(shù)組名 else printf(error!輸入錯誤!n); exit(-1); GetTop(OPTR,e); /while GetTop(OPND,e); return e;/EvaluateExpressionvoid main() SElemType result; printf(請輸入表達式，以#號結(jié)束n); result=EvaluateExpression(); printf(結(jié)果為:%f:n,result);八、調(diào)試及運行結(jié)果 1、程序調(diào)試 1）使用Microsoft visual c+ 編輯軟件進行源程序的編寫。 2）使用Microsoft visual c+軟件進行編譯，步驟：按F7。 3）使用Microsoft visual c+運行程序并調(diào)試，步驟：（1） 按F7；（2）按Ctrl+F5。 2、運行及程序界面 1）編輯程序界面圖一 2）執(zhí)行程序及運行后界面圖二 -Configuration:0-Win32Debug-Linking.0. exe - 0 error(s), 0 warning(s)圖三3）運行過程 1、輸入正確的表達式后2、更改表達式九：總結(jié)通過此次的課程設(shè)計，更加清楚了算術(shù)表達式求值的過程，同時也更加深刻的理解了棧的相關(guān)知識。更加深刻的知道程序設(shè)