1
第三章 栈和队列
3.4 实训
【实训 1】栈的应用
1．实训说明
本实训是关于栈的应用，栈在各种高级语言编译系统中应用十分广泛，在本实训程序中，利用栈的
“先进后出”的特点，分析 C 语言源程序代码中的的括号是否配对正确。通过本对本实训的学习，可以
理解的基本操作的实现。
本实训要求设计一个算法，检验 C 源程序代码中的括号是否正确配对。对本算法中的栈的存储实现，
我们采用的是顺序存储结构。要求能够在某个 C 源程序上文件上对所设计的算法进行验证。
2．程序分析
（1）int initStack(sqstack **s) 初始化一个栈
（2）int push(sqstack *s,char x) 入栈，栈满时返回 FALSE
（3）char pop(sqstack *s) 出栈，栈空时返回 NULL
（4）int Empty(sqstack *s) 判断栈是否为空，为空时返回 TRUE
（5）int match(FILE *f) 对文件指针 f 对指的文件进行比较括号配对检验，从文件中每读入一个
字符 ch=fgetc(f)，采用多路分支 switch(ch)进行比较：
①若读入的是“[”、“{”或“（”，则压入栈中，
②若读入的是“]”，则：若栈非空，则出栈，判断出栈符号是否等于“[”，不相等，则返回
FALSE。
③若读入的是“}”，则：若栈非空，则出栈，判断出栈符号是否等于“{”，不相等，则返回
FALSE。
④若读入的是“）”，则：若栈非空，则出栈，判断出栈符号是否等于“（”，不相等，则返回
FALSE。
⑤若是其它字符，则跳过。
文件处理到结束时，如果栈为空，则配对检验正确，返回 TRUE。
（6）主程序 main()中定义了一个文件指针，输入一个已经存在的 C 源程序文件。
3．程序源代码
# define MAXNUM 200
# define FALSE 0
# define TRUE 1
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct {
char stack[MAXNUM];
int top; } sqstack; /*定义栈结构*/
int initStack(sqstack **s)
{/*初始化栈*/
if ((*s=(sqstack*)malloc(sizeof(sqstack)))==NULL) return FALSE;
(*s)->top=-1;
return TRUE;
}
