文档介绍：第三章栈和队列
【实训 1】栈的应用
本实训是关于栈的应用,栈在各种高级语言编译系统中应用十分广泛,在本实训程序中,
利用栈的“先进后出”的特点,分析 C 语言源程序代码中的的括号是否配对正确。通过本对
本实训的学习,可以理解的基本操作的实现。
本实训要求设计一个算法,检验C 源程序代码中的括号是否正确配对。对本算法中的栈
的存储实现,我们采用的是顺序存储结构。要求能够在某个C 源程序上文件上对所设计的算
法进行验证。
(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 源程序文件。
# define MAXNUM 200
# define FALSE 0
# define TRUE 1
#include ""
#include ""
#include ""
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;
}
int push(sqstack *s,char x)
{/*将元素 x 插入到栈 s 中,作为 s 的新栈顶*/
if(s->top>=MAXNUM-1) return FALSE; /*栈满*/
s->top++;
s->stack[s->top]=x;
return TRUE;
}
char pop(sqstack *s)
{/*若栈 s 不为空,则删除栈顶元素*/
char x;
if(s->top<0) retur