数据结构括号匹配检验.doc

《数据结构与算法》课程设计报告题目:,遇到左括号就进栈,遇到右括号则左括号出栈,代表这对括号匹配,如果右括号进栈时,栈为空,则说明缺少左括号,若表达式扫描完栈为空,则说明表达式的括号匹配,否则说明表达式缺少左括号。?程序流程图开始给定判断的表达式检验函数左括号右括号入栈找栈顶元素是否与它配配对删除栈顶,继续不配对,则不匹配栈空匹配栈不空不匹配结束?算法用到的抽象数据类型定义: 1. ADT Stack{ 数据对象: D={a i |a i∈ ElemSet,i=1,2 ,…, n,n≥ 0} 数据关系: R1={<a i-1 ,a i >|a i-1 ,a i∈ D,i=2, …,n} 约定 a n 端为栈顶, a 1 端为栈底。基本操作: (1) InitStack(&S) ; 操作结果:构造一个空栈 S。(2) StackEmpty(S) ; 初始条件:栈 S 已存在。操作结果:若栈 S 为空栈,则返回 TURE ,否则 FALUSE 。(3) StackFull(S) ; 初始条件:栈 S 已存在。操作结果:若栈 S 为满,则返回 TURE, 否则 FALUSE. (4) GetTop(S,&e) ; 初始条件:栈 S 已存在且非空。操作结果:用 e 返回 S 的栈顶元素。(5) Push(&S,e) ; 初始条件:栈 S 已存在。操作结果:插入元素 e 为新的栈顶元素。(6) Pop(&S,&e) ; 初始条件:栈 S 已存在且非空。操作结果:删除 S 的栈顶元素,并用 e 返回其值。}ADT Stack ?算法中函数编号及功能要求: 1. voidInitStack(SeqStack*S) :初始化,构造一个空栈 S 2. IsEmpty(SeqStack *S) :判断栈 S 为空栈时返回值为真,反之为假 3. IsFull(SeqStack *S) :判断栈 S 为满栈时返回值为真,反之为假 4. Push(SeqStack *S,StackElementType x) :插入元素 x 为新的栈顶元素 5. Pop(SeqStack *S,StackElementType *x) :将栈 S 的栈顶元素弹出,放到 x 所指的存储空间中 6. GetTop(SeqStack *S,StackElementType *x) :将栈 S 的栈顶元素弹出, 放到 x 所指的存储空间中,但栈顶指针保持不变 7. Match(char ch,char str) :进行括号的匹配 8. BracketMatch(char *str) : str[] 中为输入的字符串,利用堆栈技术来检查该字符串中的括号是否匹配?函数之间的调用关系(子程序编号见上): 主函数调用函数 8 函数 8 调用函数 1、2、4、5、6、7 六. C语言实现的程序清单/******* 括号匹配的检验********/ #define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define StackElementType char #include "" /* 顺序栈*/ typedef struct { StackElementType elem[Sta