栈的应用习题：有效的括号

typedef int typedata;
typedef struct stack {
	typedata* a;
	int top;
	int capacity;
 } ST;

void STinit(ST* p) {
	assert(p);
	p->a = NULL;
	p->capacity = p->top = 0;
}
void STpush(ST* p,typedata x) {
	assert(p);
	//扩容
	if (p->top == p->capacity) {
		int newcapacity = p->capacity == 0 ? 4 : (p->capacity) * 2;
		typedata* tmp = (typedata*)realloc(p->a, sizeof(typedata)*newcapacity);
		if (tmp == NULL) {
			perror("realloc");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;

	}
	p->a[p->top] = x;
	p->top++;
}
void STpop(ST* p) {
	assert(p);
	assert(p->top);
	p->top--;


}

typedata STTop(ST* p) {
	assert(p);
	assert(p->top);
	return p->a[p->top - 1];

}
bool STempty(ST* p) {
	assert(p);
	return p->top == 0;
}
int STsize(ST* p) {
	assert(p);
	return p->top;
}
void STdestroy(ST* p) {
	assert(p);
	free(p->a);
	p->a = NULL;
	p->capacity = p->top = 0;
}

//上方为创建栈



bool isValid(char* s) {
    ST m;
    STinit(&m);
    while(*s){
        if(*s=='('||*s=='['||*s=='{'){
             STpush(&m,*s);

        }//如果是左括号，就把它放入栈
        else{
            ///这里判断栈是否为空，为空则无法与右括号匹配，false
            if(STempty(&m)){
                STdestroy(&m);
                return false;
            }
            ///不为空的话，就匹配，由于要判断都符合需要都满足条件，而不合适的话一次就可以输出false，故判断不匹配
            char top=STTop(&m);
             STpop(&m);
            if(top=='('&&*s!=')'||
            top=='['&&*s!=']'||
              top=='{'&&*s!='}'){
                 STdestroy(&m);
                  return false;
            }
        }
        s++;
    }///为了可以释放掉开辟的空间，故首先保存返回值，然后销毁栈，最后输出
    bool ret=STempty(&m);
     STdestroy(&m);
     return ret;

}