數(shù)據(jù)結(jié)構(gòu)課程設(shè)計：算術(shù)表達(dá)式

表達(dá)式求值目的利用《數(shù)據(jù)結(jié)構(gòu)》課程的相關(guān)知識完成一個具有一定難度的綜合設(shè)計題目，利用C/C++語言進(jìn)行程序設(shè)計，并規(guī)范地完成課程設(shè)計報告。通過課程設(shè)計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現(xiàn)實復(fù)雜問題的分析建模和解決方法（包括問題描述、系統(tǒng)分析、設(shè)計建模、代碼實現(xiàn)、結(jié)果分析等）；提高利用計算機(jī)分析解決綜合性實際問題的基本能力。設(shè)計一個程序，演示以字符序列的形式輸入不含變量的實數(shù)表達(dá)式求值的計算結(jié)果需求分析設(shè)計一個程序，演示以字符序列的形式輸入不含變量的實數(shù)表達(dá)式求值的計算結(jié)果。對于這個程序我們從輸入，輸出，和功能三方面來分析。程序輸入：從鍵盤上輸入表達(dá)式，一個算術(shù)表達(dá)式，由常量、運算符和括號組成（以字符串形式輸入，不含變量）。為了簡化，操作數(shù)只能為浮點數(shù)，操作符為“+”、“-”、“*”、“/”、“（”、“）”，用“#“表示結(jié)束。程序輸出：表達(dá)式運算結(jié)果，運算符棧、運算數(shù)棧、輸入字符和主要操作變化過程，如運算符棧、運算數(shù)棧的出入記錄，字符出入棧的過程，打印出完整的過程。功能要求及說明：從鍵盤上輸入表達(dá)式。分析該表達(dá)式是否合法（包含分母不能為零的情況）：（1） 是數(shù)字，則判斷該數(shù)字的合法性。（2） 是規(guī)定的運算符，則根據(jù)規(guī)則進(jìn)行處理。在處理過程中，將計算該表達(dá)式的值。（3） 若是其它字符，則返回錯誤信息。若上述處理過程中沒有發(fā)現(xiàn)錯誤，則認(rèn)為該表達(dá)式合法，并打印處理結(jié)果。概要設(shè)計數(shù)據(jù)結(jié)構(gòu)的選擇：任何一個表達(dá)式都是由操作符，運算符和界限符組成的。我們分別用順序棧來寄存表達(dá)式的操作數(shù)和運算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。為了實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧。一個稱做SqStackl，用以寄存運算符；另一個稱做SqStack2，用以寄存操作數(shù)或運算結(jié)果。首先置操作數(shù)棧為空棧，表達(dá)式起始符“＃”作為運算符棧的棧底元素，然后依次讀入表達(dá)式的每個字符，若是操作數(shù)則進(jìn)入SqStack2棧，若是運算符則和SqStack1棧的棧頂運算符比較優(yōu)先權(quán)后做相應(yīng)操作，直至整個表達(dá)式求值完畢。兩個棧：typedefstruct//運算符棧{char*base;char*top;intstacksize;}SqStack1;typedefstruct//運算數(shù)棧{float*base;float*top;intstacksize;}SqStack2;相關(guān)功能函數(shù)：voidInitStackl(SqStackl&SI);//聲明運算符棧建立函數(shù)voidInitStack2(SqStack2&S2);//聲明運算數(shù)棧建立函數(shù)主要的確定如何入棧的函數(shù)：voidevaluate(SqStackl&S1,SqStack2&S2);voidPush1(SqStackl&S1,chare);//聲明入棧函數(shù)

voidPush2(SqStack2&S2,floate);//聲明入棧函數(shù)

charGetTop1(SqStackl&Sl);//聲明取棧頂元素函數(shù)

floatGetTop2(SqStack2&S2);//聲明取棧頂元素函數(shù)

charPop1(SqStackl&Sl);//聲明出棧函數(shù)

floatPop2(SqStack2&S2);//聲明出棧函數(shù)

charCompare(charm,charn);//聲明比較函數(shù)通過這個函數(shù)我們來實現(xiàn)運算符運算的先后順序判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的算符間的優(yōu)先關(guān)系如下：+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=最后的計算函數(shù)：floatOperate(floata,charrheta,floatb);//聲明運算函數(shù)為了使運算的過程更加直觀的反應(yīng)出來，我們再繪制一個表格，繪制表格的相關(guān)函數(shù)如下：voidDispStackl(SqStackl&Sl);//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2&S2);//從棧底到棧頂依次輸出各元素

函數(shù)模塊之間的調(diào)用關(guān)系：棧的建立及初始化模塊O運算符運算數(shù)出棧模塊判斷字符類型模塊運算符優(yōu)先級比較模塊判斷輸入是否結(jié)束模塊主程序模塊輸入結(jié)束輸出結(jié)果運算符進(jìn)棧模塊運算數(shù)進(jìn)棧模塊運算模塊棧的建立及初始化模塊O運算符運算數(shù)出棧模塊判斷字符類型模塊運算符優(yōu)先級比較模塊判斷輸入是否結(jié)束模塊主程序模塊輸入結(jié)束輸出結(jié)果運算符進(jìn)棧模塊運算數(shù)進(jìn)棧模塊運算模塊詳細(xì)設(shè)計首先本程序定義兩個順序棧：運算符棧（SqStackl）和運算數(shù)棧（SqStack2）；typedefstruct//運算符棧{char*base;char*top;intstacksize;}SqStack1;typedefstruct//運算數(shù)棧{float*base;float*top;intstacksize;}SqStack2;然后是主要功能函數(shù)的詳細(xì)設(shè)計：/*運算符棧函數(shù)*/voidInitStackl(SqStackl&S1)//構(gòu)造一個空棧SI{S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!Sl.base)cout<<"存儲分配失敗！";//存儲分配失敗S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}確定如何入棧的函數(shù)實現(xiàn)如下：voidPushl(SqStackl&S1,chare)//入棧{if(S1.top-S1.base>二S1.stacksize)//如果棧滿，追加存儲空間{Sl.base=(char*)realloc(Sl.base,(Sl.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存儲分配失?。?;else{Sl.top=Sl.base+Sl.stacksize;Sl.stacksize=Sl.stacksize+STACKINCREMENT;}}*S1.top=e;S1.top二S1.top+1;//將元素壓入棧中，指針上移}實現(xiàn)提取棧頂元素的函數(shù)實現(xiàn)：charGetTop1(SqStack1&S1)//取棧頂元素{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t運算符棧已空!\n";elsee=*(Sl.top-l);returne;}以及設(shè)計的一個在結(jié)果顯示過程的棧中清單打印函數(shù)voidDispStack1(SqStack1&S1)//從棧底到棧頂依次輸出各元素{chare,*p;if(Sl.top==Sl.base)cout<<"";else{p=Sl.base;while(p<Sl.top){e=*p;p++;cout<<e;}}}核心的算法確定如何入棧函數(shù)的實現(xiàn)如下voidevaluate(SqStack1&S1,SqStack2&S2){charc;floatt,e;intn=0,i=1,j=0,k=0,l=0;charch[STACK_INIT_SIZE];ints=1;intflag=0,flag2=0;floatp1,p2;charch1;Pushl(Sl,'#');//將'#'入棧，作為低級運算符cout<<〃?請輸入不含變量的表達(dá)式(以#結(jié)束！)：\n";cin>>ch;c=ch[0];cout<<〃\n?對表達(dá)式求值的操作過程如下：〃<<〃\n \n〃<<"步驟\t運算符棧S1\t運算數(shù)棧S2\t輸入字符\t\t主要操作〃;while(c！='#'||GetTop1(S1)！='#'){cout<<〃\n \n〃;cout<<i++<<〃\t〃;DispStack1(S1);cout<<〃\t\t〃;DispStack2(S2);cout<<〃\t\t〃;if(flag==1){k--;flag=0;}if(flag2){k+=flag2;flag2=0;}for(l=0;l<k;l++)cout<<'';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!='#'&&flag!=1){k++;flag=0;}as:if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')){//輸入的字符如果不是運算符號，則繼續(xù)輸入直到輸入的是運算符為止，將非運算符轉(zhuǎn)換成浮點數(shù)if(!(c=='.')&&n>=0){e=float(c-48);n++;if(n==1)t=e;elseif(n>1)t=t*10+e;c=ch[s++];}if(n==-1){e=float(c-48);t=t+e/10;c=ch[s++];}if(c=='.'){n=-1;c=ch[s++];}if((c>='0'&&c<='9')||c=='.'){flag2++;gotoas;}if(c<'0'||c>'9'){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//輸入的是運算符{n=0;//非運算型數(shù)據(jù)計數(shù)器清零switch(Compare(GetTopl(Sl),c))//比較運算符的優(yōu)先級{case'<'://棧頂元素優(yōu)先級低，則入棧且繼續(xù)輸入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case'='://棧頂元素優(yōu)先級相等，脫括號并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case'>'://棧頂元素優(yōu)先級高，則退棧并將運算結(jié)果入棧p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n \n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++)cout<<'';cout<<"#"<<"\t\t"<<"RETURN(GETTOP(S2))";cout<<"\n \n";if(S2.top-1二二S2.base)//顯示表達(dá)式最終結(jié)果cout<<"\n?表達(dá)式的結(jié)果為："<<GetTop2(S2)<<endl;elsecout<<"\n表達(dá)式出錯！\n";}運算符的優(yōu)先級比較函數(shù)實現(xiàn)如下charCompare(charm,charn)//運算符的優(yōu)先級比較{if(n=='+'||n=='-')//輸入符號為〃+〃、〃-〃{if(m=='('||m=='#')return'<';//棧頂元素為〃(〃、〃#〃,此時棧頂符號優(yōu)先級低，返回〃<〃elsereturn'>';//否則，棧頂符號優(yōu)先級高,返回〃>〃}elseif(n=='*'||n=='/')//輸入的符號為〃*〃、‘7〃{if(m==')'||m=='*'||m=='/')return'>';//棧頂元素為〃)〃、〃*〃、〃/〃,此時棧頂符號優(yōu)先級高，返回〃>〃elsereturn'<';//否則，棧頂符號優(yōu)先級低,返回〃<〃}elseif(n=='(')return'〈’；//輸入的符號為〃(〃，則直接返回〃〈“elseif(n==')')//輸入的符號為〃)〃{if(m=='(')return'二’；//棧頂元素為〃(〃,此時優(yōu)先級同，返回〃二〃elsereturn'>';//否則，棧頂符號優(yōu)先級高,返回〃>〃}else //輸入符號為其他{if(m=='#')return'二’；//棧頂元素為〃#〃,此時優(yōu)先級同，返回〃二〃elsereturn'>';//否則，棧頂符號優(yōu)先級高,返回〃>〃}}以及最后的計算函數(shù)floatOperate(floata,chartheta,floatb)//運算函數(shù){floattmp=0；if (theta二二'+')tmp二a+b;//從運算符棧取出的符號為〃+〃，則運算數(shù)棧的兩元素相加，并返回elseif(theta二二'-')tmp二a-b;//從運算符棧取出的符號為〃-〃，則運算數(shù)棧的兩元素相減，并返回elseif(theta二二'*')tmp二a*b;//從運算符棧取出的符號為〃*〃，則運算數(shù)棧的兩元素相乘，并返回elseif(theta=='/') //從運算符棧取出的符號為〃/〃，則運算數(shù)棧的兩元素相除，并返回{if(b==0)cout<<〃\n表達(dá)式出錯!除數(shù)不能為0!\n";elsetmp=a/b;}returntmp;}調(diào)試分析1．結(jié)構(gòu)分析:棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。因為在C語言中數(shù)組是用下標(biāo)從零開始的，因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)，不指向任何結(jié)點；要么其值為非空，即它的值是一個結(jié)點的存儲地址。注意，當(dāng)P為空值時，則它不指向任何結(jié)點，此時不能通過P來訪問結(jié)點，否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯誤結(jié)果。2．算法的時空分析：時間和空間性能分析：時間上，對于含n個字符的表達(dá)式，無論是對其進(jìn)行合法性檢測還是對其進(jìn)行入棧出棧操作n次，因此其時間復(fù)雜度為O(n)。空間上，由于是用數(shù)組來存儲輸入的表達(dá)式，用棧來存儲運算中的數(shù)據(jù)和運算符，而棧的本質(zhì)也用到的數(shù)組，數(shù)組在定義時必須確定其大小。在不知表達(dá)式長度的情況下確定數(shù)組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。測試結(jié)果1、實數(shù)混合運算

RETURN(GETTOP(S2))#3Opera(.7, 4.)74Push2(S2,4)74#PushlCSl,-)3社7Operate(.1,+,6jF#+16Operate(.2,:+:,3.)123Push2(S2,3)123-4#Pushl(：Sl/+\)4U+12#3-4#Push2(S2,2)3#+12*3-4#PushlCSl,+)社1+2*3-4#Push2(S2,1)11+2+3-4#運算數(shù)棧艾輸入字符主要操作運算符棧關(guān)請輸人不合變量的表達(dá)式〔以結(jié)束!〕RETURN(GETTOP(S2))#3Opera(.7, 4.)74Push2(S2,4)74#PushlCSl,-)3社7Operate(.1,+,6jF#+16Operate(.2,:+:,3.)123Push2(S2,3)123-4#Pushl(：Sl/+\)4U+12#3-4#Push2(S2,2)3#+12*3-4#PushlCSl,+)社1+2*3-4#Push2(S2,1)11+2+3-4#運算數(shù)棧艾輸入字符主要操作運算符棧關(guān)請輸人不合變量的表達(dá)式〔以結(jié)束!〕1+2+3-O對表達(dá)式求值的操作過程如下：E3'C:\IJsers\kai\Documents\C-表達(dá)式&?6,0\算術(shù)表達(dá)式,exe"OX果束繼結(jié)結(jié)鍵的鍵意式意任達(dá)任按表按請?5"C:\Users\kai\Documents\C-Free\Prqjects\算術(shù)表達(dá)式\vc6,0\算術(shù)表達(dá)式.exe"- 0 X晴輸人不含變量的表達(dá)式（以#結(jié)束！）:1.4+1.0*1.5-1.6#對表達(dá)式求值的操作過程如下：步驟 運算符棧E1運算數(shù)棧史輸入字符主要操作1#1.4+1.0*1.5-1.舗Push2(S2,1.4)2#1.44+1.0*1.5-1.肘Pushl(SI,+)3 #+1.4+1.0*1.5-1.舗Push2(S2,1)4 tt+1.41.0*1.5-1.Pushl(SI,*)5 #+*1.410*1.5-1.舗F'ush2(S2,1.5)6#+*1.411.51.5-1.肘Operate」丄*,1.5.)7 #+1.41.51.5-1.訓(xùn)Opera4,+,1.5.)8#2.91.5-1.肘Pushl(SI,-)9 卜2.9.5-1.訓(xùn)F'ush2(S2,1.6)102.91.6-1.肘OperatmU.E1.6j11#1.3#RETURN(GETTOP(S2))表達(dá)式的結(jié)果為：1.3按任意鍵結(jié)束！請按任意鍵繼續(xù)???■■5 9HRlHOggl囪玨?宇中2336以上調(diào)試結(jié)果是正確的。能夠?qū)崿F(xiàn)各個符號優(yōu)先級先后順序的運算，根據(jù)符號優(yōu)先級（、）、+、-、*、/，如此順序進(jìn)行運算，實現(xiàn)了基本表達(dá)式運算的功能。但是需要注意的是，這個程序功能并不是那么完善，具體能實現(xiàn)的功能如下：由于中英文字符的不同，加上本程序沒有對中文字符加以處理，當(dāng)從鍵盤輸入的表達(dá)式中包含中文括號時程序無法正確的計算出結(jié)果，而是會報錯！同樣表達(dá)式中只能包含英文的運算符，輸入中文的運算符時會報錯！同樣，從鍵盤輸入的表達(dá)式必須要運算符匹配，例如括號要匹配，要成對出現(xiàn)，由于本程序沒有加以處理，遇到這種情況，程序會報錯！用戶使用說明1?使用