堆栈应用括号匹配实验.doc

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 堆栈应用括号匹配实验 学院： 计算机与软件学院 专业： 未分 指导教师： 杨芳 报告人： 姜家祥 学号：2013150387 班级： 08 实验时间： 2013-10-9 实验报告提交时间： 2014-10-10 教务处制一、实验目的 掌握堆栈的基本原理掌握堆栈的存储结构掌握堆栈的进栈、弹栈、判断栈空的实现方法掌握应用堆栈实现括号匹配的原理和实现方法二、实验要求 熟悉C+语言编程熟练使用C+语言实现堆栈的进栈Push、插入Pop、判断栈空等操作熟练使用堆栈实现括号匹配算法三、实验内容 本次实验有两项内容：（一）堆栈应用括号匹配1、问题描述一个算术表达式中包括圆括号、方括号和花括号三种形式的括号编程实现判别表达式中括号是否正确匹配的算法2、算法顺序扫描算术表达式若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3)从算术表达式中取出一个字符，如果是左括号(或或 )，则让该括号进栈(PUSH)如果是右括号()或或 )：2、 如果栈为空，则说明右括号多于左括号，返回(-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-15、输出共有n行，每一行是一个测试结果，有四种结果：0：左右括号匹配正确(1+2)*3-1-1：左右括号配对次序不正确(1+2*3)-1-2：右括号多于左括号(1+2)*3)-1-3：左括号多于右括号(1+2)*3-16、输出样本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 0 0.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.125 215.125 165、输出样本10011.001F.200四、程序清单#includeusing namespace std;#include#define Max_Size 100typedef struct Stack /定义栈char baseMax_Size; int top;Stack;void InitStack(Stack &S) /构造空栈S.top=0;int Push(Stack &S,char ch) /元素进栈S.top+;S.baseS.top=ch;return 1;int Pop(Stack &S,char ch) /元素出栈S.top-;ch=S.baseS.top;return 1;int Empty(Stack &s,int n) if(s.top=0) return 1; else return 0;int Pipei(Stack &S,string S1) /匹配int i,m=0,n=0,num=0,num1=0; char c,ch,ch1,ch2100;InitStack(S);for(i=0;iS1.length();i+)c=S1i;if(c=(|c=)|c=|c=|c=|c=)ch2m+=c;/把字符组S1的括号复制到ch2中for(i=0;i=m-1;i+)ch=ch2i;if(ch=(|ch=|ch=)Push(S,ch);/左括号，进栈if(ch=)|ch=|ch=)num1+;if(ch=)&S.baseS.top=()|(ch=&S.baseS.top=)|(ch=&S.baseS.top=)Pop(S,ch1);/右括号匹配栈顶左括号，左括号出栈elsei=m-1;return -1;/左右括号不匹配if(Empty(S,n)⁢while(t-)cinP;x=Pipei(S,P);coutxendl;return 0;*#includeusing namespace std;#define Max_Value 100typedef struct Numint baseMax_Value;int top;Num;void InitNum(Num &S)S.top=0;int Push(Num &S,int a )if(S.top=Max_Value)return -1;S.top+;S.baseS.top=a;return 1;int Pop(Num &S,int &a)if(S.top=10)coutchar(e%10+65);elsecoute;void Num_2(Num &S,double a,int k)InitNum(S);int b,i,e,j=0;for(i=0;i3;i+)Push(S,a*k);b=a*k;a=a*k-b;for(j=1;j=10)coutchar(S.basej%10+65);elsecoutt;while(t-)cinak;m=a;n=a-m;Num_1(S,m,k);cout.;Num_2(S,n,k);coutendl;return 0;五、程序运行时截图六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）对于第一题，感觉还好，就