题目描述

题目链接：20. 有效的括号 - 力扣（LeetCode）

题目分析

题目给了我们三种括号：（）、{ }、[ ]

这里的匹配包括：顺序匹配和数量匹配

最优的思路就是用栈来解决：

括号依次入栈，当遇到右括号的时候，和他最近的那个左括号匹配，能匹配则返回true，否则false；最近的左括号即为栈顶元素

数组栈我们在之前实现过，直接拿来用就可以了：数组栈的实现-CSDN博客

由于存放的数据是字符，所以这里的STDataType就可以typedef为char

遍历字符串：

• 是左括号就入栈
• 遇到右括号，则取栈顶元素，并pop掉
• 最后如果栈为空则返回true，否则返回false，所以我们还需要判空
• 防止内存泄漏，我们在每次返回false之前都需要Destroy

代码示例

根据这个思路我们就可以写代码了：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//标识栈顶位置
	int capacity;
}ST;
//声明

//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);

//定义

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}
//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

bool isValid(char* s) {
	ST st;
	STInit(&st);
	//遍历
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			STPush(&st, *s);
		}
		else
		{
			if (STEmpty(&st))
			{
				STDestroy(&st);
				return false;
			}
			//取栈顶元素
			char top = STTop(&st);
			STPop(&st);
			//匹配
			if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{'))
			{
				STDestroy(&st);
				return false;
			}
		}
		++s;
	}
	bool ret = STEmpty(&st);
	STDestroy(&st);
	return ret;
}