括号匹配的检查_课程设计

《括号匹配的检查_课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、衡阳师范学院《C语言数据结构》课程设计报告题目：括号匹配的检验班级：1101学号：作者姓名：指导教师：2012年11月12目录1设计题目与要求31.1实验目的31.2问题描述31.3设计要求32总体设计思想及相关知识32.1总体设计思想32.2开发环境与工具........................................................43功能设计43.1抽象数据类型的定义43.2栈的基本运算......................................................43.3栈的基本操作的实现...........

2、.........................................43.4模块流程图64源程序代码65测试及结果96总结117小组成员任务分配11参考文献12121．设计题目与要求1.1实验目的通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈先进后出的特点，掌握栈的表示和实现。1.2问题描述假设表达式中允许包括两种括号:圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或(()]）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列：[([][])]12345

3、678当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号相匹配的，第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务了，······，依次类推。可见，这个处理过程恰与栈的特点相吻合。1.3设计要求读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。2．总体设计思想

4、及相关知识2.1总体设计思想最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：[()[]]、([{}])、{([]]}122.2开发环境与工具系统平台：Windows应用程序实现语言：C语言开发工具：VC++6.03．功能设计3.1抽象数据类型的定义堆栈的定义：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作"栈顶(top)"，不允许插入和删除的另一端称作

5、"栈底(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.3栈的基本操作的实现(1）置空

6、栈（首先建立栈空间，然后初始化栈顶指针）SeqStack*Init_Stack(){SeqStack*s;s=(SeqStack*)malloc(sizeof(SeqStack));s->top=-1;returns;12}(2)判空栈intEmpty_Stack(SeqStack*s){If(s->top==-1)return1;Elsereturn0;}(3)入栈intPush_Stack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)return0;//栈满不能入栈else{s->top++;s->data[s->top]=x;re

7、turn1;}}(4)出栈intPop_Stack(SeqStack*s,datatype*x){if(Empty_Stack(s))return0;//栈空不能出栈else{*x=s->data[s->top];//栈顶元素存入*x，返回s->top--;return1;}}(5)取栈顶元素datatypeTop_Stack(SeqStack*s){12if(Empty_Stack(s))return0;//栈空elsereturn(s->data[s-top]);}3.4模块流程开始输入