括号匹配的检查 课程设计

衡衡阳阳师师范范学学院院 C C 语语言言 数数据据结结构构 题题 目 目 括号匹配的检验括号匹配的检验 班班 级 级 1 1 1 1 0 0 1 1 学学 号 号 作者姓名 作者姓名 指导教师 指导教师 2012 年 11 月 课程设计报告 2 目 录 1 设计题目与要求 3 1 1 实验目的 3 1 2 问题描述 3 1 3 设计要求 3 2 总体设计思想及相关知识 3 2 1 总体设计思想 3 2 2 开发环境与工具 4 3 功能设计 4 3 1 抽象数据类型的定义 4 3 2 栈的基本运算 4 3 3 栈的基本操作的实现 4 3 4 模块流程图 6 4 源程序代码 6 5 测试及结果 9 6 总结 11 7 小组成员任务分配 11 参考文献 12 3 1 设计题目与要求 1 1 实验目的 通过对括号匹配的检验的程序设计编写 深入了解和掌握栈的使用 了解 栈先进后出的特点 掌握栈的表示和实现 1 2 问题描述 假设表达式中允许包括两种括号 圆括号和方括号 其嵌套的顺序随意 即 或 等为正确的格式 或 均为不正确的格式 检验括号是否匹配 的方法可用 期待的急迫程度 这个概念来描述 例如考虑下列括号序列 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后 它期待着与其匹配的第八个括号的出现 然 而等来的却是第二个括号 此时第一个括号只能暂时靠边 而迫切等待与第二 个括号相匹配的 第七个括号的出现 类似的 因等来的第三个括号 其期待 的匹配程度较第二个括号更急迫 则第二个括号也只能靠边 让位于第三个括 号 显然第二个括号的期待急迫性高于第一个括号 在接受了第四个括号后 第三个括号的期待得到满足 消解之后 第二个括号的期待匹配成了当前最急 迫的任务了 依次类推 可见 这个处理过程恰与栈的特点相 吻合 1 3 设计要求 读入圆括号和方括号的任意序列 输出 匹配 或 此串括号匹配不合法 2 总体设计思想及相关知识 2 1 总体设计思想 最内层 最迟出现 的左括号必须与最内层 最早出现 的同类右括号匹 配 它最期待着急迫的配对 配对之后 期待得以消除 因此为左括号设置一 个栈 置于栈顶的左括号期待配对的急切程度最高 另外 在算法的开始和结 4 束时 栈都应该是空的 例如 2 2 开发环境与工具 系统平台 Windows 应用程序 实现语言 C 语言 开发工具 VC 6 0 3 功能设计 3 1 抽象数据类型的定义 堆栈的定义 栈 Stack 是限定只能在表的一端进行插入和删除操作的线 性表 在表中 允许插入和删除的一端称作 栈顶 top 不允许插入和删除的 另一端称作 栈底 bottom 3 2 栈的基本运算 1 栈初始化 Init Stack s 操作结果是构造了一个空栈 2 判栈空 Empty Stack s 操作结果是若 s 为空返回 1 否则返回为 0 3 入栈 Push Stack s x 操作结果是在栈 s 的顶部插入一个新的元素 x x 成为新的栈顶元素 栈发生变化 4 出栈 Pop Stack s 在栈 s 存在且非空的情况下 操作结果是将栈 s 的 顶部元素从栈中删除 栈中少了一个元素 栈发生变化 5 读栈顶元素 Top Stack s 在栈 s 存在且非空的情况下 操作结果是读 栈顶元素 栈不变化 3 33 3 栈的基本操作的实现 1 置空栈 首先建立栈空间 然后初始化栈顶指针 SeqStack Init Stack SeqStack s 5 s SeqStack malloc sizeof SeqStack s top 1 return s 2 判空栈 int Empty Stack SeqStack s If s top 1 return 1 Else return 0 3 入栈 int Push Stack SeqStack s datatype x if s top MAXSIZE 1 return 0 栈满不能入栈 else s top s data s top x return 1 4 出栈 int Pop Stack SeqStack s datatype x if Empty Stack s return 0 栈空不能出栈 else x s data s top 栈顶元素存入 x 返回 s top return 1 5 取栈顶元素 6 datatype Top Stack SeqStack s if Empty Stack s return 0 栈空 else return s data s top 3 43 4 模块流程 输 出 输 出 判断括号 是否匹配 4 源程序代码 include include define MAXSIZE 100 typedef char datatype struct SeqStack 开 始 输入括号序列 7 datatype data MAXSIZE int top SeqStack Init Stack SeqStack s s SeqStack malloc sizeof SeqStack s top 1 return s int Empty Stack SeqStack s if s top 1 return 1 else return 0 int Push Stack SeqStack s datatype x if s top MAXSIZE 1 return 0 栈满不能入栈 else s top s data s top x return 1 int Pop Stack SeqStack s datatype x if Empty Stack s return 0 栈空不能出栈 else x s data s top 栈顶元素存入 x 返回 s top return 1 8 datatype Top Stack SeqStack s if Empty Stack s return 0 栈空 else return s data s top int match char s SeqStack st datatype x char p s st Init Stack while p switch p case case case Push Stack st p break case if Top Stack st Pop Stack st else return 0 break case if Top Stack st Pop Stack st else return 0 break case if Top Stack st Pop Stack st else return 0 break default return 0 break p 9 return Empty Stack st 1 0 int main printf 请输入一组或多组括号序列 按 enter 键结束输入 n char s MAXSIZE while gets s printf match s 括号匹配 n 括号不匹配 n return 0 5 测试及结果 10 图 5 1 图 5 2 图 5 3 11 图 5 4 6 总结 经过了两周的时间 我们完成了这个课程设计 通过这次课程设计 我们学到了很多关于数据结构中栈的使用操作 经过 这些天的上机操作 我们也意识到了自己的不足之处 例如容易把符号打错 在查找错误时难以发现等问题 在这程序设计中遇到的问题 一般上网查询或 者问上一届的同学 参考他人的做法 多次操作失败过 但还是一步步改正 所以说 这次的课程设计给了我们一个提高 过程中发现对 C 语言还是不太 熟悉 数据结构很重要 多实践操作很关键 在以后的计算机学习过程中 理 解理论知识 注重实践操作 小组成员任务分配小组成员任务分配 程序编程前阶段 全组成员查看相关