数据结构实验报告(实验三).doc

深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 实验三：栈的应用 学院： 计算机与软件学院 专业： 指导教师： 蔡平 报告人： 文成 学号： 2011150259 班级： 5 实验时间： 2012-10-08 实验报告提交时间： 2012-10-20 教务部制 一、实验目的与要求： 目的： 1.掌握线性表的基本原理 2.掌握线性表地基本结构 3.掌握线性表地创建、插入、删除、查找的实现方法 要求： 1.熟悉C++语言编程 2.熟练使用C++语言实现线性表地创建、插入、删除、查找的实现方法 二、实验内容： Problem A: 数据结构——实验3——STL堆栈对象的例程 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 103 Solved: 85 [Submit][Status][Web Board] Description 掌握C++中STL自带的堆栈对象应用。 演示堆栈对象的各种操作，以字符串的逆序输出为例子 输入一个字符串，按输入顺序将字符压入堆栈，然后根据堆栈后进先出的特点，做逆序输出 Input 第一行输入t，表示有t个测试实例 第二起，每一行输入一个字符串，注意字符串不要包含空格 Output 每行逆序输出每一个字符串 Sample Input 2 abcdef aabbcc Sample Output fedcba ccbbaa HINT Problem B: 数据结构——实验3——堆栈应用之括号匹配 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 365 Solved: 120 [Submit][Status][Web Board] Description 处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下： ( ) [ ( ) ( [ ] ) ] { } 1 2 3 4 5 6 7 8 9 10 11 12 从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则： 1、 当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。 2、 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除 3、 若到最后，括号不能完全匹配，则说明输入的表达式有错 Input 第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入 Output 对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error Sample Input 2 (a+b)[4*5+(-6)] [5*8]/{(a+b)-6 Sample Output ok error HINT 算法流程 1、初始化，i=0，建立堆栈，栈为空 2、输入表达式，建立指针指向表达式的头部 3、读入表达式的第i个字符 4、如果第i个字符是左括号，入栈 5、如果第i个字符是右括号，检查栈顶元素是否匹配 A.如果匹配，弹出栈顶元素 B.如果不匹配，报错退出 6、i++，指向下一个字符，是否已经表达式末尾 A. 未到末尾，重复步骤3 B. 已到达末尾 a. 堆栈为空，输出ok b. 堆栈不为空，输出error 实验步骤与过程： 源代码： A： #includeiostream #includestring.h #includestdlib.h #includeiomanip using namespace std; const