括号匹配的检查 课程设计
衡阳师范学院
《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开发环境与工具
系统平台: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.3栈的基本操作的实现
(1)置空栈(首先建立栈空间,然后初始化栈顶指针) SeqStack * Init_Stack() {
SeqStack *s;
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)取栈顶元素
datatype Top_Stack(SeqStack *s) {
if (Empty_Stack(s)) return 0; //栈空 else return(s->data[s-top]); }
3.4模块流程
4.源程序代码
#include #include #define MAXSIZE 100 typedef char datatype; struct SeqStack { datatype data[MAXSIZE];
};
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;} }
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,&x);else 0;break;
case ']':if(Top_Stack(st)=='[') Pop_Stack(st,&x);else 0;break;
case '}':if(Top_Stack(st)=='{') Pop_Stack(st,&x);else 0;break; default:return 0;break; } p++;
}
return Empty_Stack(st)?1:0;
}
return
return
return
int main() { }
printf("请输入一组或多组括号序列,按enter键结束输入:\n"); char s[MAXSIZE]; while(gets(s)) { }
return 0;
printf(match(s)?"括号匹配\n":"括号不匹配\n");
5.测试及结果
图5-1
图5-2
图5-3
图5-4
6.总结
经过了两周的时间,我们完成了这个课程设计。
通过这次课程设计,我们学到了很多关于数据结构中栈的使用操作。经过这些天的上机操作,我们也意识到了自己的不足之处,例如容易把符号打错,在查找错误时难以发现等问题。在这程序设计中遇到的问题,一般上网查询或者问上一届的同学,参考他人的做法,多次操作失败过,但还是一步步改正。 所以说,这次的课程设计给了我们一个提高,过程中发现对C语言还是不太熟悉,数据结构很重要,多实践操作很关键。在以后的计算机学习过程中,理解理论知识,注重实践操作。
小组成员任务分配
程序编程前阶段:全组成员查看相关资料,包括书本资料和网上资料,共同讨论实现方案,及设计思想;
程序编写阶段:XX进行上机操作,完成程序基本框架
程序报告编写:XX
格式的排版及修改:XX
参考文献
[1]严蔚敏 吴伟民 编著·。数据结构:C语言版。北京:清华大学出版社,2007
[2周海英 马巧梅 编著。数据结构与算法设计(第二版)。北京:国防工业出版社,2009.6