實驗二 棧的應(yīng)用-算術(shù)表達式的計算

-.z.大學(xué)城市學(xué)院實驗報告課程名稱數(shù)據(jù)構(gòu)造與算法實驗工程名稱實驗二棧的應(yīng)用---算術(shù)表達式的計算實驗成績指導(dǎo)教師〔簽名〕日期實驗?zāi)康暮鸵?．進一步掌握棧的根本操作的實現(xiàn)。2．掌握棧在算術(shù)表達式的計算方面的應(yīng)用。二.實驗容1.編寫程序利用棧將中綴表達式轉(zhuǎn)換成后綴表達式，即從鍵盤輸入任一個中綴表達式〔字符串形式〕，轉(zhuǎn)換成后綴表達式后，將后綴表達式輸出。假設(shè)：中綴表達式包含圓括號()及雙目運算符+、-、*、/、^〔乘方〕。要求：把棧的根本操作的實現(xiàn)函數(shù)存放在頭文件stack1.h中〔棧元素的類型為char〕，在主文件test6_2.cpp中包含將中綴表達式S1轉(zhuǎn)換成后綴表達式S2的轉(zhuǎn)換函數(shù)voidChange(char*S1,char*S2)及主函數(shù)，在主函數(shù)中進展輸入輸出及轉(zhuǎn)換函數(shù)的調(diào)用。2.選做：編寫利用棧對后綴表達式進展求值的函數(shù)doublepute(char*str)，以計算從前述程序得到的后綴表達式的值。要求：把棧的根本操作的實現(xiàn)函數(shù)存放在頭文件stack2.h中〔棧元素的類型為double〕，在主文件test6_2.cpp中添加后綴表達式求值函數(shù)，并在主函數(shù)中增加調(diào)用求值函數(shù)及輸出結(jié)果值的語句。3.填寫實驗報告，實驗報告文件取名為report2.doc。4.上傳實驗報告文件report2.doc與源程序文件stack1.h、stack2.h〔假設(shè)有〕及test6_2.cpp到Ftp效勞器上你自己的文件夾下。函數(shù)的功能說明及算法思路〔算法思路見源程序的注釋局部〕//棧的順序存儲構(gòu)造定義structStack{ ElemType*stack; inttop; intMa*Size;};//初始化棧S為空voidInitStack(Stack&S)//元素item進棧，即插入到棧頂voidPush(Stack&S,ElemTypeitem)//刪除棧頂元素并返回ElemTypePop(Stack&S)//讀取棧頂元素的值ElemTypePeek(Stack&S)//判斷S是否為空，假設(shè)是則返回true，否則返回falseboolEmptyStack(Stack&S)//去除棧S中的所有元素，釋放動態(tài)存儲空間voidClearStack(Stack&S)//將中綴算術(shù)表達式轉(zhuǎn)換為后綴算術(shù)表達式voidChange(char*S1,char*&S2)//返回運算符op所對應(yīng)的優(yōu)先級數(shù)值intPrecedence(charop)//計算由str所指字符串的后綴表達式的值doublepute(char*str)四.實驗結(jié)果與分析五.心得體會【附錄----源程序】test6_2.cpp*include<iostream.h>*include<stdlib.h>*include<math.h>*include"stack1.h"*include"stack2.h"voidmain(){ char*[30],y[30]; doubler; while(1){ cout<<"請輸入一個中綴算術(shù)表達式："; cin.getline(*,sizeof(*)); Change(*,y); cout<<"對應(yīng)的后綴算術(shù)表達式為："; cout<<y<<endl; r=pute(y); cout<<"后綴算術(shù)表達式值為："<<r<<endl<<endl; }}stack1.htypedefcharElemType1;structStack1{ ElemType1*stack; inttop; intMa*Size;};voidInitStack(Stack1&S){ S.Ma*Size=10; S.stack=newElemType1[S.Ma*Size]; if(!S.stack){ cerr<<"動態(tài)儲存分配失敗"<<endl; e*it(1); } S.top=-1;}voidPush(Stack1&S,ElemType1item){ if(S.top==S.Ma*Size-1){ intk=sizeof(ElemType1); S.stack=(ElemType1*)realloc(S.stack,2*S.Ma*Size*k); S.Ma*Size=2*S.Ma*Size; } S.top++; S.stack[S.top]=item;}ElemType1Pop(Stack1&S){ if(S.top==-1){ cerr<<"Stackisempty!"<<endl; e*it(1); } S.top--; returnS.stack[S.top+1];}ElemType1Peek(Stack1&S){ if(S.top==-1){ cerr<<"Stackisempty!"<<endl; e*it(1); } returnS.stack[S.top];}boolEmptyStack(Stack1&S){ returnS.top==-1;}voidClearStack(Stack1&S){ if(S.stack){ delete[]S.stack; S.stack=0; } S.top=-1; S.Ma*Size=0;}//返回運算符op所對應(yīng)的優(yōu)先級數(shù)值intPrecedence(charop){ switch(op){ case'+': case'-': return1; case'*': case'/': return2; case'^': return3; case'(': case'': default: return0; }}//將中綴算術(shù)表達式轉(zhuǎn)換為后綴算術(shù)表達式voidChange(char*S1,char*S2){ Stack1R; InitStack(R); Push(R,''); inti=0,j=0; charch=S1[i]; while(ch!='\0'){ //對于空格字符不做任何處理，順序讀取下一個字符 if(ch=='') ch=S1[++i]; //對于左括號，直接進棧 elseif(ch=='('){ Push(R,ch); ch=S1[++i]; } //對于右括號，使括號的仍停留在棧中的運算符依次出棧并寫入S2 elseif(ch==')'){ while(Peek(R)!='(') S2[j++]=Pop(R); Pop(R);//刪除棧頂?shù)淖罄ㄌ? ch=S1[++i]; } //對于運算符，使暫存于棧頂且不低于ch優(yōu)先級的運算符依次出棧并寫入S2 elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'){ charw=Peek(R); while(Precedence(w)>=Precedence(ch)){ S2[j++]=w; Pop(R); w=Peek(R); } Push(R,ch);//把ch運算符寫入棧中 ch=S1[++i]; } else{ if((ch<'0'||ch>'9')&&ch!='.'){ cout<<"中綴表達式表示錯誤！"<<endl; e*it(1); } while((ch>='0'&&ch<='9')||ch=='.'){ S2[j++]=ch; ch=S1[++i]; } S2[j++]=''; } } //把暫存在棧中的運算符依次退棧并寫入到S2中 ch=Pop(R); while(ch!=''){ if(ch=='('){ cerr<<"e*pressionerror!"<<endl; e*it(1); } else{ S2[j++]=ch; ch=Pop(R); } } S2[j++]='\0';}stack2.htypedefdoubleElemType2;structStack2{ ElemType2*stack; inttop; intMa*Size;};voidInitStack(Stack2&S){ S.Ma*Size=10; S.stack=newElemType2[S.Ma*Size]; if(!S.stack){ cerr<<"動態(tài)儲存分配失敗"<<endl; e*it(1); } S.top=-1;}voidPush(Stack2&S,ElemType2item){ if(S.top==S.Ma*Size-1){ intk=sizeof(ElemType2); S.stack=(ElemType2*)realloc(S.stack,2*S.Ma*Size*k); S.Ma*Size=2*S.Ma*Size; } S.top++; S.stack[S.top]=item;}ElemType2Pop(Stack2&S){ if(S.top==-1){ cerr<<"Stackisempty!"<<endl; e*it(1); } S.top--; returnS.stack[S.top+1];}ElemType2Peek(Stack2&S){ if(S.top==-1){ cerr<<"Stackisempty!"<<endl; e*it(1); } returnS.stack[S.top];}boolEmptyStack(Stack2&S){ returnS.top==-1;}voidClearStack(Stack2&S){ if(S.stack){ delete[]S.stack; S.stack=0; } S.top=-1; S.Ma*Size=0;}//計算由str所指字符串的后綴表達式的值doublepute(char*str){ Stack2S; InitStack(S); double*,y; inti=0; while(str[i]){ if(str[i]=='') { i++; continue; } switch(str[i]){ case'+': *=Pop(S)+Pop(S); i++; break; case'-': *=Pop(S); *=Pop(S)-*; i++; break; case'*': *=Pop(S)*Pop(S); i++; break; case'/': *=Pop(S); if(*!=0) *=Pop(S)/*; else{ cerr<<"Divideby0!"<<endl; e*it(1); } i++; break; case'^': *=Pop(S); *=pow(Pop(S),*); i++; break; default: *=0; while(str[i]>=48&&str[i]<=57){ *=**10+str[i]-48; i++; } if(str[i]=='.'){ i++; y=0; doublej=10.0; while(str[i]>=48&&str[i]<=5