表达式的括号匹配检验问题课程设计报告.docVIP

合肥学院 计算机科学与技术系 课程设计报告 2008~2009学年第二学期 课程 数据结构与算法 课程设计名称 表达式的括号匹配检验问题 学生姓名 汤振兴 学号 0704032028 专业班级 07网络工程（2）班 指导教师 屠菁 张贯虹 2009年5月 题目：表达式的括号匹配检验问题。 试验完成如下要求：假设在表达式中允许有三种括号：圆括号、方括号和花括号，其嵌套的顺序是随意。要求设计测试数据，如果在表达式中括号使用正确，输出结果为“此表达式中括号匹配合法”，否则输出结果为“此表达式中括号匹配不合法”，#为表达式的起始和结束标志。在初始和结束时，栈为空。 问题分析和任务定义 此程序需要完成如下要求：表达式中允许有三种括号：圆括号、方括号和花括号，嵌套顺序随意。要求设计测试数据，判断表达式中括号使用是否正确，如果正确，输出结果为“此表达式中括号匹配合法”，否则输出结果为“此表达式中括号匹配不合法”，表达式的输出格式为：“#表达式#”。 实现本程序需要解决的几个问题： 用什么数据结构。 怎样实现判断括号是匹配的。 括号匹配与不匹配有几种情况。 输出与输入数据的形式。 本程序的难点在于怎么样判断括号是否匹配。 按任务书中的提示，首先，建立一个栈，用来存储读入的括号。若是左括号，则做为一个新的更急迫的期待压入栈，若是右括号，则和当前栈顶的括号比较，若匹配，则输出此表达式中括号匹配合法，若不匹配，则输出此表达式中括号匹配不合法。括号分为大括号，小括号，中括号，每个括号比较的方法是一样的。如输入为#(3+2)#: 输入#，输入（，“（” 输入3+2，输入 “）”，是右括， 是左括号，入栈 号“（”出栈，与“）”比较，匹 配，栈空 图1 具体实例演示括号匹配过程 由于本程序要求表达式的输入形式是#表达式#，#是表达式的起始与结束的标志，所以判断表达式遍历完的条件是读到第二个#号。 总的来说本题目是一个以栈为数据结构，设计一个求有关于表达式中括号匹配的问题的程序。数据类型应为字符型，需要自定义栈的结构体，初始栈，入栈，出栈，判断栈空的操作。 本程序用的是顺序栈，用地址连续的存储空间依次存储栈中的元素，并记录当前栈顶数据元素的位置，这样的栈称为顺序栈。同顺序表的存储结构类似，顺序栈也可以用向量来实现。由于入栈和出栈运算都是在栈顶进行，而栈底位置是固定不变的，可以将栈底位置设置在向量的起始处；栈顶位置是随入栈和出栈操作而变化的，故需要用一个整型变量TOP来记录当前栈顶元素在向量中的位置。类似顺序表的类型定义，顺序栈的类型可以定义如下： #define maxlen 100 Typedef struct { Datatype data[maxlen]; int top; } 通常，借助一个栈结构来检验某表达式中括号是否正确匹配。具体的方法是：设置一个栈，每读入一个左括号，则入栈，等待相匹配的同类右括号；如读入的是右括号，则与当前栈顶的左括号相比较，若是同类型括号，则两者匹配，将栈顶的左括号出栈，否则属于不匹配。另外，如果不再有读入的右括号，而栈中仍有等待匹配的左括号，或者是读入了一个右括号，而栈中已无等待匹配的左括号，均属于不匹配的情况。只有当输入序列和栈同时为空时，才说明所有的括号已完全匹配。 概要设计和数据结构选择 问题分析中和任务书中的提示都说了要用到栈，所以用栈这个数据结构。 图2 程序流程图 本程序包含6个函数： 主函数main() 初始化栈函数creatstack() 入栈函数push() 出栈函数pop() 判断栈空函数stackempty() 判断括号是否匹配函数bracket() 各函数之间的关系： 图3 函数间关系图 详细设计和编码 完成概要设计中定义的所有的数据类型，对每个操作给出算法。 自定义栈的结构体 typedef struct { char data[maxlen]; int top; } stack; 建空栈 让top=-1，即栈元素为空，建立空栈。 入栈操作 如果栈元素不满，则(s-top)++,需要入栈的元素入栈。这里要注意的是一定要判断栈中 元素是否满了，判断的方法是看s-top是否不等于maxlen-1，如果等于则栈满了，不能进行入栈操作，不等于则能入栈。 出栈操作 如果栈元素不为空，则要出栈的元素出栈，同时(s-top)--。和入栈操作一样，出栈操作 也要注意一个问题，那就是判断栈是否空了，判断方法看s-top是否等于-1，如果等于则栈空了，不能进行