括号配对的程序设计与实现1.docx

《括号配对的程序设计与实现1.docx》由会员分享，可在线阅读，更多相关《括号配对的程序设计与实现1.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告括号配对的程序设计与实现2014年12月29日(5) Pop(SeqStack *S,StackElementType *x) 将栈 S 的栈顶元素弹出放 到X所指的存储空间中GetTop(SeqStack *S,StackElementType *x)将栈 S 的栈顶元素弹 出放到X所指的存储空间中 但栈顶指针保持不变(6) Match(char ch,char str) 进行括号的匹配BracketMatch(char *str)str口中为输入的字符串 利用堆栈技术来检查该字符串中的括号是否匹配二、核心代码判断括号是否匹配：str口中为输入的字符

2、串，利用堆栈技术来检查该字符 串中的括号是否匹配，使用for循环对字符串中的字符逐一扫描，用Match判 断两个括号是否匹配，己匹配的左括号出栈，如果不匹配输出其结果结束；假设 匹配，那么输出匹配。void BracketMatch(char *str)(SeqStack S;int i;char ch;lnitStack(&S);for(i=0; stri!=O,; i+) switch(stri) casecase T：casePush(&S,stri);break;casecase T：caseif(lsEmpty(&S)printf(n 右括号多余!n);return; else (G

3、etTop(&S,&ch);if(Match(ch,stri)Pop(&S,&ch);else printf(n对应的左右括号不同类!n);return;/*switch*/*for*/if(lsEmpty(&S)pnntf(n 括号匹配!n);else printf(n 左括号多余!n“);3程序清单#defineTRUE 1#define FALSE 0#define Stack_Size 50#define StackElementType charinclude stdio.htypedef struct(StackElementType elemStack_Size;int top;

4、SeqStack;void lnitStack(SeqStack *S)(S-top = -1;)int lsEmpty(SeqStack *S)(return(S-top=-l?TRUE:FALSE);int lsFull(SeqStack *S)(return(S-top=Stack_Size-l?TRUE:FALSE);int Push(SeqStack *S,StackElementType x)(if(S-top=Stack_Size-l) return(FALSE);S-top+;S-elemS-top = x;return(TRUE);int Pop(SeqStack *S,St

5、ackElementType *x)(if(S-top = -1)return(FALSE);else *x = S-elemS-top;S-top-;return(TRUE); int GetTop(SeqStack *S,StackElementType *x) (if(S-top = -1)return(FALSE);else *x = S-elemS-top;return(TRUE);)int Match(char ch,char str) (if(ch=( & str=T) return TRUE; else if(ch= & str=T) return TRUE; else if(

6、ch= & str=) return TRUE; else return FALSE;)void BracketMatch(char *str)(SeqStack S;int i;char ch;lnitStack(&S);for(i=0; stri!=O; i+) switch(stri) casecase T： casePush(&S,stri);break;case ) case case if(lsEmpty(&S) (printf(n 右括号多余!n“);return; else ( GetTop(&S,&ch); if(Match(ch,stri) Pop(&S,&ch); els

7、e printf(n对应的左右括号不同类!n“); return;)/*switch*/ /*for*/if(lsEmpty(&S)printf(n 括号匹配!n“);else printf(n 左括号多余!n“); void main() 10*括号匹配的检验printf(n);printf(”请输入算数表达式:);gets(str);BracketMatch(str);printf(谢谢使用!n“);11char str100; printf(4测试4.1 测试数据(1) a* (b+c) * (b-d) =(2) a* (b+c)*(b-d)二4. 2测试结果分析输入的表达式为：a*(b

8、+c)*(b-d)二，图4-1为程序运行后的表达式中括号匹 配正确的结果，表达式正确；图4-1输入的表达式为：a*(b+c)*(b-d)二，图4-2为程序运行后的表达式中括号的左括号多余的结果，即括号匹配错误，表达式有错误;图4-2125总结这次课程设计是运用C语言以及这学期所学习的数据结构完成的。数据结构 是有某一数据元素的集合和该集合中的数据元素之间的关系组成。我做的课题 是：编一个程序判断括号是否匹配。通过这次的编程实训，让我受益较多，更进一步的了解和掌握顺序栈的类型 定义方法，顺序栈的操作和应用以及栈先进后出操作原那么在解决实际问题中的应 用；也认识到了自己在数据结构方面的漏缺之处，同

9、时也增强了自我学习的能力, 相信我通过这次的实训可以让我在以后更好的学习编程！13参考文献严蔚敏等.数据结构（C语言版）清华大学出版社朱战立.数据结构一使用C语言（第四版）.电子工业出版社吴跃.数据结构和算法.机械工业出版社周海英等.数据结构与算法设计（第二版）.国际工业出版社14题目括号配对的程序设计与实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答以下问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照

10、规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语：日期：年 月日1课程设计目标与任务11.1课程设计目标11. 2课程设计任务11.3课程设计内容12分析与设计22.1题目分析22. 2存储结构设计32. 3算法描述32.4程序流程图42.5测试程序说明63程序清单94测试124.1测试数据124. 2测试结果分析125总结13参考文献141课程设计目标与任务1.1课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面 得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法 及上机操作方面受到比拟系统严格的训

11、练，培养软件工作所需要的动手能力。1. 2课程设计任务数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计 基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作 方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，

12、分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。 1.3课程设计内容（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号, 这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是 否正确配对。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计2.1题目分析假设

13、表达式中允许包括三种括号：圆括号、方括号和花括号，其嵌套的顺序 随意，即()或()等为正确的格式，()或()或()均为不正确 的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例 如考虑以下括号序列：()2 3 4 5 6 7 8当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然 而等来的却是第二个括号，此时第一个括号只能靠边，而迫切等待与第二 个括号相匹配的、第七个括号“)”的出现，类似地，因等来的是第三个括号“”， 其期待匹配的程度较第二个括号更急迫，那么第二个括号也只能靠边，让位于第三 个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号

14、之 后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前 最急迫的任务了，.，依次类推。可见这个处理过程恰与栈的特点相吻合。在算术表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点。因此首先建立一个空的堆栈，依次读入字符直到文件的末尾。我们可以利用 一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验 匹配情况。输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号, 这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是 否正确配对。算术表达式中各种括号的使用规那么为：出现左括号，必有相应的右

15、括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。否那么，括号 匹配不正确，那么该算数表达式无效；程序结束。2. 2存储结构设计本程序用的是顺序栈，用地址连续的存储空间依次存储栈在中的元素，并记 录当前栈顶数据元素的位置，这样的栈称为顺序栈。同顺序表的存储结构类似， 顺序栈也可以用向量来实现。由于入栈和出栈运算都是在栈顶进行的，而栈底位 置是固定不变的，可以将栈底位置设置在向量的起始处；栈顶位置是随入栈和出 栈操作而变化的，故需要用一个整型变量TOP来记录当前栈顶元素在向量中的 为何子。类似顺序表的类型定义，顺序栈的类型可定义如下：typedef structStackElement

16、Type elemStack_Size;int top;SeqStack;2. 3算法描述首先建立一个空的堆栈，依次读入字符直到文件的末尾。在算术表达式中， 右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆 栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有以下4种情况：(1)括号匹配不正确左括号多于右括号；右括号多于左括号；左右括号配对次序不正确；(2)左右括号配对正确；具体方法如下：顺序扫描算术表达式，假设该表达式中无括号时，那么为空栈， 此时结束。当遇到3种类型括号的左括号时，让该括号进栈。当扫描到某一种类 型的右括号时，比拟当前栈顶括号是否与之匹配，假设匹配

17、，那么退栈继续进行判断; 假设当前栈顶括号与当前扫描的括号不相同，那么左、右括号配对次序不正确；假设字 符串当前为某种类型右括号而堆栈已空，那么右括号多于左括号；字符串循环扫描 结束时，假设堆栈非空，那么说明左括号多于右括号；以上三种情况均为括号匹配不 正确，那么输出不匹配括号的位置。如果上述三种情况都没有出现，那么说明左、右 括号匹配正确。2. 4程序流程图运行程序，用键盘输入算是表达式，判断读入的字符是否为括号，假设不是括 号，那么不入栈继续读取；假设是括号，那么入栈，在判断该括号是左还是右括号，假设 是左括号那么等待下一个括号的读入，如果读入的下一个括号是右括号，判断该右 括号是否与上一

18、个左括号匹配，假设匹配，那么栈顶元素出栈，继续读取，假设不匹配, 那么输出错误；如果读入的下一个括号为左括号，那么入栈成为栈顶元素；重复该步 骤。读取完结束后，判断栈是否为空，如果为栈空，那么该表达式书写正确，括号 完全匹配正确；如果栈非空，那么表达式无效，括号匹配不正确。开始结束图2-22. 5测试程序说明一、算法用到的抽象数据类型定义1、ADT Stack数据对象 D=ai|aiElemSet,i=L2 n, n20数据关系Rl=| ai-l,ai G D,i=2, ,)约定an端为栈顶al端为栈底基本操作：(1) lnitStack(&S)操作结果构造一个空栈S。(2) StackEmp

19、ty(S)初始条件栈S已存在。操作结果 假设栈S为空栈 那么返回TURE 否那么FALUSE。(3) StackFull 初始条件栈S已存在。操作结果 假设栈S为满 那么返回TURE,否那么FALUSE.(4) GetTop(S,&e)初始条件栈S已存在且非空。操作结果 用e返回S的栈顶元素。(5) Push(&S,e)初始条件栈S已存在。操作结果 插入元素e为新的栈顶元素。(6) Pop(&S,&e)初始条件栈S已存在且非空。操作结果删除S的栈顶元素算法中函数编号及功能要求：(1) voidlnitStack(SeqStack*S)初始化构造一个空栈 SlsEmpty(SeqStack *S)判断栈S为空栈时返回值为真 反之为假(2) lsFull(SeqStack *S)判断栈S为满栈时返回值为真 反之为假Push(SeqStack *S,StackElementType x)插入元素 x 为新的栈顶元素