括号匹配检查课程设计.docVIP

衡阳师范学院 《C语言 数据结构》 题 目： 括号匹配的检验 班 级： 1 1 0 1 学 号： 作者姓名： 指导教师： 2012年11月目 录 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 1．设计题目与要求 1.1实验目的 通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈先进后出的特点，掌握栈的表示和实现。 1.2问题描述 假设表达式中允许包括两种括号:圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或(()]）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号相匹配的，第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务了，······，依次类推。可见，这个处理过程恰与栈的特点相吻合。 1.3设计要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。 2．总体设计思想及 2.1总体设计思 最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：[()[]]、 ([{}]) 、{([]]} 2.2开发环境与工具 系统平台：实现语言：C 开发工具：3．功能设计 3.1抽象数据类型的定义 堆栈的定义：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作栈顶(top)，不允许插入和删除的另一端称作栈底(bottom) 。=( 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)取栈顶元素 datatype Top_Stack(SeqStack *s) { if (Empty_Stack(s)) return 0; //栈空 else return(s-data[s-top]); } 3.4模块流程 4.源程序代码 #includestdio.