數(shù)據(jù)結構課程設計：算術表達式

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

函數(shù)模塊之間的調(diào)用關系：棧的建立及初始化模塊O運算符運算數(shù)出棧模塊判斷字符類型模塊運算符優(yōu)先級比較模塊判斷輸入是否結束模塊主程序模塊輸入結束輸出結果運算符進棧模塊運算數(shù)進棧模塊運算模塊棧的建立及初始化模塊O運算符運算數(shù)出棧模塊判斷字符類型模塊運算符優(yōu)先級比較模塊判斷輸入是否結束模塊主程序模塊輸入結束輸出結果運算符進棧模塊運算數(shù)進棧模塊運算模塊詳細設計首先本程序定義兩個順序棧：運算符棧（SqStackl）和運算數(shù)棧（SqStack2）；typedefstruct//運算符棧{char*base;char*top;intstacksize;}SqStack1;typedefstruct//運算數(shù)棧{float*base;float*top;intstacksize;}SqStack2;然后是主要功能函數(shù)的詳細設計：/*運算符棧函數(shù)*/voidInitStackl(SqStackl&S1)//構造一個空棧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ù)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<<〃?請輸入不含變量的表達式(以#結束！)：\n";cin>>ch;c=ch[0];cout<<〃\n?對表達式求值的操作過程如下：〃<<〃\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ù)輸入直到輸入的是運算符為止，將非運算符轉換成浮點數(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)先級高，則退棧并將運算結果入棧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)//顯示表達式最終結果cout<<"\n?表達式的結果為："<<GetTop2(S2)<<endl;elsecout<<"\n表達式出錯！\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表達式出錯!除數(shù)不能為0!\n";elsetmp=a/b;}returntmp;}調(diào)試分析1．結構分析:棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。因為在C語言中數(shù)組是用下標從零開始的，因此我們在調(diào)用他們的數(shù)據(jù)是要特別注意。指針變量的值要么為空(NULL)，不指向任何結點；要么其值為非空，即它的值是一個結點的存儲地址。注意，當P為空值時，則它不指向任何結點，此時不能通過P來訪問結點，否則會引起程序錯誤。如果輸入的數(shù)字不符合題目要求，則會產(chǎn)生錯誤結果。2．算法的時空分析：時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為O(n)?？臻g上，由于是用數(shù)組來存儲輸入的表達式，用棧來存儲運算中的數(shù)據(jù)和運算符，而棧的本質也用到的數(shù)組，數(shù)組在定義時必須確定其大小。在不知表達式長度的情況下確定數(shù)組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。測試結果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ù)棧艾輸入字符主要操作運算符棧關請輸人不合變量的表達式〔以結束!〕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ù)棧艾輸入字符主要操作運算符棧關請輸人不合變量的表達式〔以結束!〕1+2+3-O對表達式求值的操作過程如下：E3'C:\IJsers\kai\Documents\C-表達式&?6,0\算術表達式,exe"OX果束繼結結鍵的鍵意式意任達任按表按請?5"C:\Users\kai\Documents\C-Free\Prqjects\算術表達式\vc6,0\算術表達式.exe"- 0 X晴輸人不含變量的表達式（以#結束?。?1.4+1.0*1.5-1.6#對表達式求值的操作過程如下：步驟 運算符棧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.訓Opera4,+,1.5.)8#2.91.5-1.肘Pushl(SI,-)9 卜2.9.5-1.訓F'ush2(S2,1.6)102.91.6-1.肘OperatmU.E1.6j11#1.3#RETURN(GETTOP(S2))表達式的結果為：1.3按任意鍵結束！請按任意鍵繼續(xù)???■■5 9HRlHOggl囪玨?宇中2336以上調(diào)試結果是正確的。能夠實現(xiàn)各個符號優(yōu)先級先后順序的運算，根據(jù)符號優(yōu)先級（、）、+、-、*、/，如此順序進行運算，實現(xiàn)了基本表達式運算的功能。但是需要注意的是，這個程序功能并不是那么完善，具體能實現(xiàn)的功能如下：由于中英文字符的不同，加上本程序沒有對中文字符加以處理，當從鍵盤輸入的表達式中包含中文括號時程序無法正確的計算出結果，而是會報錯！同樣表達式中只能包含英文的運算符，輸入中文的運算符時會報錯！同樣，從鍵盤輸入的表達式必須要運算符匹配，例如括號要匹配，要成對出現(xiàn)，由于本程序沒有加以處理，遇到這種情況，程序會報錯！用戶使用說明1?使用