4.1OJ题：括号匹配问题

点击上面网址可查看原题

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1）左括号必须用相同类型的右括号闭合。
2）左括号必须以正确的顺序闭合。

解答

首先我们先把栈的接口函数完善进去

typedef char STDataType;
typedef struct Stack{
    STDataType* a;
    int top;
    int capacity;
}ST;
void StackInit(ST* ps){
    assert(ps);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}
void StackPush(ST* ps,STDataType x){
    assert(ps);
    if(ps->top==ps->capacity){
        int newcapacity=ps->capacity==0?4:ps->capacity*2;
        STDataType* tmp=(STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
        if(tmp==NULL){
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity=newcapacity;
    }
    ps->a[ps->top++]=x;
}
void StackPop(ST* ps){
    assert(ps);
    assert(ps->top>0);
    ps->top--;
}
STDataType StackTop(ST* ps){
    assert(ps);
    assert(ps->top>0);
    return ps->a[ps->top-1];
}
void StackDestroy(ST* ps){
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}

然后在完善括号匹配函数的功能

bool isValid(char * s){
    ST st;
    StackInit(&st);
    for(int i=0;s[i]!='\0';++i){
        if(s[i]=='('||s[i]=='{'||s[i]=='['){
            StackPush(&st,s[i]);
        }else{
            if(st.top==0){
                StackDestroy(&st);
                return false;
            }
            if((s[i]==')'&&StackTop(&st)!='(')
             ||(s[i]=='}'&&StackTop(&st)!='{')
             ||(s[i]==']'&&StackTop(&st)!='[')){
                StackDestroy(&st);
                return false;
             }else{
                 StackPop(&st);
             }
        }
    }
    if(st.top==0){
        StackDestroy(&st);
        return true;
    }else{
        StackDestroy(&st);
        return false;
    }
}