【LeetCode刷题指南】--有效的括号

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：随着编程相关知识点的学习，我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站，但是博主一直都在推荐大家使用力扣，是因为力扣的判题严谨且大部分都是接口型题目，与面试中的笔试题也更加贴合。那么还是老样子，博主会为大家提供我自己的思路和代码，但是算法题的解法肯定不止一个，欢迎大家一起交流和讨论。

有效的括号

解题过程：

代码演示：

有效的括号

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

题目描述：

题目示例：

思路：借助数据结构-栈，遍历字符串，左括号入栈，右括号取栈顶元素进行比较，看是否匹配

解题过程：

1.遍历字符串，左括号就入栈，右括号就取栈顶元素

2.前提是不为空才能取，如果为空证明前面没有左括号直接销毁返回false

3.如果不为空，取栈顶元素进行匹配，出现匹配不成功的销毁后返回false

4.如果本次匹配成功，出栈，继续遍历

5.遍历完后进行判空，如果栈为空证明全部匹配上了，返回true，如果不为空则返回false

复杂度：

时间复杂度: O(n)

空间复杂度: O(∗)

代码演示：

typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->top = 0;ps->capacity = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//检查空间//空间不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}//出栈
void STPop(ST*ps)
{//ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{return 	ps->arr[ps->top - 1];;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//求栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}//----------------------以上是栈结构常用接口--------------------------------
bool isValid(char* s) {ST st;STInit(&st);char*pi=s;while(*pi!='\0'){if(*pi=='('||*pi=='['||*pi=='{'){STPush(&st,*pi);}else{//右括号取栈顶元素进行匹配//栈不为空才能取if(STEmpty(&st)){STDestory(&st);return false;}char top=STTop(&st);if((top=='('&&*pi!=')')||(top=='['&&*pi!=']')||(top=='{'&&*pi!='}')){STDestory(&st);return false;}//本次匹配就出栈STPop(&st);}pi++;}//为空有效，非空无效bool ret=STEmpty(&st)?true:false;STDestory(&st);return ret;
}