括号匹配算法的设计与实现-数据结构课程设计

河南工程学院数据结构与算法课程设计成果报告括号匹配算法的设计与实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号匹配算法的设计与实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计的基本要求12 分析与设计22.1 括号匹配的概述22.2 存储结构设计22.3 算法描述42.4 程序流程图63 程序清单74 测试104.1 测试数据104.2 测试结果分析105 总结116参考文献121 课程设计目标与任务1.1 课程设计目标（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力。（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计任务 设计括号匹配的相关函数库，以便在程序设计中调用，要求：（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。（2）能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计的基本要求严格按照题意要求，独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设计报告，做好设计总结。2 分析与设计2.1 括号匹配的概述假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( ( ) )或 ( ) 等为正确的格式， ( 或 ( ) 或( ( ) 均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号排序： ( ) 12345678当计算机接受了第一个括号后，它期待着预期匹配的第八个括号的出现，然而等来的确实第二个括号，此时的第一个括号只能暂时等待。第二个括号期待着第七个括号的出现，然而等来的确实第三个括号，第二个括号仍然需要让先。第三个括号出现之后期待着第四个括号的出现，匹配完成之后第二个括号继续开始期待，依此类推，即可完成对括号的匹配。可见这个处理过程恰好和栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，如是右括号，则或者使置于栈顶的最迫切的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更迫切的期待压入栈，自然使原有的在栈中的左右未消解的急迫性都降了一级。另外，在算法的开始和结束时，栈都是空的。2.2 存储结构设计构造一个空栈S， int InitStack(SqStack &S)S.base=(SElemType * )malloc(sizeof(SElemType);if(!S.base)exit(0); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;判断构造的若栈S是否为空栈，用于主函数中对于括号出栈是否为空作为判断。若为空则返回TRUE，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;将栈清空，以用来进栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base;栈的销毁void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;2.3 算法描述构造一个算法，用来确定什么样的情况括号匹配是正确的。int Comp(char a,char b)if(a=(&b!=)|(a=&b!=)|(a=&b!=)return 0;else return 1;事先够想出括号匹配错误的情况，并加以分析，只有三种，做括号多出，右括号多出或者括号紊乱。分析出来错误的情况并输出。Status GetCount(SqStack *S)char eSTACK_INIT_SIZE;char e1;int i=0;InitStack(*S);printf(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括号匹配错误); exit(0);for(i=0;ei!=0;i+)/以/0判断输入是否结束switch(ei)case (:case :case :Push(*S,ei);break; case ):case :case : GetTop(*S,e1); if(GetTop(*S,e1)=0) printf(右括号多余); exit(0); if(Comp(e1,ei)=1) Pop(*S,e1); /S-top-; else printf(括号匹配错误n); exit(0);if(S-top!=S-base)printf(左括号多余n);else printf(括号匹配正确n);return 0;2.4 程序流程图程序有两个模块一个模块存储括号配对的正确情况， Comp（）方法用来判断括号配对的正确情况（详情参考图2.4 程序流程图2）如左右括号多出等。GetCount（）用来判断括号匹配的错误的情况（详情参考图2.4 程序流程图2）。主函数用来调用这两个方法。如图所示：主函数调用Comp（）调用GetCount（）结束图2.4 程序流程图1GetCount（）方法用来判断输入的字符串是否为正确的括号匹配序列。通过出栈与进栈的循环来判定为左括号多余或者是右括号多余。循环流程图如下：输入字符串为左括号？否是为右括号且匹配？左括号进栈是左括号出栈指向下一个字符图2.4 程序流程图23 程序清单#include#include#include#include#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立栈的首节点typedef structSElemType *base; /在栈构造前和销毁后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/构造一个空栈Sint InitStack(SqStack &S)S.base=(SElemType * )malloc(sizeof(SElemType);if(!S.base)exit(0); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;/若栈S为空栈，则返回TRUE，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置为空栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base; /销毁栈S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素个数，即栈的长度int StackLength(SqStack S)return S.stacksize;/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e为新的栈顶元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判断是否栈满，是则追加存储空间S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return 1; /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERRORStatus Pop(SqStack &S,SElemType &e)if(StackEmpty(S)=1)return 0;elsee=*-S.top;return 1;/括号匹配int Comp(char a,char b)if(a=(&b!=)|(a=&b!=)|(a=&b!=)return 0;else return 1;Status GetCount(SqStack *S)char eSTACK_INIT_SIZE;char e1;int i=0;InitStack(*S);printf(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括号匹配错误); exit(0);for(i=0;ei!=0;i+)/以/0判断输入是否结束switch(ei)case (:case :case :Push(*S,ei);break;case ):case :case : GetTop(*S,e1); if(GetTop(*S,e1)=0) printf(右括号多余); exit(0); if(Comp(e1,ei)=1) Pop(*S,e1); /S-top-; else printf(括号匹配错误n); exit(0);if(S-top!=S-base)printf(左括号多余n);else printf(括号匹配正确n);return 0;/主函数void main()SqStack S;InitStack(S);GetCount(&S);4 测试4.1 测试数据（1）左括号多余。（2）右括号多余。（3）匹配正确4.2 测试结果分析（1）错误的情况之一是左括号多余，例如 ( )就是一个简单的左括号多余情况，输出之后的结果如图：图4.2-1 左括号多余（2）错误的情况之二是右括号多余，例如( ) 就是一个简单的右括号多余情况，输出之后的结果如图：图4.2-2 右括号多余（3）匹配正确的有很多种情况。举例一种 ( ) 就是正确的括号匹配情况，输出之后的结果如图：图4.2-3 括号匹配正确5 总结通过这次的数据结构课程设计实验周,我进一步理解了顺序堆栈的构造极其逻辑结构定义，并一定程度上掌握顺序堆栈的基本操作算法。书本上对顺序堆栈的基本算法介绍的比较详尽，但由于我对这方面的知识了解真的不深，而且之前C 语言的基础没有打好，程序设计过程中遇到不少难题，通过和直到老师、同学们的沟通，并上网查了些资料，问题终于得到一定程度上的解决。 这一次程序设计实验周中我受益匪浅，掌握到了顺序堆栈的基本算法。所学到的知识得到了很好的复习并巩固。我认识到数据结构是实践很强的一门课程，光是“听”和“读”是绝对不够的，必须加强实践。6参考文献1.严蔚敏，吴伟民编著，数据结构（C语言版），清华大学出版社，2005 2 严蔚敏，陈文博编著，数据结构及应用算法教程，清华大学出版社，2006 3 李云清，杨庆红，揭安全编著，数据结构（C语言版），人民邮电出版社2006 4 谭浩强，张基温，唐永炎编著，C语言程序设计教程（第二版）高等教育出版社，2005 5 苏仕华等编著，数据结构课程设计，上海；机械工业出版社，2004#include#include#include#include#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立栈的首节点typedef structSElemType *base; /在栈构造前和销毁后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/构造一个空栈Sint InitStack(SqStack &S)S.base=(SElemType * )malloc(sizeof(SElemType);if(!S.base)exit(0); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;/若栈S为空栈，则返回TRUE，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置为空栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base; /销毁栈S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素个数，即栈的长度int StackLength(SqStack S)return S.stacksize;/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e为新的栈顶元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判断是否栈满，是则追加存储空间S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return