#include "stdio.h"
#include "malloc.h"

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef struct{
    char *base;
    char *top;
    int stacksize;
}sqStack;

int initStack(sqStack *s)
{
    /*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/
    s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
    if(!s->base) return 0;              /*分配空间失败*/
    s->top = s->base;                   /*最开始，栈顶就是栈底*/
    s->stacksize = STACK_INIT_SIZE;     /*最大容量为STACK_INIT_SIZE */
    return 1;
}

int Push(sqStack *s, char e){
    if(s->top - s->base >= s->stacksize){
    /*栈满，追加空间*/
    s->base = (char *)realloc(s->base, (s->stacksize +
    STACKINCREMENT)*sizeof(char));
    if(!s->base) return 0;          /*存储分配失败*/
    s->top = s->base + s->stacksize;
    s->stacksize = s->stacksize + STACKINCREMENT;       /*设置栈的最大容量*/
    }
    *(s->top) = e;          /*放入数据*/
    s->top++;
    return 1;
}

int Pop(sqStack *s , char *e){
    if(s->top == s->base) return 0;
    *e = *--(s->top); 
    return 1;
}

int match(char e,char c){       /*比较栈顶元素e和输入的括号字符c是否匹配*/
    if(e=='(' && c==')')return 1;
    if(e=='[' && c==']')return 1;
    return 0;
}


void MatchBracket()
{
    sqStack s;
    char c , e ;
    initStack( &s );            /*初始化一个空栈*/
    scanf("%c",&c);         /*输入第一个字符*/
    while(c!='#'){          /*'#'为输入的结束标志*/
        if(s.top == s.base)
            Push(&s,c); /*如果栈为空，则说明输入的是第一个字符，因此保存在栈中*/
        else
        {
             Pop(&s,&e);        /*取出栈顶元素*/
             if(match(e,c)!= 1){/*将输入的元素与取出的栈顶进行比较，如果匹配不成功*/
                Push(&s,e); /*先将原栈顶元素重新入栈*/
                Push(&s,c); /*再将输入的括号字符入栈*/
               }
        }
        scanf("%c",&c);  /*输入下一个字符*/
        }
    if(s.top == s.base)  printf("The brackets are matched\n");  /*如果栈s为空，则括号完全匹配*/
    else  printf("The brackets are not matched\n");     /*如果栈s不为空，则括号不完全匹配*/

}

main()
{
    printf("Please input some brackets for determing whether match\n");
    MatchBracket();
    getchar();
    getchar();
}