/*
  建立链栈实现括号匹配问题   创建栈,判断是否空栈 
*/
#include<stdio.h> 
#include<stdlib.h>
#include<string.h>
#define status int
typedef struct node
{
	char ch; 
	node* next;
}SNode;
typedef struct
{
	SNode *top;
	//SNode *base;
}Stack;
//创建空栈    base  赋值为NULL, top 指向栈顶元素 
status initStack(Stack &S)  
{	
	S.top=NULL;
	return 0; 
} 
bool empty(Stack S)
{
	if(NULL==S.top)
	return 1; 
	return 0;
}
status pushStack(Stack &S,char e) //入栈 
{
	SNode* p;
	p=(SNode*)malloc(sizeof(SNode));
	if(NULL==p) 
	{
		printf("内存分配失败,终止程序!\n");
		exit(-1);
	}
	p->ch=e; 
	p->next=S.top;
	S.top=p;
	//printf("%c入栈成功\n",e) ;
	return  0;
}
status popStack(Stack &S,char &e) //出栈
{
	SNode *q;
	if(NULL!=S.top)
	{
	//	printf("%X&&\n",S.top);
		e=S.top->ch;
		q=S.top;
		S.top=q->next;
		free(q);
		//printf("%c成功出栈\n\n",e) ;
		return 1;
	}
	else
	{
		printf("栈为空,出栈失败!\n");
		return 0;
	}
	
} 
status clearStack(Stack &S) //清空栈 
{
	while(NULL!=S.top)
	{
		SNode *q;
		q=S.top;
		free(q);
		S.top=S.top->next;
	}
}
status matching(Stack &S,char str[],int len)
{
	int i;char e;
	for(i=0;i<len;++i)
	{
		if(str[i]=='{'||str[i]=='['||str[i]=='(')
		pushStack(S,str[i]);
		else if(empty(S))
		{
			printf("不匹配\n");
			return 0 ;
		}
		else 
		{
		   	if(str[i]=='}')
		   	{
		   		if(S.top->ch=='{')
		   		popStack(S,e);
		   		else
		   		{
					printf("不匹配\n") ;
		   			return 0 ;
		   		}
		   	}
		   	else if(str[i]==']')
		   	{
		   		if(S.top->ch=='[')
		   		popStack(S,e);
		   		else 
				{
					printf("不匹配\n");
						//printf("不匹配,到来不速之客\n") ;
		   			return 0 ;
				}
		   	}
		   	else if(str[i]==')')
		   	{
		   		if(S.top->ch=='(')
		   		popStack(S,e);
		   		else
				{
					printf("不匹配\n");
		   			return 0 ;
				} 
		   	}
		}
	}
	if(empty(S))
	printf("匹配\n");
	else
	{
		printf("不匹配\n");
	}
}
status main()
{
	Stack S;
	initStack(S);
	int i,len;
	char str[20],ch;
    while(~scanf("%s",str))
    {
    	  len=strlen(str);
          matching(S,str,len);
          clearStack(S);
    }
	return 0;
}

括号匹配(链栈实现)