括号匹配算法设计的实现1.docx

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

1、河南工程学院数据结构与算法课程设计成果报告括号匹配算法设计的实现break;case:if(Pop(s) !=)return 0;break;case：if(Pop(s)!=,)return 0;break;)int re=0; /定义并初始化判空函数的返回值re=Empty(s,re); 返回判空函数的返回值if(re=l)return 1; 栈为空elsereturn 0; /栈不为空，有左括号，即存在(或T或T未匹配)void main() 主函数(char str 100; 定义一个单字符型数组以储存键盘输入的字符串。cout请您输入一个长度小于的字符串：endl;cinstr;从键盘

2、输入字符存储到字符数组中，有输入那么继续。int re=Check(str);if (re= 1)coutvv您输入的字符串中的括号完全匹配！ endl;else if (re=0)cout 您输入的字符串中的括号不匹配！ endl;4测试4.1测试数据算法设计完成后，输入几组表达式进行测试。输入表达式 2x+6y-3y+2z*4z+(45-2x)*13-32.运行结果如图 4. 1。S3 3 E:Microsoft Visual StudioMyProjectslyDebugly.exe青您输入一个长度小于的字符串：2x+6y-3y+2z*4z+*1332电输入的字符串中的括号完全匹配！Pr

3、ess any key to continue图4.1表达式。的运行结果输入表达式2x+3y+3y-4z)+4z-2y-(2x-3z)*5+2z,运行结果如图 4. 2。S3 3 E:Microsoft Visual StudioMyProjectslyDebugly.exe靖您输入一个长度小于的字符串： 2x+ +4z2y 3_*5 -2n 摩输入的字符串中的括号不匹配！ pi*ess any key to continue图4.2表达式的运行结果输入表达式65+x*z- (x+y/z+78*2,运行结果如图4. 3。 3 E:Microsoft Visual StudioMyProject

4、slyDebugly.exe请您输入一个长度小于的字符串: 65+x*z-*2 国输入的字符串中的括号不匹配!Press any key to continue图4. 3表达式的运行结果4. 2测试结果及分析第一个表达式中左括号和右括号相互匹配，所以显示您输入的字符串中的括 号完全匹配。第二个表达式括号类型不匹配，即“”和“)”不匹配，所以显示您输入 的字符串中的括号不匹配。第三个表达式中括号个数不匹配，即缺少一个“)”，所以显示您输入的的 字符串的括号不匹配。5总结通过一个星期的上机实训，我发现了自己的很多缺乏之处。我做的题目是括 号匹配的算法设计。题目很简单，但是我却花了一个星期仍然没有自

5、己想象中做 的成功。期间老师不断地给予指导，我也在改进过程中不断地学习。我感觉要想 做好编程，不仅需要丰富的理论知识，还要有定期的上机实践。只凭自己的一点 书上学到的理论就想熟练的编程序是几乎不可能的。在以后的学习中，还要不断 地加强自己的上机实践能力。10参考文献1朱战立.数据结构一使用C语言（第四版）电子工业出版社2009周海英.马巧梅数据结构与算法设计（第二版）国际工业出版社20053吴跃.数据结构和算法机械工业出版社2010严蔚敏.吴伟民数据结构：C语言版清华大学出版社200711题目括号匹配算法设计的实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本

6、操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1 课程设计目标11.2 课程设计内容及要求11. 3课程设计思想12分析与设计22.1题目设计分析22. 2概要设计和数据结构的选择22. 3算法描述32.4程序流程图43程序清单54测试84.1测试数据84. 2测试结果及分析95总结101课程设计目标与任务

7、1.1 课程设计目标通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈 先进后出的特点，掌握栈的表示和实现。通过本课程设计，提高在数据结构的选 择和应用、算法的设计与实现等方面的能力。加深对数据结构基本内容的理解和 灵活应用，同时，培养软件工作所需要的动手能力。在程序设计方法及上机操作 方面得到比拟严格的全面的锻炼。1.2 课程设计内容及要求输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三 种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正 确配对。最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形 方式显示出来，将复杂的运行过

8、程以动态方式显示出来。给出假设干例程，演示通 过调用自己所缩写程序来实现相关问题的求解。1. 3课程设计思想匹配思想：从左至右扫描一个字符串（或表达式），那么每个右括号将与最近遇到 的那个左括号相匹配。那么可以在从左至右扫描过程中把所遇到的左括号存放到堆栈 中。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈 顶删除该左括号。算法思想：设置一个栈，利用栈来判断括号是否匹配时，遇到左 括号就进栈，遇到右括号那么左括号出栈，代表这对括号匹配，如果右括号进栈时， 栈为空，那么说明缺少左括号，假设表达式扫描完栈为空，那么说明表达式的括号匹配，否 那么说明表达式缺少左括号。最内层（

9、最迟出现）的左括号必须与最内层（最早出现） 的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为 左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法 的开始和结束时，栈都应该是空的。例如：（）、（）、（2分析与设计2.1题目设计分析设计一个程序可以判断给定表达式中所含的括号是否正确配对出现。给定表 达式可包含：圆括号，方括号和花括号这三种括号。本程序用C+编写，完成圆 括号、方括号和大括号(选作)的匹配检验，即当输入一串括号后能够判断出此 串括号匹配是否合法。一、输入形式和输入范围括号以字符串形式输入，只输入圆括号、方括号和大括号三种括号，三种括 号可以随

10、意嵌套。二、输出形式及功能当输入任意一字符串后，都会做出判断，输出输入的括号串是否合法。三、测试数据输入(),结果“匹配”输入()，结果此串括号匹不合法。2. 2概要设计和数据结构的选择一、概要设计(1)定义抽象数据类型存储编号、密码指针：using namespace std;#define stacksize 100 定义栈的空间大小struct stack /定义栈的结构体char strstackstacksize;定义栈的存储格式为字符型int top; ; 定义栈的栈顶变量(2)程序流程：在屏幕上显示：“请您输入一个字符串”。输入一串字符串(表达式)。进行get ()操作。进行br

11、acket ()操作。输出结果，是否匹配。二、数据结构的选择此题目设计选择的数据结构为栈。因为栈的特点是先进后出，使用栈使括号 匹配问题简易化。多项式中的括号对数是成对出现的，可以将它抽象为一个对称 的字符串，字符串的前一半看做连续出现的左括号字符，后一半看做连续出现的 右括号字符，与栈顶元素比拟，假设匹配那么栈顶指针下移，即删除栈顶元素，继续 比拟。当栈内元素为空时，说明左右的左括号与右括号匹配，那么匹配成功。2. 3算法描述括号匹配问题是指要匹配一个字符串的左，右括号。括号问题可以用来解决 c语言中的“”和“的匹配问题，可以观察到，如果从左至右扫描一个字符 串，那么每个右括号将于最近遇到的

12、那个未匹配的左括号相匹配，在从左至右的 扫描工程中把所遇到的左括号存放到堆栈内，每当遇到一个右括号时，就将它与 栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。即假设一个算术 表达式可以包含3种括号：圆括号“（”和“）”，方括号和花括 号“ ”和“且这三种括号可按照任意次序嵌套使用（如：，和 （”） O设计一个程序，判别所给定表达式中所含括号是否匹配。在任意个 表达式中，判断括号类型及其对数是否匹配。可以将表达式看做一个字符串，当 此字符串为左括号时，将其入栈，当此字符串为右括号时，与栈顶元素比拟，假设 不匹配那么显示失败，假设匹配，循环比拟个字符与栈内元素是否匹配，直到栈为空 且括号

13、对数及类型相同，那么该表达式的括号匹配，否那么匹配失败。2. 4程序流程图流程图如图2.1所示。对括号出现的情况进行判断，如果是、口（那么元素 进栈，如果是、）那么与出栈元素进行比拟。继续匹配，直到读完。假设不匹配 那么进行标示，最后输出结果。开始输入字符串图2.1括号匹配算法设计流程图3程序清单#includeHstdafx.hn#include#include#includeusing namespace std;#define stacksize 100定义栈的空间大小struct stack /定义栈的结构体char strstackstacksize，定义栈的存储格式为字符型 int

14、 top; /定义栈的栈顶变量)；void InitStack(stack &s) 定义一个新栈s,初始化栈顶为-1 s.top = -1;char Push(stack &s, char a) 入栈操作，将字符 a 入栈 s if(s.top = stacksize - 1) /当栈顶为栈的空间大小-1,栈满 return 0;s.top+；入栈操作一次，栈顶+1s.strstacks.top = a;此时，栈顶元素为字符a return a;)char Pop(stack &s ) 出栈操作if(s.top - -1) 当栈顶为-1时: 栈空return 0;char a = $版双15到

15、);/将栈顶元素赋予字符a,并返回字符a,完成出栈 操作s.top-;return a;)int Empty(stack &s,int re) 定义判断栈是否为空的函数if(s.top-l)return 1;/栈为空时返回值为1elsereturn 0; 栈不为空时返回值为0)int Check(char* str) 检验括号是否匹配的函数stack s;InitStack(s);int strn = strlen(str); 定义字符串长度为 strnfor(int i=0;istm;i+)char a=stri;switch (a)对输入的字符a进行判断case，：case,：case：Push(s,a);假设是左括号，那么进行入栈操作break;/假设是右括号，那么进行出栈操作，假设出栈元素不是与输入相对应的 左括号，那么字符串括号中不匹配，返回case):if（Pop（s）!二greturn 0;