括号匹配

赵增良

计算机科学与技术（非师范）091班09220137

一 、 问题描述

输入“（”，“）”，“[”，“]”这些括号，以“@”结尾，编程实现判断输入的括号是否成功匹配。

二 、 设计思路 用栈操作，对输入逐个判断，如果出现是右括号且栈空或者右括号且与栈顶没有匹配或者左括号有剩余，则说明没有匹配，否则成功匹配。 三 、 源代码 #include

#include

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct //栈节点 {

char *base; char *top; int stacksize;

}SqStack;

int Initstazk(SqStack &S) //建栈函数

{

S.base=(char *)malloc(STACK_INIT_SIZE * sizeof(char)); if(!S.base)exit(0);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return 1; }

int Push(SqStack &S,char e) //压入栈函数 {

if(S.top-S.base>=S.stacksize) {

S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char)); if(!S.base)exit(0);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e; return 1;

}

int Pop(SqStack &S,char &e) //弹出栈函数 {

if(S.top==S.base)return 0;

e=*--S.top;

return 1; }

bool StackEmpty(SqStack &S) //判断栈是否为空函数 {

return S.top==S.base?1:0; } int main() { int i,t;

char a,b; SqStack S;

Initstazk(S); //建栈 printf(\"请输入括号，以@结束\\n\");

while(scanf(\"%c%*c\ //输入，已@结束 {

if(a=='('||a=='[')Push(S,a); //如果是左括号，进栈

else {

if(StackEmpty(S)){t=0;break;} //是右括号，栈空则没有匹配 else

{

Pop(S,b);

if(!((a==')'&&b=='(')||(a==']'&&b=='['))){t=0;break;} //右括号与栈顶元素不匹配则没有匹配 } }

}

if(a=='@') //全部检测 {

if(!StackEmpty(S))t=0; //栈不空，则没有匹配 else t=1; //栈空，则成功匹配 }

if(t==0)printf(\"没有匹配\\n\"); else printf(\"匹配成功\\n\"); return 0;

}

四 、 运行结果

两组数据的运行结果

五 、 实验体会

掌握栈的创建、压入栈、弹出栈、判断栈是否为空等的操作，熟练栈的运用。