數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 實(shí)驗(yàn)報(bào)告.docVIP

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 實(shí)驗(yàn)報(bào)告題目：2.3 表達(dá)式求值問(wèn)題1. 問(wèn)題描述表達(dá)式是數(shù)據(jù)運(yùn)算的基本形式。人們的書(shū)寫(xiě)習(xí)慣是中綴式，如：11+22*（7-4）/3。中綴式的計(jì)算按運(yùn)算符的優(yōu)先級(jí)及括號(hào)優(yōu)先的原則，相同級(jí)別從左到右進(jìn)行計(jì)算。表達(dá)式還有后綴式（如：22 7 4 *3/11 +）和前綴式（如：+ 11/*237 4 3）。后綴表達(dá)式和前綴表達(dá)式中沒(méi)有括號(hào)，給計(jì)算帶來(lái)方便。如后綴式計(jì)算時(shí)按運(yùn)算符出現(xiàn)的先后進(jìn)行計(jì)算。本設(shè)計(jì)的主要任務(wù)是進(jìn)行表達(dá)式形式的轉(zhuǎn)換及不同形式的表達(dá)式計(jì)算。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本題中使用順序棧用來(lái)存取運(yùn)算符和運(yùn)算數(shù)，順序棧類(lèi)的定義如下：/順序棧類(lèi)定義template class SqStackprivate:T *base;/棧底指針int top;/棧頂int stacksize;/棧容量public:SqStack(int m);/構(gòu)建函數(shù)SqStack()delete base;top=0;stacksize=0;/析構(gòu)函數(shù)void Push(T x);/入棧T Pop();/出棧T GetTop();/獲取棧頂元素int StackEmpty();/測(cè)?？誺oid ClearStack();/清空棧void StackTop();/返回棧頂指針void StackTranverse();/顯示棧中元素;3. 算法設(shè)計(jì)本題中規(guī)定的功能涉及的算法有：中綴表達(dá)式求值、將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式、將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式、后綴表達(dá)式求值、前綴表達(dá)式求值。（1） 中綴表達(dá)式求值首先定義了兩個(gè)棧，分別用于存取運(yùn)算符和運(yùn)算數(shù)，如下：SqStack OP(20); SqStackOD(20);然后依次讀取表達(dá)式的一個(gè)字符C，如果C是運(yùn)算數(shù)，入運(yùn)算數(shù)棧OP.Push(C)；如果C是運(yùn)算符，把它與棧頂元素的優(yōu)先級(jí)比較：若“”，從運(yùn)算符棧退出一個(gè)運(yùn)算符，從運(yùn)算數(shù)棧里退出兩個(gè)運(yùn)算數(shù)進(jìn)行運(yùn)算，并將結(jié)果入運(yùn)算數(shù)棧。這時(shí)需用到比較運(yùn)算符優(yōu)先級(jí)的函數(shù)：char Precede(char t1,char t2) /算符的優(yōu)先級(jí)比較重復(fù)上述過(guò)程直到把表達(dá)式掃描完，操作數(shù)棧的棧頂元素為計(jì)算結(jié)果。算法如下： case:theta=OP.Pop();/ 退棧并將運(yùn)算結(jié)果入棧 if(theta=(|theta=) cout表達(dá)式有誤!; exit(0); b=OD.Pop(); if(b=0) cout表達(dá)式有誤!endl; exit(0); if(OD.StackEmpty() cout表達(dá)式有誤!endl; exit(0); a=OD.Pop(); OD.Push(Operate(a,theta,b); （2）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式從左向右讀取表達(dá)式，讀到運(yùn)算數(shù)把它輸出；讀到運(yùn)算符f2，把運(yùn)算符棧頂元素的算符優(yōu)先級(jí)f1進(jìn)行比較：若“f1f2”，從運(yùn)算符棧退出一個(gè)運(yùn)算符，從運(yùn)算數(shù)棧里輸出所有比f(wàn)2優(yōu)先級(jí)高的運(yùn)算符，直至棧頂算符優(yōu)先級(jí)小于f2，f2入運(yùn)算符棧。具體算法如下：case:postexpi+=OP.Pop();break; / 運(yùn)算符出棧輸出（3）將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式將中綴式入棧再依次從棧中讀取元素：如果是操作數(shù)把它加入一個(gè)數(shù)組中;如果是運(yùn)算符：若?？栈驐ｍ斒怯依ㄌ?hào)或此元素的優(yōu)先級(jí)大于等于棧頂元素，則此運(yùn)算符入棧；否則，棧頂運(yùn)算符出棧并加入數(shù)組中；若是左括號(hào)，棧中元素逐個(gè)出棧加入數(shù)組中，直到遇到右括號(hào)。最后數(shù)組中的元素序列為中綴式的逆序，將數(shù)組中的元素入棧再出棧就得到前綴式。 部分算法如下：SqStackST(20);SqStackSP(20);SqStackOP(20);while(*exp!=) /利用棧得到中綴式的逆序ST.Push(*exp+);while(!ST.StackEmpty()x=ST.Pop();if(x=0&x|Precede(x,OP.GetTop()=)OP.Push(x);break;elsesj+=OP.Pop();if(x=()while(OP.GetTop()!=)sj+=OP.Pop();OP.Pop();while(!OP.StackEmpty()sj+= ;sj+=OP.Pop();sj=0;while(si!=0)SP.Push(si+);while(!SP.StackEmpty()preexpk+=SP.Pop(); /再次求逆序得到前綴式（4）后綴表達(dá)式求值創(chuàng)建一個(gè)棧，作為運(yùn)算數(shù)棧讀取表達(dá)式： 若是運(yùn)算數(shù)，入運(yùn)算數(shù)棧； 若是運(yùn)算符，從運(yùn)算數(shù)棧退出兩個(gè)運(yùn)算數(shù)，進(jìn)行運(yùn)算，并把運(yùn)算結(jié)果入運(yùn)算數(shù)棧。最后，棧頂元素即為表達(dá)式的值。具體算法如下：SqStack OD(20);c=*postexp+;while(c!=0)if(c=0&c=0&c=9|c=.);zi=0;d=atof(z); / 將字符串?dāng)?shù)組轉(zhuǎn)為浮點(diǎn)型存于dOD.Push(d);if(In(c)/c為運(yùn)算符b=OD.Pop ();/ 退出兩個(gè)運(yùn)算數(shù)運(yùn)算a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;c=*postexp+;v=OD.Pop ();（5）前綴表達(dá)式求值創(chuàng)建棧ST和 棧OD用于存取表達(dá)式逆序和運(yùn)算數(shù)，利用棧得到前綴表達(dá)式的逆序存入棧ST；棧ST出棧，為X: 若X是運(yùn)算數(shù)，則把X存入數(shù)組，直至X不是運(yùn)算數(shù)； 若X是運(yùn)算符，則從運(yùn)算數(shù)棧退出兩個(gè)運(yùn)算數(shù)，進(jìn)行運(yùn)算，并把運(yùn)算結(jié)果入運(yùn)算數(shù)棧。最后，棧頂元素即為表達(dá)式的值。具體算法如下：SqStackST(20); SqStackOD(20);while(*preexp!=0)ST.Push(*preexp+); / 利用棧得到前綴表達(dá)式的逆序while(!ST.StackEmpty()x=ST.Pop();if(x=0&x=0&x=0;p+,k-)sp=zk;d=atof(s);OD.Push(d);if(In(x)a=OD.Pop();b=OD.Pop();OD.Push(Operate(a,x,b);v=OD.Pop();return v;（6）界面設(shè)計(jì)程序包含多個(gè)功能，所以，采用菜單，以方便用戶(hù)進(jìn)行功能選擇。菜單如下：/顯示主菜單cout-* 主 菜 單 *-n;cout 1-創(chuàng)建表達(dá)式n;cout 2-表達(dá)式求值n;cout 3-求后綴表達(dá)式n;cout 4-后綴表達(dá)式求值n;cout 5-求前綴表達(dá)式n;cout 6-前綴表達(dá)式求值n; cout 7-顯示表達(dá)式n;cout 8-退出n;coutEnter choice:;4. 運(yùn)行與測(cè)試（1） 運(yùn)行程序，顯示菜單，如下圖所示：（2） 按“1”創(chuàng)建表達(dá)式。根據(jù)提示，輸入表達(dá)式，如下圖所示： （3） 按“2”表達(dá)式求值。 （4） 按“3”求后綴表達(dá)式。 （5） 按“4”求后綴表達(dá)式的值。 （6） 按“5”求前綴表達(dá)式。 （7） 按“6”求前綴表達(dá)式的值。 （8） 按“7”求顯示中綴表達(dá)式。 （9） 按“1”和“2”，輸入一個(gè)錯(cuò)誤的表達(dá)式，程序會(huì)判斷表達(dá)式錯(cuò)誤。 （10） 按“8”退出。5.調(diào)試記錄及收獲（1）學(xué)會(huì)理解運(yùn)用棧的結(jié)構(gòu)，使用棧的“先進(jìn)后出”的特點(diǎn)；（2）前綴和后綴的變換借助于棧實(shí)現(xiàn)，理解前綴、中綴、后綴的不同之處；（3）調(diào)試程序要細(xì)致耐心，當(dāng)程序的功能較多時(shí)，要仔細(xì)測(cè)試程序的每一個(gè)功能，發(fā)現(xiàn)錯(cuò)誤要及時(shí)查錯(cuò)修改，不斷完善程序。7.源程序#includeusing namespace std;/順序棧類(lèi)定義template class SqStackprivate:T *base;/棧底指針int top;/棧頂int stacksize;/棧容量public:SqStack(int m);/構(gòu)建函數(shù)SqStack()delete base;top=0;stacksize=0;/析構(gòu)函數(shù)void Push(T x);/入棧T Pop();/出棧T GetTop();/獲取棧頂元素int StackEmpty();/測(cè)棧空void ClearStack();/清空棧void StackTop();/返回棧頂指針void StackTranverse();/顯示棧中元素;/順序棧類(lèi)實(shí)現(xiàn)template SqStack:SqStack(int m) /創(chuàng)建一個(gè)空棧base=new Tm;if(base=NULL) cout棧創(chuàng)建失敗，退出!endl;exit(1);stacksize=m;top=-1;template void SqStack:Push(T x) /入棧操作if(top=stacksize-1) throw 棧滿(mǎn)，無(wú)法入棧;top+;basetop=x;/couttop：topendl;template T SqStack:Pop() /出棧操作T x;if(top=-1) throw ?？眨荒艹鰲?x=basetop-;/couttop：topendl;return x;template /獲取棧頂元素T SqStack:GetTop()if(top=-1) throw ?？眨瑮ｍ敓o(wú)元素;/couttop：topendl;return basetop;template int SqStack:StackEmpty() /測(cè)?？読f(top=-1) return 1;elsereturn 0;template void SqStack:ClearStack() /清空棧top=-1;template void SqStack:StackTop() /返回棧頂指針cout棧頂top= top;template void SqStack:StackTranverse() /輸出棧中元素int i=top; while(i=0) coutbasei-t; coutendl; char pause;char Precede(char t1,char t2) /算符的優(yōu)先級(jí)比較 char f; switch(t2) case +: case -:if(t1=(|t1=) f=; break; case *: case /:if(t1=*|t1=/|t1=) f=; else f=; break; case (:if(t1=) cout表達(dá)式有誤!endl; exit(0); else f=; break; case ):switch(t1) case (:f=; break; case =:cout表達(dá)式有誤!; break; case =:switch(t1) case =:f=; break; case (:cout表達(dá)式有誤!; return f; int In(char c) / 判斷c是否為運(yùn)算符 switch(c) case+: case-: case*: case/: case(: case): case=:return 1; default:return 0; double Operate(double a,char theta,double b) /進(jìn)行一次運(yùn)算 double c; switch(theta) case+:c=a+b;break; case-:c=a-b;break; case*:c=a*b;break; case/:c=a/b;break; return c; double Val_Exp(char *exp) /中綴表達(dá)式求值 SqStack OP(20);/建立容量為20的運(yùn)算符棧 SqStack OD(20);/建立容量為20的運(yùn)算數(shù)棧 char theta; double a,b,d; char c,x; / 存放由鍵盤(pán)接收的字符 char z6; / 存放符點(diǎn)數(shù)字符串 int i; OP.Push(=); / =是表達(dá)式結(jié)束標(biāo)志 c=*exp+; /每次從表達(dá)式中讀取一個(gè)字符 x=OP.GetTop(); while(c!=|x!=) if(In(c) / 是7種運(yùn)算符之一 switch(Precede(x,c) case:theta=OP.Pop();/ 退棧并將運(yùn)算結(jié)果入棧 if(theta=(|theta=) cout表達(dá)式有誤!; exit(0); b=OD.Pop(); if(b=0) cout表達(dá)式有誤!endl; exit(0); if(OD.StackEmpty() cout表達(dá)式有誤!=0&c=0&c=9|c=.); zi=0; d=atof(z); / 將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d OD.Push(d); else / c是非法字符 cout表達(dá)式有誤!endl; exit(0); x=OP.GetTop(); d=OD.GetTop(); return d; void CreatePreExp(char * exp,char * &preexp) /由中綴式求前綴式 char x;char s20;int j=0,i=0,k=0;SqStackST(20);SqStackSP(20);SqStackOP(20);while(*exp!=) /利用棧得到中綴式的逆序ST.Push(*exp+);while(!ST.StackEmpty()x=ST.Pop();if(x=0&x|Precede(x,OP.GetTop()=)OP.Push(x);break;elsesj+=OP.Pop();if(x=()while(OP.GetTop()!=)sj+=OP.Pop();OP.Pop();while(!OP.StackEmpty()sj+= ;sj+=OP.Pop();sj=0;while(si!=0)SP.Push(si+);while(!SP.StackEmpty()preexpk+=SP.Pop(); /再次求逆序得到前綴式preexpk=0;cout前綴表達(dá)式為:preexpendl;void CreatePostExp(char * exp,char * &postexp) /由中綴式求后綴式char c,x;int i=0;SqStack OP(20);OP.Push(=); / =是表達(dá)式結(jié)束標(biāo)志c=*exp+;while(c)if(c=0&c=9)|c=.)postexpi+=c;c=*exp+;if(In(c) / 是7種運(yùn)算符之一postexpi+= ; x=OP.GetTop();switch(Precede(x,c)case:postexpi+=OP.Pop(); / 運(yùn)算符出棧輸出 break;postexpi=0;/whilecout后綴表達(dá)式為:postexpendl;double Val_PostExp(char *postexp) /后綴表達(dá)式求值int i;char z6;double v=0,d=0,a,b;char c;SqStack OD(20);c=*postexp+;while(c!=0)if(c=0&c=0&c=9|c=.);zi=0;d=atof(z); / 將字符串?dāng)?shù)組轉(zhuǎn)為浮點(diǎn)型存于dOD.Push(d);if(In(c)/c為運(yùn)算符b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;c=*postexp+;v=OD.Pop ();return v;double Val_PreExp(char * preexp) /前綴表達(dá)式求值int k,p=0;char z6,s6;char x;double v,d=0,a,b;SqStackST(20); SqStackOD(20);while(*preexp!=0)ST.Push(*preexp+); / 利用棧得到前綴表達(dá)式的逆序while(!ST.StackEmpty()x=ST.Pop();if(x=0&x=0&x=0;p+,k-)sp=zk;d=atof(s);OD.Push(d);if(In(x)a=OD.Pop();b=OD.Pop();OD.Push(Operate(a,x,b);v=OD.Pop();return v; /主函數(shù)void main() char exp20;/=(2.2+5)+4*(5-3.1)=;char *postexp,*preexp;postexp=new char20; preexp=new char20;*postexp=0;*preexp=0;double v1,v2;system(cls);/執(zhí)行系統(tǒng)命令cls，清屏int choice; do/顯示主菜單cout-* 主 菜 單 *-n;cout 1-創(chuàng)建表達(dá)式n;cout 2-表達(dá)式求值n;cout 3-求后綴表達(dá)式n;cout 4-后綴表達(dá)式求值n;cout 5-求前綴表達(dá)式n;cout 6-前綴表達(dá)式求值n; cout 7-顯示表達(dá)式n;cou