《括号匹配的检验.doc》由会员分享，可在线阅读，更多相关《括号匹配的检验.doc（11页珍藏版）》请在三一办公上搜索。
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) & Stackto
8、p(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(mystack) )printf(此串括号匹配不合法！n);elseprintf(匹配！n);void main()char strMaxstack;printf(请输入要匹配的括号的序列:n);gets(str);Expiscorrect(str);
