括号匹配实现《数据结构与算法》课程设计成果报告.doc

河南工程学院数据结构与算法课程设计成果报告括号匹配实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号匹配实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计目标11.2课程设计任务12 分析与设计22.1题目分析22.2存储结构设计22.3算法描述32.4程序流程图73 程序清单84 测试104.1测试数据10参考文献13附 录141 课程设计目标与任务1.1课程设计目标1.掌握栈的定义，表示方法及实现，理解栈结构的性质。2.通过本课程设计，使得在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2课程设计任务设计括号匹配的相关函数库，以便在程序设计中调用，要求：1.输入一个算数表达式，式中包含三种括号：圆括号、方括号、花括号。这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。2.最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；3.给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。 2 分析与设计2.1题目分析题中要求设计括号匹配的相关函数库，在程序执行中需要输入一个算数表达式通过调用括号匹配函数来判断给定的表达式中括号匹配是否正确。设计括号匹配函数可以用栈来实现，通过括号的进栈出栈以及对栈顶元素的判定来判断括号匹配是否正确。2.2存储结构设计1.对要输入的算数表达式定义一个字符串类型变量str来存储，并通过stri来读取表达式中的字符。cout请输入表达式str;int i=0;2.设计一个栈用来对字符串中的括号进行进栈出栈操作。class my_stackprivate: char data100;public: int top; my_stack() top=0; void push(char x) /压栈 datatop+=x; void pop() /出栈 top-; char frond_top() return datatop; ;2.3算法描述1.定义一个字符串类型的变量str用来储存算数表达式并通过stri来读取表达式中的字符。2.建立一个栈data，并给出压栈push()和出栈pop()的函数。3.从算数表达式的第一个字符开始。4.判断读取的字符是否为括号如果是括号：1.栈为空则让此字符入栈。2.栈不为空则判断读取的字符与栈顶元素是否为可以匹配的括号，如果不匹配让此字符入栈，如果匹配则对栈进行出战栈操作。然后读取算数表达式的下一个字符。若不是括号:直接读取算数表达式的下一个字符。5.重复步骤四。6.当表达式读取完之后对栈进行判断。若栈空则所有括号匹配完，即输入的表达式括号匹配形式正确，若栈非空，则括号没有匹配完，即输入的表达式括号匹配形式错误。首先设计一个栈，其中成员函数包括压栈出栈和访问栈顶元素。代码实现如下：class my_stackprivate: char data100;public: int top; my_stack() top=0; void push(char x) /压栈 datatop+=x; void pop() /出栈 top-; char frond_top() return datatop; ;my_stack S; /定义对象栈S定义一个字符串类型变量，将需要测试的算数表达式赋值给此变量。代码实现如下：cout请输入表达式str;将各括号赋值给不同变量，直接判断读取的表达式中的字符是否为括号，并通过变量间接对括号进行赋值来判断括号是否匹配。代码实现如下：char a=(,a1=),b=,b1=,c=,c1=; if(stri=a|a1|b|b1|c|c1) if(S.top=0) S.push(stri); else a=-1; a1=1; b=-2; b1=2; c=-3; c1=3; if(stri+S.frond_top()!=0) S.push(stri); else S.pop(); 对上程序进行循环，当对表达式所有字符读取结束时，循环结束 。代码实现如下：do char a=(,a1=),b=,b1=,c=,c1=; if(stri=a|a1|b|b1|c|c1) if(S.top=0) S.push(stri); else a=-1; a1=1; b=-2; b1=2; c=-3; c1=3; if(stri+S.frond_top()!=0) S.push(stri); else S.pop(); i+; while(i=str.length();循环结束后对栈顶元素进行判断，若栈顶元素为空则表达式括号匹配正确，否则表达式括号匹配错误。代码实现如下：if(S.top=0) cout输入的表达式正确endl; else cout输入的表达式有误endl; return 0;2.4程序流程图括号不匹配括号匹配stri入栈i+开始 i=0输入算数表达式str栈为空stri是括号stri出栈stri与栈顶元素匹配stri入栈i=length（）栈顶元素为空结束在程序中输入一个算数表达式，通过循环依次对表达式中的括号进行进栈出栈操作。表达式中字符判断完毕后通过判断栈是否为空得出给定的表达式中括号匹配是否正确。图2.4 括号匹配流程图3 程序清单#include #includeusing namespace std;class my_stackprivate: char data100;public: int top; my_stack() top=0; void push(char x) /压栈 datatop+=x; void pop() /出栈 top-; char frond_top() return datatop; ;my_stack S; /定义对象栈Sint main()cout请输入表达式str; int i=0; do char a=(,a1=),b=,b1=,c=,c1=; if(stri=a|a1|b|b1|c|c1) if(S.top=0) S.push(stri); else a=-1; a1=1; b=-2; b1=2; c=-3; c1=3; if(stri+S.frond_top()!=0) S.push(stri); else S.pop(); i+; while(i=str.length(); if(S.top=0) cout输入的表达式正确endl; else cout输入的表达式有误endl; return 0;4 测试4.1测试数据3*(4+7) 3*4-2*3+5）3+4-7)*(5-2)+13*(7-4)/2*(5+2)5-2*(3+4)/2-7+1*6+54.2测试结果分析检验输入的表达式中的括号是否匹配，将每个元素进栈出栈过程在调试中显示出来。方便观察，现在输入各种表达式及括号，每一个元素的读取，各个情况的判断和选择都一一表述出来并能正确判别其中括号是否匹配。例如测试的第一个表达式3*(4+7) :1.第一个字符3不是括号。读取下一个字符。2.*不是括号。接着读取下一个字符，3.是括号且现在栈为空让此大括号入栈。继续读取下一个字符，4.是括号，现在栈不为空，但是与不匹配所以让入栈。继续读取下一个字符。5.(是括号，此时栈不为空，但是(与栈顶元素不匹配所以让(入栈。继续读取下一个字符。6.4不是括号，读取下一个字符。7.+不是括号，读取下一个字符。8.7不是括号，读取下一个字符。9.)是括号，此时栈不为空，且)与栈顶元素(是匹配括号则让栈顶元素出栈。继续往下读取。10.是括号，此时栈不为空且与栈顶元素相匹配则让栈顶元素出栈。继续读取下一个字符。11.是括号，此时栈不为空，且与栈顶元素相匹配,则让栈顶元素出栈。12.此时表达式已经读取完，判断栈顶元素是否为空，显然此时栈已经为空。13.则得出结果所有括号刚好匹配完，表示式括号匹配形式正确。同理，对于其他表达式的判断也是如此进行。第二、三、五表达式括号形式匹配错误，第四个表达式括号匹配正确。5 总结这次课程设计是运用C+语言以及这学期所学习的数据结构的知识完成的。本实验，我做的检验括号匹配的问题。首先分析问题，理解题目意思。想出具体解决该问题的算法。通过栈的思想来解决问题。此次实验遇到困难不多，算法比较简单。通过一个数组和一个栈就可以解决问题了。只是在刚开始时，直接把判别式读入栈中，导致调试出现错误，一时无法解决，通过多次调试检得以解决。还有在该程序中遇到的问题是，将遇到的左括号压入栈中时，调用Push()函数时，它的顶部top值不变，还不清楚为什么，所以此程序没有写Push()函数，直接在检验函数中将括号压入栈中。通过本次实验，也了解到自己的语言知识还很匮乏，缺乏独立设计程序的能力，容易产生思维定式。在今后，一定要把语言学好，基础打牢，多进行实践，独立思考，取得进步。参考文献1谭浩强.C+面向对象程序设计.清华大学出版社2谭浩强.C