数据结构实验之栈四：括号匹配
Time Limit: 1000MS Memory limit: 65536K
题目描述
给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。输入
输入数据有多组，处理到文件结束。输出
如果匹配就输出“yes”，不匹配输出“no”示例输入
sin(20+10){[}]
示例输出
yesno
提示
来源
ma6174示例程序
#include <stdio.h>
#include <stdlib.h>#include <string.h>
#define sizenum 100
#define maxsize 100
typedef char element;
typedef struct
{
element *top;
element *base;
int stsize;
}sq;
int intistack(sq*l)
{
l->base=(element*)malloc(maxsize*sizeof(element));
if(!l->base)
return -1;
l->top=l->base;
l->stsize=maxsize;
return 0;
}
int empty(sq*l)
{
if(l->base==l->top)
return 1;
else return 0;
}
int push(sq*l,char *a)
{
if(l->top-l->base>l->stsize)
{
l->base=(element*)realloc(l->base,(l->stsize+sizenum)*sizeof(element));
if(!l->base)
return -1;
l->top=l->base+l->stsize;
l->stsize+=sizenum;
}
*(++l->top)=*a;
return 0;
}
void chuli(sq*l,char s[])
{
int i,len=strlen(s);
for(i=0;i<len;i++)
{
if(s[i]=='('||s[i]=='['||s[i]=='{')
{
push(l,&s[i]);
}//左括号直接入栈
else
{
if(empty(l)&&(s[i]==')'||s[i]==']'||s[i]=='}'))
{
push(l,&s[i]);
break;
}//栈空右括号入栈
if(!empty(l)&&s[i]==')'||s[i]==']'||s[i]=='}')
{
if(*(l->top)=='('&&s[i]==')'||*(l->top)=='['&&s[i]==']'||*(l->top)=='{'&&s[i]=='}')
{
l->top--;
}//栈非空左右括号匹配，栈顶元素（左括号）出栈
else
{
push(l,&s[i]);//括号不匹配，右括号入栈
}
}
}
}
if(empty(l))
printf("yes\n");//栈空--括号匹配
else
printf("no\n");
}
int main()
{
char s[maxsize];
sq l;
while(gets(s)!=NULL)
{
intistack(&l);
chuli(&l,s);
}
return 0;
}