括号匹配的检验

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

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

4、数原型： stacknotempty(seqstack s) 功能： 判断堆栈是否为空 代码：int stacknotempty(seqstack s) if(s.toptop=maxstack) printf(堆栈已满无法插入！n);return 0;elses-stacks-top=x;s-top+;return 1;（4）函数原型：stackpop(seqstack *s , datatype *d) 功能：堆栈中数据元素出栈 代码：int stackpop(seqstack *s , datatype *d) if(s-toptop-;*d=s-stacks-top;return 1;

5、（5）函数原型：stacktop(seqstack s , datatype *d) 功能：取堆栈中栈顶元素 代码：int stacktop(seqstack s , datatype *d)if(s.toptop=0;int stacknotempty(seqstack s) /*判断非空否*/if(s.toptop=maxstack) printf(堆栈已满无法插入！n);return 0;elses-stacks-top=x;s-top+;return 1;int stackpop(seqstack *s , datatype *d) /*出栈*/if(s-toptop-;*d=s-st

6、acks-top;return 1;int stacktop(seqstack s , datatype *d)if(s.top=0)printf(堆栈已空！n);return 0;else*d = s.stacks.top-1;return 1;void expiscorrect(char expmaxstack ) /*判断有n个字符的的字符串exp左、右括号是否配对正确*/seqstack mystack;int i;char c;stackinitiate(&mystack); for (i=0 ; expi != 0 ; i+)if ( ( expi = ( ) | ( expi =

7、 ) )stackpush(&mystack , expi ); /*入栈*/else if ( expi = ) & stacknotempty(mystack) & stacktop(mystack , &c) & c = ()stackpop ( &mystack , &c );else if ( expi = ) & stacknotempty(mystack) & stacktop(mystack , &c) & c != ( )printf(此串括号匹配不合法！n);return;else if ( expi = & stacknotempty(mystack) & stacktop(mystack , &c)& c =)stackpop(&mystack , &c);else if ( expi = & stacknotempty(mystack) & stacktop(mystack , &c)& c != )printf(此串括号匹配不合法！n);return;else if( ( expi =) ) | ( expi = ) & !stacknotempty(mystack) )printf(此串括号匹配不合法！n);return; if ( stacknotempty(my