《數據結構》課程設計PAGEPAGE10中南民族大學計算機科學學院專業：軟件工程學號：201421092032姓名：李凱表達式求值一目的利用《數據結構》課程的相關知識完成一個具有一定難度的綜合設計題目，利用C/C++語言進行程序設計，并規范地完成課程設計報告。通過課程設計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現實復雜問題的分析建模和解決方法（包括問題描述、系統分析、設計建模、代碼實現、結果分析等）；提高利用計算機分析解決綜合性實際問題的基本能力。設計一個程序，演示以字符序列的形式輸入不含變量的實數表達式求值的計算結果二需求分析設計一個程序，演示以字符序列的形式輸入不含變量的實數表達式求值的計算結果。對于這個程序我們從輸入，輸出，和功能三方面來分析。程序輸入：從鍵盤上輸入表達式，一個算術表達式，由常量、運算符和括號組成（以字符串形式輸入，不含變量）。為了簡化，操作數只能為浮點數，操作符為“+”、“-”、“*”、“/”、“（”、“）”，用“#“表示結束。程序輸出：表達式運算結果，運算符棧、運算數棧、輸入字符和主要操作變化過程，如運算符棧、運算數棧的出入記錄，字符出入棧的過程，打印出完整的過程。3.功能要求及說明：從鍵盤上輸入表達式。分析該表達式是否合法（包含分母不能為零的情況）：（1）是數字，則判斷該數字的合法性。（2）是規定的運算符，則根據規則進行處理。在處理過程中，將計算該表達式的值。（3）若是其它字符，則返回錯誤信息。若上述處理過程中沒有發現錯誤，則認為該表達式合法，并打印處理結果。三概要設計1.數據結構的選擇：任何一個表達式都是由操作符，運算符和界限符組成的。我們分別用順序棧來寄存表達式的操作數和運算符。棧是限定于緊僅在表尾進行插入或刪除操作的線性表。為了實現算符優先算法，可以使用兩個工作棧。一個稱做SqStack1，用以寄存運算符；另一個稱做SqStack2，用以寄存操作數或運算結果。首先置操作數棧為空棧，表達式起始符“＃”作為運算符棧的棧底元素，然后依次讀入表達式的每個字符，若是操作數則進入SqStack2棧，若是運算符則和SqStack1棧的棧頂運算符比較優先權后做相應操作，直至整個表達式求值完畢。兩個棧：typedefstruct//運算符棧{ char*base; char*top; intstacksize;}SqStack1;typedefstruct//運算數棧{ float*base; float*top; intstacksize;}SqStack2;2.相關功能函數：voidInitStack1(SqStack1&S1);//聲明運算符棧建立函數voidInitStack2(SqStack2&S2);//聲明運算數棧建立函數主要的確定如何入棧的函數：voidevaluate(SqStack1&S1,SqStack2&S2);voidPush1(SqStack1&S1,chare);//聲明入棧函數voidPush2(SqStack2&S2,floate);//聲明入棧函數charGetTop1(SqStack1&S1);//聲明取棧頂元素函數floatGetTop2(SqStack2&S2);//聲明取棧頂元素函數charPop1(SqStack1&S1);//聲明出棧函數floatPop2(SqStack2&S2);//聲明出棧函數charCompare(charm,charn);//聲明比較函數通過這個函數我們來實現運算符運算的先后順序判斷運算符優先權，返回優先權高的算符間的優先關系如下：θ1θ2+-*/（）#+>><<<>>->><<<>>*>>>><>>/>>>><>>（<<<<<=）>>>>>>#<<<<<=最后的計算函數：floatOperate(floata,charrheta,floatb);//聲明運算函數為了使運算的過程更加直觀的反應出來，我們再繪制一個表格，繪制表格的相關函數如下：voidDispStack1(SqStack1&S1);//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2&S2);//從棧底到棧頂依次輸出各元素3.函數模塊之間的調用關系：四詳細設計首先本程序定義兩個順序棧：運算符棧（SqStack1）和運算數棧（SqStack2）；typedefstruct//運算符棧{ char*base; char*top; intstacksize;}SqStack1;typedefstruct//運算數棧{ float*base; float*top; intstacksize;}SqStack2;然后是主要功能函數的詳細設計：/*運算符棧函數*/voidInitStack1(SqStack1&S1)//構造一個空棧S1{ S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S1.base)cout<<"存儲分配失敗！";//存儲分配失敗 S1.top=S1.base; S1.stacksize=STACK_INIT_SIZE;}確定如何入棧的函數實現如下：voidPush1(SqStack1&S1,chare)//入棧{ if(S1.top-S1.base>=S1.stacksize)//如果棧滿，追加存儲空間 { S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<"存儲分配失敗！"; else { S1.top=S1.base+S1.stacksize; S1.stacksize=S1.stacksize+STACKINCREMENT; } } *S1.top=e;S1.top=S1.top+1;//將元素壓入棧中，指針上移}實現提取棧頂元素的函數實現：charGetTop1(SqStack1&S1)//取棧頂元素{ chare; if(S1.top==S1.base)cout<<"\n\t\t\t運算符棧已空!\n"; elsee=*(S1.top-1); returne;}以及設計的一個在結果顯示過程的棧中清單打印函數voidDispStack1(SqStack1&S1)//從棧底到棧頂依次輸出各元素{ chare,*p; if(S1.top==S1.base)cout<<""; else { p=S1.base; while(p<S1.top) { e=*p; p++; cout<<e; } }}核心的算法確定如何入棧函數的實現如下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; Push1(S1,'#');//將'#'入棧，作為低級運算符 cout<<"●請輸入不含變量的表達式（以#結束!）：\n"; cin>>ch; c=ch[0]; cout<<"\n●對表達式求值的操作過程如下：" <<"\n________________________________________________________________________________\n" <<"步驟\t運算符棧S1\t運算數棧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=='#')) {//輸入的字符如果不是運算符號，則繼續輸入直到輸入的是運算符為止，將非運算符轉換成浮點數 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;//非運算型數據計數器清零 switch(Compare(GetTop1(S1),c))//比較運算符的優先級 { case'<'://棧頂元素優先級低，則入棧且繼續輸入 Push1(S1,c); cout<<"\t\tPush1(S1,"<<c<<")"; c=ch[s++]; break; case'='://棧頂元素優先級相等，脫括號并接收下一字符 Pop1(S1); cout<<"\t\tPop1(S1)"; c=ch[s++]; break; case'>'://棧頂元素優先級高，則退棧并將運算結果入棧 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";}運算符的優先級比較函數實現如下charCompare(charm,charn)//運算符的優先級比較{ if(n=='+'||n=='-')//輸入符號為"+"、"-" { if(m=='('||m=='#')return'<';//棧頂元素為"("、"#",此時棧頂符號優先級低，返回"<" elsereturn'>';//否則，棧頂符號優先級高,返回">" } elseif(n=='*'||n=='/')//輸入的符號為"*"、"/" { if(m==')'||m=='*'||m=='/')return'>';//棧頂元素為")"、"*"、"/",此時棧頂符號優先級高，返回">" elsereturn'<';//否則，棧頂符號優先級低,返回"<" } elseif(n=='(')return'<';//輸入的符號為"(",則直接返回"<" elseif(n==')')//輸入的符號為")" { if(m=='(')return'=';//棧頂元素為"(",此時優先級同，返回"=" elsereturn'>';//否則，棧頂符號優先級高,返回">" } else//輸入符號為其他 { if(m=='#')return'=';//棧頂元素為"#",此時優先級同，返回"=" elsereturn'>';//否則，棧頂符號優先級高,返回">" }}以及最后的計算函數floatOperate(floata,chartheta,floatb)//運算函數{ floattmp=0; if(theta=='+')tmp=a+b;//從運算符棧取出的符號為"+"，則運算數棧的兩元素相加，并返回 elseif(theta=='-')tmp=a-b;//從運算符棧取出的符號為"-"，則運算數棧的兩元素相減，并返回 elseif(theta=='*')tmp=a*b;//從運算符棧取出的符號為"*"，則運算數棧的兩元素相乘，并返回 elseif(theta=='/') //從運算符棧取出的符號為"/"，則運算數棧的兩元素相除，并返回 { if(b==0)cout<<"\n表達式出錯!除數不能為0!\n"; elsetmp=a/b; } returntmp;}五調試分析1．結構分析:棧中的數據節點是通過數組來存儲的。因為在C語言中數組是用下標從零開始的，因此我們在調用他們的數據是要特別注意。指針變量的值要么為空(NULL)，不指向任何結點；要么其值為非空，即它的值是一個結點的存儲地址。注意，當P為空值時，則它不指向任何結點，此時不能通過P來訪問結點，否則會引起程序錯誤。如果輸入的數字不符合題目要求，則會產生錯誤結果。2．算法的時空分析：時間和空間性能分析：時間上，對于含n個字符的表達式，無論是對其進行合法性檢測還是對其進行入棧出棧操作n次，因此其時間復雜度為O(n)。空間上，由于是用數組來存儲輸入的表達式，用棧來存儲運算中的數據和運算符，而棧的本質也用到的數組，數組在定義時必須確定其大小。在不知表達式長度的情況下確定數組的長度確非易事，此時極易造成空間的浪費，因此空間性能不是很好。六測試結果1、實數混合運算以上調試結果是正確的。能夠實現各個符號優先級先后順序的運算，根據符號優先級（、）、+、-、*、/，如此順序進行運算，實現了基本表達式運算的功能。但是需要注意的是，這個程序功能并不是那么完善，具體能實現的功能如下：由于中英文字符的不同，加上本程序沒有對中文字符加以處理，當從鍵盤輸入的表達式中包含中文括號時程序無法正確的計算出結果，而是會報錯！同樣表達式中只能包含英文的運算符，輸入中文的運算符時會報錯！同樣，從鍵盤輸入的表達式必須要運算符匹配，例如括號要匹配，要成對出現，由于本程序沒有加以處理，遇到這種情況，程序會報錯！七用戶使用說明使用環境：VisualC++6.0.操作要求：程序運行后,