括号匹配程序设计.docx

《括号匹配程序设计.docx》由会员分享，可在线阅读，更多相关《括号匹配程序设计.docx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、河南工程学院数据结构与算法课程设计成果报告括号匹配程序设计2014年12月29日3程序清单#include#include#include#include#define STACKNIT_SIZE 100存储空间初始分配量#define STACKINCREMENT 10typedef char Status;typedef char SEIemType;建立栈的首节点typedef structSEIemType *base; 在栈构造前和销毁后，base的值为NULLSEIemType *top; 栈顶指针int stacksize;当前已分配的存储空间，以元素为单位JSqStack;构造

2、一个空栈Sint lnitStack(SqStack &S)S.base=(SEIemType * )malloc(sizeof(SEIemType);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的元素个数，即栈的长度int StackLength(SqStack S)return S.stacksi

3、ze;)假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERROR int GetTop(SqStack S,SEIemType &e)if(S.top=S.base)return 0;e=*(S.top-l);return 1;)插入元素e为新的栈顶元素Status Push(SqStack &S,SEIemType &e)1昭1：(6七3$0=53130)判断是否栈满,是那么追加存储空间S.base=(SEIemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SEIemType);if(!S.base)e

4、xit(O);S.top=S.base+S.stacksize;S.stacksize+二 STACKINCREMENT;*S,top+ =e;return 1;假设栈不空，那么删除s的栈顶元素，用e返回其值，并返回0K,否那么返回ERRORStatus Pop(SqStack &S,S曰emType &e)if(StackEmpty(S)=l)return 0;elsee=*-S.top;return 1;)括号匹配int Comp(char a,char b)if(a=,(&b!=T) | | (a=,&b!=T) I I (a=&b!=)return 0;else return 1;)/

5、Status GetCount(SqStack *S) chareSTACK_INIT_SIZE;char el;int i=0;lnitStack(*S);printf(Please enter a string of parenthesis:);gets(e);if(e0=y)|(e0=T)|(e0=)printf(括号匹配错误)；exit(0);for(i=0;ei!=0;i+)以“/O” 判断输入是否结束 switch(ei)casecase 1:casePush(*S,ei);break;)case )case T：caseGetTop(*S,el);if(GetTop(*S,el)

6、=0)printfC1右括号多余)； exit(O);)if(Comp(el,ei)=l)Pop(*S/el);/S-top-;)else printf。1括号匹配错误n”)； exit(O);)if(S-top!= S-base)printf(左括号多余n);else printf(括号匹配正确n)；return 0;主函数void main()SqStack S;InitStack(S);GetCount(&S);)4测试4.1测试数据测试数据分别为：()；()；()；()；().依次对应为匹配正确，括号匹配 错误，左括号多余和右括号多余的情况。4. 2测试结果分析(1)以下为输入正确括号

7、序列时的运行结果图，测试数据分别为 ()/()：cT *F:bghDebugbgh.exe*情输入一串括号: 聘等匹配正确情输入一串括号: 聘等匹配正确Press any key to continue图2.57:括号匹配正确cT *F:bghDebugbgh. exe*入一串括号：入一串括号：逋转入：二括鲁匹配正确Press any key to continue图2.5-2：括号匹配正确(2)以下为出现匹配错误时的运行结果,测试数据为)：c： F: bghDebugbgh. exe*适前入一患循号：tress any key to continue图2.5-3:括号匹配错误(3)以下为出现

8、左括号多余时的运行结果，测试数据为卜图2. 5-4:左括号多出图2. 5-4:左括号多出10(4)以下为出现右括号多余时的运行结果，测试数据为“()”：图2.5-5:右括号多出(5)下面为本程序的一个漏洞，即为没有判断输入的是否为括号，如果在输入 非括号的情况下，程序并不能给出正确的反应，依然按照正常的括号匹配模式进 行。请输入一串括号：1234 括号匹配定碉Press any key to continue图2. 5-6:输入格式异常在这里分析解决方案为，在读入字符前再添加一个判定函数，判断他是否为左括 号或者右括号，假设都不是那么提示异常，加入以下函数int pd(char a) retu

9、rn 1;)调试后运行结果为：Press any key to continue图2.5-6:异常解决115总结通过这次的课程设计，学会了好以前不太懂的知识。在进行算法设计以及 功能实现的过程中，不仅复习到了书本中学习的知识，同时也另外学习了很多新 的知识。并且在修改一个个程序bug时，也逐渐规范了编程习惯，了解了一些常 见错误的解决方法。实践出真知，这些在实践中学到的东西定会让我以后的编程 轻松更多。把握每一次学习的机会，珍惜每一次的实践设计，现在多犯错，才会 在以后走的更顺，更远。121.2.3.4.5.参考文献数据结构（C语言版）严蔚敏 清华大学出版社2002数据结构-C语言描述王路群数

10、据结构实验教程（C语言版）数据结构题集严蔚敏，吴伟民编C程序设计（第四版）谭浩强13中国水利水电出版社2007王国钧清华大学出版社2009清华大学出版社2002清华大学出版社2002题目括号匹配程序设计考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答以下问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程

11、设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程实际基本要求11.4 课程设计形式12分析与设计22.1题目需求分析22. 2存储结构设计22. 3算法描述32.4程序流程图63程序清单74测试104.1测试数据104. 2测试结果分析105总结12参考文献131课程设计目标与任务1.1课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与现面得到 训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上 机操作方面受到比拟系统严格的训练，培养软件工作所需要的动手能力。1. 2课程设计任务（1）输入一个算术表达式，式中包含三种括号：圆括号、

12、方括号和花括号, 这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是 否正确配对。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1. 3课程实际基本要求严格按照题意要求，独立进行设计，不能随意更改。假设确因条件所限，必须 要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作 计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设 计报告，做好设计总结。1. 4课程设计形式校内机房实习，上机编码。2分

13、析与设计由题意分析，假设表达式允许包含两种括号：圆括号和分括号，其嵌套的顺 序随意，即(口()或者()等为正确的格式，或者()均为不正确的格式。检验 括号是否匹配的方法可用“期待的击破程度”这个概念来述。2. 1题目需求分析例如考虑到以下括号序列：()当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现， 然而等来的却是第二个括号，此时第一个括号“只能暂时靠边，而迫切等待 与第二个括号向匹配的，第七个括号”)”的出现，类似的，因等来的是第三个 括号“【”，与其期待匹配的程度较第二个括号更急切，那么第二个括号只能靠边, 让位于第三个括号，显然第二个括号的期待急迫程度高于第一个括号；在接

14、受了 第四个括号之后，第三个括号的期待程度得到满足，消解之后，第二个括号的期 待匹配就成为当前最急迫的任务了以此类推，可见，这个处理过程恰巧与栈 的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，假设是右括号，那么或者使置 于栈顶的最急迫的期待得以消解，或者不合法的情况；假设读入左括号，那么作为一 个更急迫的期待压入栈中，作为栈顶，自然使原有的在栈中的所有未消解的急迫 性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。2. 2存储结构设计根据题目需求，此题需设计一个顺序栈的存储结构，即利用一组地址连续的 存储单元依此存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在 顺

15、序栈中的位置。在初始化设空栈时不限定栈的最大容量。现设定两个常量:STACKNIT_SIZE(存储空间分配量)和STACKINCREMENT (存 储空间分配增量)，并以下述类型说明作为顺序栈的定义：typedef char SEIemType;建立栈的首节点typedef structSEIemType *base; 在栈构造前和销毁后，base的值为NULLSEIemType *top; 栈顶指针int stacksize;当前已分配的存储空间，以元素为单位SqStack;其中stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定 的初始化量进行第一次存储分配，base可

16、成为栈底指针，在顺序栈中，它始终 指向栈底的位置，假设base的值为NULL,那么说明栈结构不存在。称top为栈顶指 针，其初值指向栈底，即top=base可作为栈空的标志，每当插入新的栈顶元素 时，指针top增1；删除栈顶元素时，指针top减1,因此，非空栈中的栈顶指 针始终在栈顶元素的下一个位置上。以下图展示了顺序栈中数据元素和栈顶指针之间的对应关系:图2.2-2：栈顶指针和栈中元素关系示意图2. 3算法描述完整的顺序栈包含很多的函数，不过根据此题的需要，只写出以下几个操作 函数：(1)构造一个空栈sint lnitStack(SqStack &S)(2)判断栈是否为空栈，假设栈S为空栈，

17、那么返回TRUE,否那么返回FALSE, 这里把top=base作为栈空的标记。int StackEmpty(SqStack S)(3)返回S的元素个数，即栈的长度int StackLength(SqStack S)(4)假设栈不空，那么用e返回S的栈顶元素，并返回0K；否那么返回ERROR, 此函数用来获得栈顶元素来判断是否与读入的右括号相匹配。int GetTop(SqStack S,SEIemType &e)(5)插入元素e为新的栈顶元素，此题中只有左括号进栈，右括号不进栈。Status Push(SqStack &S,S曰emType &e)(6)假设栈不空，那么删除S的栈顶元素，用e

18、返回其值，并返回0K,否那么返 回ERROR；此函数返回的栈顶元素(即一个左括号)假设与读入的右括号匹配，那么 使下个元素成为最急迫的期待置于栈顶。Status Pop(SqStack &S,S日emType &e)(7)括号匹配，此函数包含两个字符变量，a代表的是左括号，b代表的是 右括号，通过判断a对应的左括号与b对应的右括号是否匹配，来完成判断。int Comp(char a,char b)(8)此函数是针对括号匹配中的几种错误，依赖上面的comp ()函数判断, 在窗体中返回不同的内容，大致的错误分为一下三种：匹配错误：即左右括号个数相等但不相匹配。左括号多余右括号多余Status G

19、etCount(SqStack *S)(9)此函数用来判断输入的字符串是否为括号。假设不是括号，那么提示异常。int pd(char a)if(a!= ()&(a!=)&(a!= )&(a!=)&(a!= )&(a!=)return 1;2.4程序流程图程序有两个模块，一个模块存储括号配对的正确情况，Comp ()方法用来 判断括号配对的正确情况(详情参考图2.4程序流程图2)如左右括号多出等。 GetCount ()用来判断括号匹配的错误的情况(详情参考图2.4程序流程图2)。 主函数用来调用这两个方法。如下图：调用Comp ()调用 GetCount ()结束图2.4程序流程图1GetCount ()方法用来判断输入的字符串是否为正确的括号匹配序列。通过 出栈与进栈的循环来判定为左括号多余或者是右括号多余。循环流程图如下：图2.4程序流程图2