堆栈应用括号匹配实验

－PAGE2－深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：堆栈应用括号匹配实验学院：计算机与软件学院专业：未分指导教师：杨芳报告人：姜家祥学号：2013150387班级：08实验时间：2013-10-9实验报告提交时间：2014-10-10教务处制一、实验目的掌握堆栈的基本原理掌握堆栈的存储结构掌握堆栈的进栈、弹栈、判断栈空的实现方法掌握应用堆栈实现括号匹配的原理和实现方法二、实验要求熟悉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} } } if(!Empty(S,n))//左括号多于右括号 return-3; if(Empty(S,n))//左右括号匹配 return0; }intmain(){ StackS;stringP; intt,x; //freopen("cin.txt","r",stdin); cin>>t; while(t--) { cin>>P; x=Pipei(S,P); cout<<x<<endl; } return0;}*******************************************************************************#include<iostream>usingnamespacestd;#defineMax_Value100typedefstructNum{ intbase[Max_Value]; inttop;}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; else return0;}voidNum_1(Num&S,inta,intk){ InitNum(S); inte; while(a){ Push(S,a%k); a=a/k;} while(!Empty(S)){ Pop(S,e); if(e>=10) cout<<char(e%10+65); else cout<<e;}}voidNum_2(Num&S,doublea,intk){ InitNum(S); intb,i,e,j=0; for(i=0;i<3;i++){ Push(S,a*k); b=a*k; a=a*k-b; } for(j=1;j<=3;j++){ if(S.base[j]>=10) cout<<char(S.base[j]%10+65); else cout<<S.base[j]; }}intmain(){ intt,k,m; doublea,n; NumS; //freopen("cin1.txt","r",stdin); cin>>t; while(t--){ cin>>a>>k; m=a; n=a-m; Num_1(S,m,k); cout<<"."; Num_2(S,n,k); cout<<endl; } return0;}

五、程序运行时截图

六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）对于第一题，感觉还好，就是有时候感觉有点混，第二题较麻烦，问题大大小小不断，慢慢调试，查看，百度指导教师批阅意见：成绩评定：指导教师签字：