朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--20.有效的括号
数 据 结 构 专 栏：数据结构
个 人 主 页 ：stackY、
LeetCode 专 栏 ：LeetCode刷题训练营
LeetCode--20.有效的括号：https://leetcode.cn/problems/valid-parentheses/
目录
1.题目介绍
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
编辑
2.实例演示
编辑
3.解题思路
本道题最简单有效的方法就是使用栈来进行解题，如果你不了解栈可以看看我的这篇博客：数据结构：栈和队列。
因为栈是先入后出，因此这样就保证了括号匹配时都是与最近的括号进行匹配，我们可以先创建一个栈，然后遍历这个字符数组，然后将右括号入栈，然后使用左括号来进行一一的匹配，匹配成功之后再进行出栈，如果每一个右括号都有与之匹配的左括号，那么就返回true，如果匹配不成功就返回false，那么在这里要注意几个小小的细节：
1.如果没有右括号入栈，还使用左括号匹配，这时就可以不用匹配了，可以直接返回false。
2.假如s这个字符数组中只有一个右括号，那么还需要在最后检测一下栈，如果栈不为空，那么就证明还有右括号没有匹配成功，因为如果匹配成功就会出栈，所以我们可以设定一个bool的检测值，将这个检测值作为最后的返回值。
正常情况：
编辑
特殊情况1：
编辑
特殊情况2：
编辑
代码演示：
//动态栈 typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity; //栈的容量 }Stack; //对栈的初始化 void StackInit(Stack* pst); //入栈 void StackPush(Stack* pst, STDataType x); //出栈 void StackPop(Stack* pst); //获取栈顶元素 STDataType StackTop(Stack* pst); //获取栈中的有效元素的个数 int StackSize(Stack* pst); //检测栈是否为空 bool StackEmpty(Stack* pst); //销毁栈 void StackDestroy(Stack* pst); //对栈的初始化 void StackInit(Stack* pst) { assert(pst); pst->a = NULL; //top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置 //pst->top = -1 //top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置 pst->top = 0; pst->capacity = 0; } //入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); //检测容量 if (pst->top == pst->capacity) { int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; //当pst->a为NULL时执行的功能是和malloc一样 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 StackPop(Stack* pst) { assert(pst); //判断栈是否为空 assert(!StackEmpty(pst)); //出栈 pst->top--; } //获取栈顶元素 STDataType StackTop(Stack* pst) { assert(pst); assert(!StackEmpty(pst)); //top指向的是栈顶的下一个位置的元素 return pst->a[pst->top - 1]; } //获取栈中的有效元素的个数 int StackSize(Stack* pst) { assert(pst); return pst->top; } //检测栈是否为空 bool StackEmpty(Stack* pst) { assert(pst); /*if (pst->top == 0) { return true; } else { return false; }*/ return pst->top == 0; } //销毁栈 void StackDestroy(Stack* pst) { assert(pst); //释放 free(pst->a); pst->a = NULL; //重置为0 pst->top = pst->capacity = 0; } bool isValid(char* s) { Stack st; StackInit(&st); while (*s) { //右括号入栈 if (*s == '(' || *s == '{' || *s == '[') { StackPush(&st, *s); } //左括号进行匹配 else { //如果没有右括号插入可以直接返回假 if (StackEmpty(&st)) { //返回前先要销毁 StackDestroy(&st); return false; } //保存栈顶的数据 char tmp = StackTop(&st); //再出栈 StackPop(&st); //进行匹配 //匹配不成功的话就返回假 //匹配成功的话继续匹配后面的 if ((*s == '}' && tmp != '{') || *s == ')' && tmp != '(' || *s == ']' && tmp != '[') { StackDestroy(&st); return false; } } //迭代 s++; } //检测栈中是否还有未匹配成功的右括号 bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！
