《数据结构与算法》课程设计报告
题目：括号匹配检验
四．算法思想
利用栈来判断括号是否匹配时，遇到左括号就进栈，遇到右括号则左括号出栈，代表这对括号匹配，如果右括号进栈时，栈为空，则说明缺少左括号，若表达式扫描完栈为空，则说明表达式的括号匹配，否则说明表达式缺少左括号。
五．算法设计
程序流程图
算法用到的抽象数据类型定义：
1．ADT Stack{
数据对象：D={a i|a i∈ElemSet,i=1,2，…，n, n≥0}
数据关系：R1={|a i-1,a i∈D,i=2, …,n}
约定a n端为栈顶，a1端为栈底。
基本操作：
（1）I nitStack(&S)；
操作结果：构造一个空栈S。
（2）S tackEmpty(S)；
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TURE，否则FALUSE。
（3）S tackFull(S)；
初始条件：栈S已存在。
操作结果：若栈S为满，则返回TURE,否则FALUSE.
（4）G etTop(S,&e)；
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
（5）P ush(&S,e)；
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
（6）P op(&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 "stdio.h"
/*顺序栈*/
typedef struct
{
StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
int top; /*用来存放栈顶元素的下标，top为-1表示空栈*/
}SeqStack;
/*初始化*/
void InitStack(SeqStack *S)
{
/*构造一个空栈S*/
S->top = -1;
}
/*判栈空*/
int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
return(S->top==-1?TRUE:FALSE);
}
/*判栈满*/
int IsFull(SeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int Push(SeqStack *S,StackElementType x)
{
if(S->top==Stack_Size-1)
return(FALSE); /*栈已满*/
S->top++;
S->elem[S->top] = x;
return(TRUE);
}
int Pop(SeqStack *S,StackElementType *x)
{
/* 将栈S的栈顶元素弹出，放到x所指的存储空间中*/
if(S->top == -1) /*栈为空*/
return(FALSE);
else
{
*x = S->elem[S->top];
S->top--; /* 修改栈顶指针*/
return(TRUE);
}
}
/*取栈顶元素。*/
int GetTop(SeqStack *S,StackElementType *x)
{
/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/
if(S->top == -1) /*栈为空*/
return(FALSE);
else
{
*x = S->elem[S->top];
return(TRUE);
}
}
/*进行匹配*/
int Match(char ch,char str)
{
if(ch=='(' && str==')')
{
return TRUE;
}
else if(ch=='[' && str==']')
{
return TRUE;
}
else if(ch=='{' && str=='}')
{
return TRUE;
}
else
return FALSE;
}
void BracketMatch(char *str) /* str[]中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配*/
{
SeqStack S;
int i;
char ch;
InitStack(&S);
for(i=0; str[i]!='\0'; i++) /*对字符串中的字符逐一扫描*/
{
switch(str[i])
{
case '(':
case '[':
case '{':
Push(&S,str[i]);
break;
case ')':
case ']':
case '}':
if(IsEmpty(&S))
{
printf("\n右括号多余!\n");
return;
}
else
{
GetTop(&S,&ch);
if(Match(ch,str[i])) /*用Match判断两个括号是否匹配*/
Pop(&S,&ch); /*已匹配的左括号出栈*/
else
{
printf("\n对应的左右括号不同类!\n");
return;
}
}
}/*switch*/
}/*for*/
if(IsEmpty(&S))
printf("\n括号匹配!\n");
else
printf("\n左括号多余!\n");
}
void main()
{
char str[100];
printf(" ************括号匹配的检验*********\n");
printf("\n");
printf("请输入括号序列: ");
gets(str);
BracketMatch(str);
printf("程序设计成员（以下名字按姓氏排列）：\n");
}
七