括号匹配的检验

1、湖南工学院计算机与信息科学系课程设计报告 20102010学年第一学期课程名称 数据结构 设计题目 括号匹配的检验 姓名 专业班级 2 学号 2010 年 12 月31 日目录1 设计任务书 1.1 题目与要求1.2 设计中涉及的知识点 2 功能设计 2.1抽象数据类型的定义2.2 模块流程图 3 程序代码设计与说明 3.1 子程序设计与其功能3.2 主函数设计与其功能 4 程序设计总结 4.1 程序调试情况4.2 个人经验及体会 5 用户使用说明 6测试结果 7 附录（源程序）1 设计任务书1.1 题目与要求问题描述假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（） ）或（

2、 ）等为正确格式，（ ）或（均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： ( ) 1 2 3 4 5 6 7 8当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了

3、满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了， ，依次类推。可见这个处理过程正好和栈的特点相吻合。基本要求读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。1.2 设计中涉及的知识点编译预处理（文件包含）、选择结构、循环结构、堆栈、函数2 功能设计2.1抽象数据类型的定义包括堆栈的定义3 程序代码设计3.1子程序设计及其功能（1）函数原型： Stackinitiate(Seqstack *S)功能：初始化堆栈代码：void Stackinitiate(Seqstack *S)S->top=0;（2）函数原型： Stacknotempty(Seqstack S

4、)功能： 判断堆栈是否为空代码：int Stacknotempty(Seqstack S)if(S.top<=0)return 0;else return 1;（3）函数原型：Stackpush(Seqstack *S, Datatype x) 功能： 数据元素入栈代码：int Stackpush(seqstack *S, Datatype x)if(S->top>=Maxstack)printf("堆栈已满无法插入！n");return 0;elseS->stackS->top=x;S->top+;return 1;（4）函数原型：St

5、ackpop(Seqstack *S , Datatype *d) 功能：堆栈中数据元素出栈代码：int Stackpop(Seqstack *S , Datatype *d)if(S->top<=0)printf("堆栈已空无数据元素出栈！n");return 0;elseS->top-;*d=S->stackS->top;return 1;（5）函数原型：Stacktop(Seqstack S , Datatype *d)功能：取堆栈中栈顶元素代码：int Stacktop(Seqstack S , Datatype *d)if(S.top

6、<=0)printf("堆栈已空！n");return 0;else*d = S.stackS.top-1;return 1;3.2 主函数设计及其功能代码：void main()char strMaxstack;printf("请输入要匹配的括号的序列:n");gets(str);void Expiscorrect(str);功能：输入一组括号的序列，可检验括号是否匹配正确。4 程序设计总结4.1 程序调试情况出现了很多的小错误，咧如：missing '' 、syntax error : ')' 在调用函数的时候用

7、了黏贴和复杂 加了一下无效的字符，定义符号也加了进去，还有大小写的一些错误。4.2 个人经验及体会经过一个星期的上机实践学习，使我对c语言和数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对c语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对c语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习c语言，还是其它的语言，以及其它的计算机方面的知识都要重在

8、实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。5 用户使用说明步骤：输入你想匹配的括号的序列，再按回车键。会出现匹配！和此串括号匹配不合法！两种结果。6测试结果7 附录（源程序）#include "string.h"#include "stdio.h"#define Maxstack 100typedef char DataType;/#include "SeqStack.h"typedef structDataType stackMaxstack;int top;Seqstack; /*定义结构体*/voi

9、d Stackinitiate(Seqstack *S) /*初始化*/ S->top=0;int Stacknotempty(Seqstack S) /*判断非空否*/ if(S.top<=0)return 0;else return 1;int Stackpush(Seqstack *S , DataType x) /*入栈*/ if(S->top>=Maxstack)法插入！n");elseS->stackS->top=x;int Stackpop(Seqstack *S , DataType *d) /*出栈*/ printf("

10、堆栈已满无return 0; S->top+; return 1;if(S->top<=0)数据元素出栈！n");else*d=S->stackS->top;int Stacktop(Seqstack S , DataType *d) if(S.top<=0)n");elseS.stackS.top-1;void Expiscorrect(char expMaxstack ) 否配对正确*/Seqstack mystack;int i;char c;Stackinitiate(&mystack);for (i=0 ; expi !

11、= '0' ; i+) ( expi = '' ) ) printf("堆栈已空无return 0; S->top-; return 1; printf("堆栈已空！return 0; *d = return 1; /*判断有n个字符的的字符串exp左、右括号是if ( ( expi = '(' ) |Stackpush(&mystack , expi ); /*入栈*/&& Stacknotempty(mystack) && Stacktop(mystack , &c)(

12、 &mystack , &c );&& Stacknotempty(mystack) && Stacktop(mystack , &c)括号匹配不合法！n");&& Stacknotempty(mystack) && Stacktop(mystack , &c)Stackpop(&mystack , &c);&& Stacknotempty(mystack) && Stacktop(mystack , &c)括号匹配不合法！n&quo

13、t;);=')' ) | ( expi = '' ) && !Stacknotempty(mystack) )匹配不合法！n"); if ( Stacknotempty(mystack) )配不合法！n"); else void main()else if ( expi = ')' && c = '(') Stackpop else if ( expi = ')' && c != '(' ) printf("此串 return; else if ( expi = '' && c ='')else if ( expi = '' &&am