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

《数据结构与算法》课程设计报告
题目:括号匹配检验

利用栈来判断括号是否匹配时,遇到左括号就进栈,遇到右括号则左括号出栈,代表这对括号匹配,如果右括号进栈时,栈为空,则说明缺少左括号,若表达式扫描完栈为空,则说明表达式的括号匹配,否则说明表达式缺少左括号。

程序流程图
开始
给定判断的表达式
检验函数
左括号
右括号
入栈
找栈顶元素是否与它配
配对删除栈顶,继续
不配对,则不匹配
栈空匹配
栈不空
不匹配
结束
算法用到的抽象数据类型定义:
Stack{
数据对象:D={ai|ai∈ElemSet,i=1,2,…,n, n≥0}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2, …,n}
约定an端为栈顶,a1端为栈底。
基本操作:
InitStack(&S);
操作结果:构造一个空栈S。
StackEmpty(S);
初始条件:栈S已存在。
操作结果:若栈S为空栈,则返回TURE,否则FALUSE。
StackFull(S);
初始条件:栈S已存在。
操作结果:若栈S为满,则返回TURE,否则FALUSE.
GetTop(S,&e);
初始条件:栈S已存在且非空。
操作结果:用e返回S的栈顶元素。
Push(&S,e);
初始条件:栈S已存在。
操作结果:插入元素e为新的栈顶元素。
Pop(&S,&e);
初始条件:栈S已存在且非空。
操作结果:删除S的栈顶元素,并用e返回其值。
}ADT Stack

算法中函数编号及功能要求:
voidInitStack(SeqStack*S):初始化,构造一个空栈S
IsEmpty(SeqStack *S):判断栈S为空栈时返回值为真,反之为假
IsFull(SeqStack *S):判断栈S为满栈时返回值为真,反之为假
Push(SeqStack *S,StackElementType x):插入元素x为新的栈顶元素
Pop(SeqStack *S,StackElementType *x):将栈S的栈顶元素弹出,放到x所指的存储空间中
GetTop(SeqStack *S,StackElementType *x):将栈S的栈顶元素弹出,放到x所指的存储空间中,但栈顶指针保持不变
Match(char ch,char str):进行括号的匹配
BracketMatch(char *str): str[]中为输入的字符串,利用堆栈技术来检查该字符串中的括号是否匹配
函数之间的调用关系(子程序编号见上):
主函数调用函数8
函数8调用函数1、2、4、5、6、7


/*******括号匹配的检验********/
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
#define StackElementType char
#include ""
/*顺序栈*/
typedef struct
{
StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
int