实验二 栈的应用-算术表达式的计算

-.z.大学城市学院实验报告课程名称数据构造与算法实验工程名称实验二栈的应用---算术表达式的计算实验成绩指导教师〔签名〕日期实验目的和要求1．进一步掌握栈的根本操作的实现。2．掌握栈在算术表达式的计算方面的应用。二.实验容1.编写程序利用栈将中缀表达式转换成后缀表达式，即从键盘输入任一个中缀表达式〔字符串形式〕，转换成后缀表达式后，将后缀表达式输出。假设：中缀表达式包含圆括号()及双目运算符+、-、*、/、^〔乘方〕。要求：把栈的根本操作的实现函数存放在头文件stack1.h中〔栈元素的类型为char〕，在主文件test6_2.cpp中包含将中缀表达式S1转换成后缀表达式S2的转换函数voidChange(char*S1,char*S2)及主函数，在主函数中进展输入输出及转换函数的调用。2.选做：编写利用栈对后缀表达式进展求值的函数doublepute(char*str)，以计算从前述程序得到的后缀表达式的值。要求：把栈的根本操作的实现函数存放在头文件stack2.h中〔栈元素的类型为double〕，在主文件test6_2.cpp中添加后缀表达式求值函数，并在主函数中增加调用求值函数及输出结果值的语句。3.填写实验报告，实验报告文件取名为report2.doc。4.上传实验报告文件report2.doc与源程序文件stack1.h、stack2.h〔假设有〕及test6_2.cpp到Ftp效劳器上你自己的文件夹下。函数的功能说明及算法思路〔算法思路见源程序的注释局部〕//栈的顺序存储构造定义structStack{ ElemType*stack; inttop; intMa*Size;};//初始化栈S为空voidInitStack(Stack&S)//元素item进栈，即插入到栈顶voidPush(Stack&S,ElemTypeitem)//删除栈顶元素并返回ElemTypePop(Stack&S)//读取栈顶元素的值ElemTypePeek(Stack&S)//判断S是否为空，假设是则返回true，否则返回falseboolEmptyStack(Stack&S)//去除栈S中的所有元素，释放动态存储空间voidClearStack(Stack&S)//将中缀算术表达式转换为后缀算术表达式voidChange(char*S1,char*&S2)//返回运算符op所对应的优先级数值intPrecedence(charop)//计算由str所指字符串的后缀表达式的值doublepute(char*str)四.实验结果与分析五.心得体会【附录----源程序】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<<"请输入一个中缀算术表达式："; cin.getline(*,sizeof(*)); Change(*,y); cout<<"对应的后缀算术表达式为："; cout<<y<<endl; r=pute(y); cout<<"后缀算术表达式值为："<<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<<"动态储存分配失败"<<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所对应的优先级数值intPrecedence(charop){ switch(op){ case'+': case'-': return1; case'*': case'/': return2; case'^': return3; case'(': case'': default: return0; }}//将中缀算术表达式转换为后缀算术表达式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);//删除栈顶的左括号 ch=S1[++i]; } //对于运算符，使暂存于栈顶且不低于ch优先级的运算符依次出栈并写入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<<"动态储存分配失败"<<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