實(shí)驗(yàn)二 棧的應(yīng)用-算術(shù)表達(dá)式的計(jì)算

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