实验二栈的应用算术表达式的计算.docx
- 文档编号:11007834
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:14
- 大小:32.83KB
实验二栈的应用算术表达式的计算.docx
《实验二栈的应用算术表达式的计算.docx》由会员分享,可在线阅读,更多相关《实验二栈的应用算术表达式的计算.docx(14页珍藏版)》请在冰点文库上搜索。
实验二栈的应用算术表达式的计算
浙江大学城市学院实验报告
课程名称数据结构与算法
实验项目名称实验二栈的应用---算术表达式的计算
实验成绩指导老师(签名)日期
一.实验目的和要求
1.进一步掌握栈的基本操作的实现。
2.掌握栈在算术表达式的计算方面的应用。
二.实验内容
1.编写程序利用栈将中缀表达式转换成后缀表达式,即从键盘输入任一个中缀表达式(字符串形式),转换成后缀表达式后,将后缀表达式输出。
假设:
中缀表达式包含圆括号()及双目运算符+、-、*、/、^(乘方)。
要求:
把栈的基本操作的实现函数存放在头文件stack1.h中(栈元素的类型为char),在主文件test6_2.cpp中包含将中缀表达式S1转换成后缀表达式S2的转换函数voidChange(char*S1,char*S2)及主函数,在主函数中进行输入输出及转换函数的调用。
2.选做:
编写利用栈对后缀表达式进行求值的函数doubleCompute(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;
intMaxSize;
};
//初始化栈S为空
voidInitStack(Stack&S)
//元素item进栈,即插入到栈顶
voidPush(Stack&S,ElemTypeitem)
//删除栈顶元素并返回
ElemTypePop(Stack&S)
//读取栈顶元素的值
ElemTypePeek(Stack&S)
//判断S是否为空,若是则返回true,否则返回false
boolEmptyStack(Stack&S)
//清除栈S中的所有元素,释放动态存储空间
voidClearStack(Stack&S)
//将中缀算术表达式转换为后缀算术表达式
voidChange(char*S1,char*&S2)
//返回运算符op所对应的优先级数值
intPrecedence(charop)
//计算由str所指字符串的后缀表达式的值
doubleCompute(char*str)
四.实验结果与分析
五.心得体会
【附录----源程序】
test6_2.cpp
#include
#include
#include
#include"stack1.h"
#include"stack2.h"
voidmain()
{
charx[30],y[30];
doubler;
while
(1){
cout<<"请输入一个中缀算术表达式:
";
cin.getline(x,sizeof(x));
Change(x,y);
cout<<"对应的后缀算术表达式为:
";
cout< r=Compute(y); cout<<"后缀算术表达式值为: "< } } stack1.h typedefcharElemType1; structStack1{ ElemType1*stack; inttop; intMaxSize; }; voidInitStack(Stack1&S) { S.MaxSize=10; S.stack=newElemType1[S.MaxSize]; if(! S.stack){ cerr<<"动态储存分配失败"< exit (1); } S.top=-1; } voidPush(Stack1&S,ElemType1item) { if(S.top==S.MaxSize-1){ intk=sizeof(ElemType1); S.stack=(ElemType1*)realloc(S.stack,2*S.MaxSize*k); S.MaxSize=2*S.MaxSize; } S.top++; S.stack[S.top]=item; } ElemType1Pop(Stack1&S) { if(S.top==-1){ cerr<<"Stackisempty! "< exit (1); } S.top--; returnS.stack[S.top+1]; } ElemType1Peek(Stack1&S) { if(S.top==-1){ cerr<<"Stackisempty! "< exit (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.MaxSize=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<<"中缀表达式表示错误! "< exit (1); } while((ch>='0'&&ch<='9')||ch=='.'){ S2[j++]=ch; ch=S1[++i]; } S2[j++]=''; } } //把暂存在栈中的运算符依次退栈并写入到S2中 ch=Pop(R); while(ch! ='@'){ if(ch=='('){ cerr<<"expressionerror! "< exit (1); } else{ S2[j++]=ch; ch=Pop(R); } } S2[j++]='\0'; } stack2.h typedefdoubleElemType2; structStack2{ ElemType2*stack; inttop; intMaxSize; }; voidInitStack(Stack2&S) { S.MaxSize=10; S.stack=newElemType2[S.MaxSize]; if(! S.stack){ cerr<<"动态储存分配失败"< exit (1); } S.top=-1; } voidPush(Stack2&S,ElemType2item) { if(S.top==S.MaxSize-1){ intk=sizeof(ElemType2); S.stack=(ElemType2*)realloc(S.stack,2*S.MaxSize*k); S.MaxSize=2*S.MaxSize; } S.top++; S.stack[S.top]=item; } ElemType2Pop(Stack2&S) { if(S.top==-1){ cerr<<"Stackisempty! "< exit (1); } S.top--; returnS.stack[S.top+1]; } ElemType2Peek(Stack2&S) { if(S.top==-1){ cerr<<"Stackisempty! "< exit (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.MaxSize=0; } //计算由str所指字符串的后缀表达式的值 doubleCompute(char*str) { Stack2S; InitStack(S); doublex,y; inti=0; while(str[i]){ if(str[i]=='') { i++; continue; } switch(str[i]){ case'+': x=Pop(S)+Pop(S); i++; break; case'-': x=Pop(S); x=Pop(S)-x; i++; break; case'*': x=Pop(S)*Pop(S); i++; break; case'/': x=Pop(S); if(x! =0) x=Pop(S)/x; else{ cerr<<"Divideby0! "< exit (1); } i++; break; case'^': x=Pop(S); x=pow(Pop(S),x); i++; break; default: x=0; while(str[i]>=48&&str[i]<=57){ x=x*10+str[i]-48; i++; } if(str[i]=='.'){ i++; y=0; doublej=10.0; while(str[i]>=48&&str[i]<=57){ y=y+(str[i]-48)/j; i++; j*=10; } x+=y; } } Push(S,x); } if(EmptyStack(S)){ cerr<<"expressionerror! "< exit (1); } x=Pop(S); if(EmptyStack(S)) returnx; else{ cerr<<"expressionerror! "< exit (1); } ClearStack(S); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验二 栈的应用算术表达式的计算 实验 应用 算术 表达式 计算