前言

今天我们再来讲一期关于题目的博客，我挑选的是一道leetcode上面的一道题，这道题目说起来也不是特别难，我们将使用栈的性质来解决这道题,让我们一起来解决这道题

在这里插入图片描述
我们通过题目可以发现我们有三种括号，上面举的例子不多

//成功匹配的例子：
{([{}])}()[]

//不成功匹配的例子：
[
)
[[]}

我们通过栈来实现这个题目，所有的左括号入栈，右括号就匹配
在这里插入图片描述
最后结束后栈空就匹配成功

我们首先需要有一个栈

typedef char STDataType;
struct Stack
{
	STDataType* a;
	int top;
	int capacity;
};
typedef struct Stack ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->top = 0;//为0的话，top指向的是栈顶的下一个元素，如果为-1；就指向栈顶元素
	ps->capacity = 4;
}
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
    ps->capacity=ps->top=0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
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];
}
int StackSize(ST* ps)//返回栈里有多少个元素
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

不会的可以在我写的关于栈的那篇博客中去学学

我们来看看代码：

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            else
            {
                char top=StackTop(&st);
                StackPop(&st);
                if(*s==')'&&top!='('||
                    *s=='}'&&top!='{'||
                    *s==']'&&top!='[')
                    {
                        return false;
                    }

            }
        }
        s++;
    }
    bool ret=StackEmpty(&st);
    if(ret)
    {
        return true;
    }
    return false;
    
}