1、 课课 程程 设设 计计 课程名称 数据结构 题目名称 括号匹配 2010 年 12 月 27 日 课程设计（论文）任务书课程设计（论文）任务书 一、课程设计（论文）的内容 括号匹配问题，假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编 写一个函数，用来判别表达式中括号是否正确配对。 二、课程设计（论文）的要求与数据 要求当输入一表达式，可判断并输出括号是否匹配。 三、课程设计（论文）应完成的工作 （1）根据上述要求完成一个功能完善的程序； （2）采用模块化的程序设计方法，程序书写符合规范，程序设计应完善； （3）对系统进行初步的错误和漏洞检测； （4）根据设计规范撰写报告并按
2、时提交； （5）设计内容用A4纸打印并按要求装订。 题目名称 括号匹配 学生学部（系） 信息与计算机学部 专业班级 09 计算机 2 班 姓 名 XX 学 号 110109020XX 四、课程设计（论文）进程安排 序号 设计（论文）各阶段内容 地点 起止日期 1 搜集资料 图书馆 11.24-11.26 2 需求分析 图书馆 11.27-11.30 3 系统分析与设计 图书馆 12.1-12.4 4 功能模块的实现 综 702 机房 12.5-12.15 5 系统测试，运行 综 702 机房 12.16-12.19 6 完成课程设计（论文） 综 702 机房 12.20-12.27 五、应收集
3、的资料及主要参考文献 【1】 周海英.马巧梅.数据结构与算法设计（第二版）.国际工业出版社 2005 【2】 朱战立.数据结构-使用 C 语言（第四版）.电子工业出版社 2009 【3】 吴跃. 数据结构和算法.机械工业出版社 2010 发出任务书日发出任务书日期：期： 2010 2010 年年 11 11 月月 23 23 日日 指导教师签名：指导教师签名： 计划完成日期：计划完成日期： 2010 2010 年年 12 12 月月 27 27 日日 教学单位责任人签章：教学单位责任人签章： 目录目录 1 设计内容设计内容.1 2 算法思想描述算法思想描述 1 3 算法及程序实现算法及程序实现
4、 . 2 4 算法测试及结果算法测试及结果 4 5 总结总结.8 参考资料参考资料.9 设计内容：设计内容：括号匹配问题，假设一个算术表达式中包含圆括号、方括号和花 括号三种类型的括号，编写一个函数，用来判别表达式中括号是否正确配对。 算法要求算法要求：要求当输入一表达式，可判断并输出括号是否匹配。 算法思想算法思想 在算术表达式中， 右括号和左括号匹配的次序正好符合后到的括号要最先被 匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。 括号匹配共有以下括号匹配共有以下 4 4 种情况种情况： 左右括号配对次序不正确； 右括号多于左括号； 左括号多于右括号； 左右括号配对正确；
5、具体方法如下：顺序扫描算术表达式，当遇到 3 种类型括号的左括号时，让该括 号进栈。当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若 匹配，则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左、 右括号配对次序不正确；若字符串当前为某种类型右括号而堆栈已空，则右括号 多于左括号；字符串循环扫描结束时，若堆栈非空，则说明左括号多于右括号； 如果上述三种情况都没有出现，则说明左、右括号匹配正确。 算法以及程序实现算法以及程序实现 主主函数函数设计如下：设计如下： Void ExpIsCorrect(char exp,int n)/判断有 n 个字符的字符串 exp 左、右
6、括号是否配对正确 SeqStack myStack;/定义顺序堆栈变量 myStack int i; char c; StackInitiate( /初始化堆栈 for(i=0;itop = 0; /*定义初始栈顶下标值*/ int StackNotEmpty(SeqStack S) /*判顺序堆栈 S 非空否，非空则返回 1，否则返回 0*/ if(S.top top = MaxStackSize) printf(“堆栈已满无法插入! n“); return 0; else S-stackS-top = x; S-top +; return 1; int StackPop(SeqStack *S, DataType *d) /*弹出顺序堆栈 S 的栈顶数据元素值到参数 d ，出栈成功则返回 1，否则返回 0*/ if(S-top top -; *d = S-stackS-top; return 1;
