栈的应用（括号匹配）

文章目录核心思想代码实现查考方式方式一手动模拟栈的变化考察“栈内元素”方式二考察“失败”的边界条件三种失败模式方式三算法的时间/空间复杂度核心思想逻辑本质括号匹配是典型的“嵌套结构”。最后出现的左括号必须最先被匹配后进先出。括号具备就近匹配、后进先出的特性后出现的左括号必须先和最近的右括号配对完美契合栈LIFO规则。遇到左括号压入栈底等待匹配。遇到右括号检查栈顶。如果栈顶是对应的左括号则弹出匹配成功否则匹配失败。遍历结束如果栈为空则全部匹配如果栈不为空说明有左括号多余。代码实现#includestdio.h#includestdbool.h#includestring.h#defineMaxSize10// 定义栈中最大元素的个数 若存满了 可使用 链栈typedefstruct{chardata[MaxSize];// 静态数组存放栈中元素inttop;// 栈顶指针指向栈顶元素初始为-1}SqStack;// 基础操作// 考试中可直接使用基本操作建议简要说明接口作用// 1.初始化栈 初始化空栈指针指向数组下标 -1无效位置voidInitStack(SqStackS){S.top-1;// 空栈标志}// 2.判断栈是否为空 判断栈是否为空top 是否为 -1boolStackEmpty(SqStack S){returnS.top-1;}// 3.新元素入栈 入栈先移指针top再放元素boolPush(SqStackS,charx){if(StackFull(S))returnfalse;// 栈满报错S.data[S.top]x;// 先移指针再存数据returntrue;}// 4.栈顶元素出栈用 x 返回 出栈先取元素再移指针top--boolPop(SqStackS,charx){if(StackEmpty(S))returnfalse;// 栈空报错xS.data[S.top--];// 先取数据再移指针returntrue;}// 核心逻辑函数boolbracketCheck(charstr[],intlength){SqStack S;InitStack(S);// 初始化栈for(inti0;ilength;i){// 1. 遇到左括号入栈if(str[i](||str[i][||str[i]{){Push(S,str[i]);// 扫描到左括号入栈}else{// 2. 遇到右括号进行匹配检查if(str[i])||str[i]]||str[i]}){// 【考点】如果栈为空说明右括号单身匹配失败if(StackEmpty(S)){returnfalse;// 右括号单身匹配失败}chartopElem;Pop(S,topElem);// 弹出栈顶左括号 栈顶元素出栈// 检查弹出的左括号是否与当前右括号匹配if(str[i])topElem!()returnfalse;if(str[i]]topElem![)returnfalse;if(str[i]}topElem!{)returnfalse;}}// 3. 忽略其他非括号字符}// 【考点】遍历结束后栈非空说明左括号多了returnStackEmpty(S);// 检索完全部括号后栈空说明匹配成功}查考方式方式一手动模拟栈的变化考察“栈内元素”形式给出一个括号序列问“栈中元素个数最多的时候是多少”或“某一时刻栈底的元素是什么”实战演示序列{ [ ( ) ] } ( )扫描字符操作栈内元素栈底→栈顶备注{入栈{栈底[入栈{ [(入栈{ [ (此时栈内元素最多3个)匹配 ({ [弹出 (]匹配 [{弹出 [}匹配 {空弹出 {(入栈()匹配 (空弹出 (答案最多时有3个元素栈底始终是{。方式二考察“失败”的边界条件三种失败模式(选择题)算法会在以下三种情况返回false三种失败对应代码行通俗记忆①左括号单身return StackEmpty(S);返回 false“左剩了” —— 遍历完栈底还有存货②右括号单身if (StackEmpty(S))return false;“右多了” —— 刚来右括号栈却空了③左右不匹配if (topElem ! ...)return false;“穿错鞋” —— 栈顶是圆括号却来了方括号方式三算法的时间/空间复杂度时间复杂度O(n)只需遍历一次字符串每个元素入栈/出栈一次。空间复杂度O(n)最坏情况下全是左括号栈需要n个空间。用栈实现括号匹配依次扫描所有字符遇到左括号入栈遇到右括号则弹出栈顶元素检查是否匹配。匹配失败的情况①左括号单身②右括号单身③左右括号不匹配