大家好，我是小卡皮巴拉
文章目录
目录
力扣题目： 有效的括号
题目描述
示例 1：
示例 2：
示例 3：
示例 4：
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（C语言）
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目： 有效的括号
原题链接：有效的括号
题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
解题思路
问题理解
题目要求我们判断一个仅包含括号（'('，')'，'{'，'}'，'['，']'）的字符串是否有效。有效字符串需满足以下条件：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
算法选择
我们可以使用栈（Stack）这一数据结构来解决这个问题。栈的特点是后进先出（LIFO），非常适合处理这种需要匹配和回溯的问题。
具体思路
初始化栈：首先，我们需要一个栈来存储左括号。在C语言中，我们可以定义一个栈的数据结构
ST，并初始化它。遍历字符串：使用指针
pi遍历输入的字符串s。处理左括号：如果当前字符是左括号（'('、'{'、'['），则将其压入栈中。
处理右括号：
首先检查栈是否为空。如果为空，说明没有对应的左括号来匹配当前的右括号，因此字符串无效。
如果栈不为空，取出栈顶元素（即最近入栈的左括号），并检查它是否与当前的右括号匹配。
如果不匹配，或者栈顶元素不是对应的左括号，则字符串无效。
如果匹配，则弹出栈顶元素（即移除已匹配的左括号）。
遍历结束后检查：遍历完整个字符串后，检查栈是否为空。如果为空，说明所有左括号都得到了正确匹配和闭合，字符串有效；否则，字符串无效。
销毁栈：在返回结果之前，销毁栈以释放分配的内存。
解题要点
栈的使用：用于存储左括号，并在遇到右括号时弹出栈顶元素进行匹配。
括号匹配：使用哈希表或数组来快速判断右括号是否与栈顶的左括号匹配。
遍历结束后的检查：遍历结束后，栈应为空，否则说明有未匹配的左括号。
完整代码（C语言）
typedef char STDataType; //定义栈的数据结构 typedef struct Stack {STDataType* arr;int top;//指向栈顶位置int capacity; }ST; //初始化 void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->top = ps->capacity = 0; }//销毁 void STDestroy(ST* ps) {if (ps->arr != NULL)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0; }//入栈——栈顶 void StackPush(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!\n");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x; }//栈是否为空 bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0; }//出栈——栈顶 void StackPop(ST* ps) {assert(!StackEmpty(ps));ps->arr[(ps->top)--]; }//取栈顶元素 STDataType StackTop(ST* ps) {assert(!StackEmpty(ps));return ps->arr[ps->top - 1]; } bool isValid(char* s) {//借助数据结构——栈，遇到左括号就入栈，遇到右括号就取栈顶元素检查是否是与之对应的右括号ST st;STInit(&st);char* pi = s;while(*pi != '\0'){if(*pi == '(' || *pi == '{' || *pi == '['){//入栈StackPush(&st,*pi);}else{//取栈顶，判断if(StackEmpty(&st))return false;char top = StackTop(&st);if((top =='('&& *pi != ')')||(top == '['&& *pi !=']')||(top == '{'&& *pi != '}'))return false;StackPop(&st);}pi++;}bool ret = StackEmpty(&st) ? true:false;STDestroy(&st);return ret; }
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
