实验03：堆栈应用括号匹配实验报告.doc

深圳大学实验报告课程名称： 数据结构实验与课程设计实验项目名称： 堆栈应用括号匹配实验学院上杨芳专业:指导教师言报告人:学号三班级:实验时间： 2013.10.9 实验报告提交时间： 教务处制一、 实验目的掌握堆栈的基本原理掌握堆栈的存储结构掌握堆栈的进栈、弹栈、判断栈空的实现方法掌握应用堆栈实现括号匹配的原理和实现方法二、 实验要求熟悉C++语言编程熟练使用C++语言实现堆栈的进栈Push、插入Pop、判断栈空等操作熟练使用堆栈实现括号匹配算法三、 实验内容本次实验有两项内容：(一)堆栈应用括号匹配1、 问题描述一个算术表达式中包括圆括号、方括号和花括号三种形式的括号编程实现判别表达式中括号是否正确匹配的算法2、 算法顺序扫描算术表达式若算术表达式扫描完成，此时如果栈空，则正确返|n| (0);如果栈未空，说明左括号多 于右括号，返回(-3)从算术表达式中取出一个字符，如果是左括号((或[或则让该括号进 栈(PUSH)如果是右括号()或]或})：⑵「、 如果栈为空，则说明右括号多于左括号，返|n|(-2)⑵、如果栈不为空，则从栈顶弹出(POP) 一个括号：若括号匹配，则转1继续进行判断；否 则，说明左右括号配对次序不正确，返H(-l)3、 输入第一行：样木个数，假设为』第二到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}-1：左右括号配对次序不正确([(1+2]*3)-1}-2：右括号多于左括号-3：左括号多于右括号(1+2)*3)-1} ([(1+2)*3-1]6、输出样木0-1-2-3（二）数制转换1、问题描述对于任意十进制数转换为k进制，包括整数部分和小数部分转换整数部分采用除k求 余法，小数部分采用乘k取整法例如x=19. 125,求2进制转换整数部分19, 小数部分0. 12519 / 2 = 9 ••• 1 0. 125 * 2 = 0.25 …09 / 2 = 4 …1 0. 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表示要转换的数 制，Kk<=163、 输出对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位4、 输入样木219. 125 215. 125 165、 输出样本10011.001F.200四、程序清单•五、程序运行时截图六、实验心得与体会（实验中遇到的问题及解决方案，或写点感想）指导教师批阅意见:成绩评定:指导教师签字：年 月 日备注:注：1、报告内的项bl或内容设置，可根据实际情况加以调整和补充2、教师批改学生实验报告时间应在学生提交实验报告时间后10 口内。