#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define FALSE 0
#define maxsize 1024
typedef struct node
{
	char data;
	struct node *next;
}linkstack;

linkstack *setnull(linkstack *r);
int Empty(linkstack *r);
linkstack *push(linkstack *r,char ch);
int match(char c1,char c2);
linkstack *poplstack(linkstack *r);

typedef struct 
{
	char data[maxsize];
	int last;
}sequenlist;

int check_pair(sequenlist *L)
{
	linkstack *top;
	int i;
	top=(linkstack *)malloc(sizeof(linkstack));
	top=setnull(top);
	int top_elem;
	for(i=0;i<=(*L).last;i++)
	{
	if(Empty(top))
	{
		top=push(top,L->data[i]);
		top_elem=i;
	}
	else if(match(L->data[top_elem],L->data[i]))
	{
		top=poplstack(top);
		top_elem-=1;
	}
	else 
	{
		top=push(top,L->data[i]);
		top_elem=i;
	}


	}
	if(Empty(top))
		return OK;
	else 
		return FALSE;
}

linkstack *setnull(linkstack *r)
{
	r=NULL;
	return r;
}

int Empty(linkstack *r)
{
	if(r==NULL)
	return OK;
	else return FALSE;
}

linkstack *push(linkstack *r,char ch)
{
	linkstack *p;
	p=(linkstack *)malloc(sizeof(linkstack));
	p->data=ch;
	p->next=r;
	return p;
}

linkstack *poplstack(linkstack *r)
{
	linkstack *p;
	p=r->next;
	free(r);
	return p;
}


int match(char c1,char c2)
{
	if(((c1=='('&&c2==')')||(c1==')'&&c2=='('))||((c1=='{'&&c2=='}')||(c1=='}'&&c2=='{'))||((c1=='['&&c2==']')||(c1==']'&&c2=='[')))
	return OK;
	else return FALSE;
}



void main()
{
	sequenlist *A;
	A=(sequenlist *)malloc(sizeof(sequenlist));
	int m,x,i;
	printf("请输入元素个数：\n");
	scanf("%d",&m);
	printf("\n");
	printf("请输入带验证匹配的符号:\n");
	for(i=0;i<m;i++)
	{
		scanf("%c",&A->data[i]);
	}
	A->last=m-1;
	x=check_pair(A);
	if(x)
	printf("全部匹配成功；\n");
	else printf("未匹配完成；\n");
}