堆栈应用括号匹配实验

深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：堆栈应用括号匹配实验学院：计算机与软件学院专业：未分指导教师：杨芳报告人：姜家祥学号：2013150387班级：08实验时间：2013-10-9实验报告提交时间：2014-10-10教务处制－2－一、实验目的掌握堆栈的基本原理掌握堆栈的存储结构掌握堆栈的进栈、弹栈、判断栈空的实现方法掌握应用堆栈实现括号匹配的原理和实现方法二、实验要求熟悉C++语言编程熟练使用C++语言实现堆栈的进栈Push、插入Pop、判断栈空等操作熟练使用堆栈实现括号匹配算法三、实验内容本次实验有两项内容：（一）堆栈应用括号匹配1、问题描述一个算术表达式中包括圆括号、方括号和花括号三种形式的括号编程实现判别表达式中括号是否正确匹配的算法2、算法顺序扫描算术表达式若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3)从算术表达式中取出一个字符，如果是左括号(‘(‘或‘[‘或‘{‘)，则让该括号进栈(PUSH)如果是右括号(‘)‘或‘]‘或‘}‘)：⑵
、如果栈为空，则说明右括号多于左括号，返回(-2)⑵、如果栈不为空，则从栈顶弹出(POP)一个括号：若括号匹配，则转1继续进行判断；否则，说明左右括号配对次序不正确，返回(-1)3、输入第一行：样本个数，假设为n。第二到n+1行，每一行是一个样本（算术表达式串），共n个测试样本。4、输入样本4{[(1+2)*3]-1}{[(1+2]*3)-1}(1+2)*3)-1}{[(1+2)*3-1]5、输出共有n行，每一行是一个测试结果，有四种结果：0：左右括号匹配正确{[(1+2)*3]-1}－3－-1：左右括号配对次序不正确{[(1+2]*3)-1}-2：右括号多于左括号(1+2)*3)-1}-3：左括号多于右括号{[(1+2)*3-1]6、输出样本0-1-2-3（二）数制转换1、问题描述对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换整数部分19，小数部分0.12519/2=9…10.125*2=0.25…09/2=4…10.25*2=0.5…04/2=2…00.5*2=1…12/2=1…01/2=0…1所以整数部分转为10011，小数部分转为0.001，合起来为10011.001提示整数部分可用堆栈，小数部分可用队列实现注意：必须按照上述方法来实现数制转换，其他方法0分2、输入第一行输入一个t，表示下面将有t组测试数据。接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1k=163、输出对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位4、输入样本219.125215.125165、输出样本10011.001F.200－4－四、程序清单#includeiostreamusingnamespacestd;#includestring#defineMax_Size100typedefstructStack{//定义栈charbase[Max_Size];inttop;}Stack;voidInitStack(Stack&S){//构造空栈S.top=0;}intPush(Stack&S,charch){//元素进栈S.top++;S.base[S.top]=ch;return1;}intPop(Stack&S,charch){//元素出栈S.top--;ch=S.base[S.top];return1;}intEmpty(Stack&s,intn){－5－if(s.top==0){return1;}else{return0;}}intPipei(Stack&S,stringS1){//匹配inti,m=0,n=0,num=0,num1=0;charc,ch,ch1,ch2[100];InitStack(S);for(i=0;iS1.length();i++){c=S1[i];if(c=='('||c==')'||c=='{'||c=='}'||c=='['||c==']')ch2[m++]=c;}//把字符组S1的括号复制到ch2中for(i=0;i=m-1;i++){ch=ch2[i];if(ch=='('||ch=='{'||ch=='[')Push(S,ch);//左括号，进栈if(ch==')'||ch=='}'||ch==']'){num1++;if((ch==')'&&S.base[S.top]=='(')||(ch=='}'&&S.base[S.top]=='{')||(ch==']'&&S.base[S.top]=='['))Pop(S,ch1);//右括号匹配栈顶左括号，左括号出栈else{i=m-1;return-1;}//左右括号不匹配if(Empty(S,n)&&im-1)return-2;//右括号多于左括号－6－}}if(!Empty(S,n))//左括号多于右括号return-3;if(Empty(S,n))//左右括号匹配return0;}intmain(){StackS;stringP;intt,x;//freopen(cin.txt,r,stdin);cint;while(t--){cinP;x=Pipei(S,P);coutxendl;}return0;}*******************************************************************************#includeiostreamusingnamespacestd;#defineMax_Value100typedefstructNum{intbase[Max_Value];inttop;－7－}Num;voidInitNum(Num&S){S.top=0;}intPush(Num&S,inta){if(S.top=Max_Value)return-1;S.top++;S.base[S.top]=a;return1;}intPop(Num&S,int&a){if(S.top=0)return-1;a=S.base[S.top];S.top--;return1;}intEmpty(Num&S){if(S.top==0)return1;elsereturn0;}voidNum_1(Num&S,inta,intk){－8－InitNum(S);inte;while(a){Push(S,a%k);a=a/k;}while(!Empty(S)){Pop(S,e);if(e=10)coutchar(e%10+65);elsecoute;}}voidNum_2(Num&S,doublea,intk){InitNum(S);intb,i,e,j=0;for(i=0;i3;i++){Push(S,a*k);b=a*k;a=a*k-b;}for(j=1;j=3;j++){if(S.base[j]=10)coutchar(S.base[j]%10+65);elsecoutS.base[j];}}intmain(){intt,k,m;－9－doublea,n;NumS;//freopen(cin1.txt,r,stdin);cint;while(t--){cinak;m=a;n=a-m;Num_1(S,m,k);cout.;Num_2(S,n,k);coutendl;}return0;}五、程序运行时截图六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）对于第一题，感觉还好，就是有时候感觉有点混，第二题较麻烦，问题大大小小不断，慢慢调试，查看，百度－10－指导教师批阅意见：成绩评定：指导教师签字：年月日－11－备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。