#include <stdio.h>
#include <stdlib.h>
#include "string.h" 
#define  OVERFLOW  0
#define  OK        1
#define  ERROR     0 


/* 作者：张泽涛 
   */ 
   
typedef struct StackNode
{
    char data;
    struct StackNode *next; 
}StackNode,*LinkStack;

int InitStack(LinkStack *S) //链栈初始化 
{
    (*S)=(StackNode*)malloc(sizeof(StackNode));
    (*S)->next=NULL;
}

int StackEmpty(LinkStack S) //判断栈是否为空 
{
    if(!(S->next)) 
        return OK;
    else   
        return ERROR;
}

int Push(LinkStack *S,char ch) //进栈 
{
    StackNode *p;
    p=(StackNode*)malloc(sizeof(StackNode));//生成新结点
    p->data=ch;
    p->next=*S;
    *S=p;
    return OK; 
}

int Pop(LinkStack *S, char ch) //出栈 
{
    StackNode *p;
    ch=(*S)->data;
    p=*S;
    (*S)=(*S)->next;
    free (p);
    return OK;
}
 
char GetTop(LinkStack S) //取栈顶指针 
{
    if(S!=NULL)
      return S->data; 
} 

int main()
{
    char A[10],ch,x;
    int i;
    int flag=1;
    
    while(1)
    {
        LinkStack S;
        InitStack(&S);
        printf("输入表达式：\n");
        scanf("%s",&A); 
    
        for(i=0;(i<strlen(A))&&flag;i++)
        {
            ch=A[i];    //读入数组中第一个字符 
            switch(ch)
            { 
            case '{':      
            case '[':
            case '(':
                Push(&S,ch);      //将元素压入栈 
                break;
            case ')':   
                if(!StackEmpty(S)&&GetTop(S)=='(')      //如果栈不为空并且取栈顶元素得到的是'(' 
                                    {
                        x=GetTop(S);                   //将栈顶元素取出来赋给x 
                        Pop(&S,x);                     //把元素x出栈 
                    }       
                else
                flag=0;                                //标志为0 
                break;
            case ']':
                if(!StackEmpty(S)&&GetTop(S)=='[')
                    {
                        x=GetTop(S);
                        Pop(&S,x);
                    }
                else
                flag=0;
                break;
            case '}':
                if(!StackEmpty(S)&&GetTop(S)=='{')
                    {
                        x=GetTop(S);
                        Pop(&S,x);
                    }
                else
                flag=0;
                break;                  
            }
        }
            if(StackEmpty(S)&&flag)                           //如果栈不为空并且标志位不为零，那么就匹配成功，否则匹配失败。 
                printf("匹配成功。\n");
            else 
                printf("匹配失败。\n");  
     } 
    return 0;
}