#define OK 1
#define ERROR 0

//定义顺序堆栈
#define STACK_SIZE 100
#define STACK_INC 10
typedef char Elem;
typedef struct
{
    Elem *base;
    Elem *top;
    int size;
}SqStack;

typedef int Status;

Status CreatStack(SqStack &S)
{
  S.base=(Elem *)malloc(STACK_SIZE*sizeof(Elem));
  S.top=S.base;
  S.size=STACK_SIZE;
  return OK;
}

Status StackEmpty(SqStack S)
{
    if(S.top!=S.base) return ERROR;
    return OK;
}

//进栈
Status Push(SqStack &S,Elem e)
{
    if(S.top-S.base>=S.size){
        S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem));
        S.top=S.base+S.size;
        S.size+=STACK_INC;
    }
    *S.top=e;
    S.top+=1;
    return OK;
}

//出栈
Status Pop(SqStack &S,Elem &e)
{
    if(S.top==S.base) return ERROR;
    S.top-=1;
    e=*S.top;
    return OK;
}

//括号匹配
Status Bracket(SqStack &S,char *str)
{
    int i=0,flag1=0,flag2;
    Elem e;
    while(str[i]!='\0')
    {
        switch(str[i])
        {
            case '(':Push(S,'(');break; //'('进栈
            case '[':Push(S,'[');break; //'['进栈
            case '{':Push(S,'{');break; //'{'进栈
            case ')':{
                    Pop(S,e);
                    if(e!='(') flag1=1; break;
                } //出栈，判断是否为'('
            case ']':{
                    Pop(S,e);
                    if(e!='[') flag1=1;break;} //出栈，判断是否为'['
                    case '}':{Pop(S,e);
                    if(e!='{') flag1=1;break;
                } //出栈，判断是否为'{'
            default:
              printf("你输入的不是有效的符号!");     
              return 0;
        }
        if(flag1) break; //出现不匹配，立即结束循环
        i++;
    }
    flag2=StackEmpty(S); //flag2判断堆栈是否为空
    if(!flag1 && flag2)
      printf("\n你输入括号匹配!\n");
    else
        printf("\n你输入的括号不匹配!\n");
  return OK;
}

//主函数
int main()
{
    int i;
    do{
        printf("\n括号匹配校验:\n");
        printf("1    进入\n");
        printf("0    退出\n");
        printf("请输入你的选择：");
        scanf("%d",&i);
        switch(i)
        {
            case 1:
                char str[255];
                SqStack S;
                int temp;
                printf("\n请输入要验证的括号序列:\n");
                scanf("%s",str);
                scanf("%c",&temp);
                CreatStack(S);
                Bracket(S,str);
                printf("\n");
                break;
            default:
                printf("\n你的输入无效！\n");
        }
    }while(i!=0);
}