《手撕数据结构经典题系列》有效括号问题

bool isValid(char * s){
    //开辟栈
    ST st;
    StackInit(&st);
    char* str=s;
    while(*str!='\0')
    {
        
        //遇到左括号入栈
        if(*str=='('
        ||*str=='{'
        ||*str=='[')
        {
            StackPush(&st,*str);
            str++;
        }
        else
        {
            //遇到右括号出栈匹配
            if(*str=='}'
            ||*str==']'
            ||*str==')')
            {
                //为空栈时
                if(StackEmpty(&st))
                {
                    StackDestroy(&st);//注意栈空间销毁（养成好的习惯）
                    return false;
                }
                else
                {
                    char tmp=StackTop(&st);//获取栈顶数据
                    StackPop(&st);//出栈
                    if((*str==']'&&tmp!='[')
                    ||(*str=='}'&&tmp!='{')
                    ||(*str==')'&&tmp!='('))
                    {
                        //匹配失败
                        StackDestroy(&st);
                        return false;
                    }
                    else
                        str++;
                }
            }
        }  
    }
    //遍历完时栈还有数据为被出栈
    if(StackEmpty(&st))
    {
        StackDestroy(&st);//结束前先销毁栈
        return true;
    }
    else
    {
        StackDestroy(&st);
        return false;
    }
}

//默认栈数据类型
typedef char STDataType;

//栈类型结构
typedef struct Stack
{
	//数组栈（指向数组的指针）
	STDataType* a;
	//栈顶位置
	int top;
	//栈容量
	int capacity;
}ST;

//栈初始化
void StackInit(ST* ps);
//栈销毁
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶数据
STDataType StackTop(ST* ps);
//栈使用空间大小
int StackSize(ST* ps);
//是否为空栈
bool StackEmpty(ST* ps);

//栈初始化
void StackInit(ST* ps)
{
	//避免传入空指针
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//定义top为栈最后数据的后一个位置
	//也可以选择让top为当前最后数据的位置 此时初始化top=-1;
	ps->capacity = 0;
	return;
}
//栈销毁
void StackDestroy(ST* ps)
{
	//避免传入空指针
	assert(ps);
	free(ps->a);//释放开辟的数组栈空间
	ps->a = NULL;//置空，避免造成野指针
}
//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//栈满的情况
	{
		//如果原来容量为0则让新容量为4，否则为两倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//调整数组栈大小（特别的：当数组指针为NULL时，realloc的作用和malloc的作用一样）
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败，那么就打印错误并结束进程
		{
			perror("realloc fail:");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//存入数据
	ps->top++;//top位置更新
	return;
}
//出栈
void StackPop(ST* ps)
{
	//避免传入空指针
	assert(ps);
	//出栈到数据个数为0结束
	if (StackEmpty(ps))
		return;
	ps->top--;//让top减减得到出栈的效果
	return;
}
//获取栈顶数据
STDataType StackTop(ST* ps)
{
	//避免传入空指针
	assert(ps);
	//为空栈时无栈顶数据
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];//此时top-1才表示栈顶数据的下标
}
//栈使用空间大小
int StackSize(ST* ps)
{
	//避免传入空指针
	assert(ps);

	return ps->top;
}
//是否为空栈
bool StackEmpty(ST* ps)
{
	//避免传入空指针
	assert(ps);

	return ps->top == 0;
}