栈的应用（括号匹配）

核心思想

逻辑本质：括号匹配是典型的“嵌套结构”。最后出现的左括号，必须最先被匹配（后进先出）。
括号具备就近匹配、后进先出的特性：后出现的左括号，必须先和最近的右括号配对，完美契合栈LIFO规则。

• 遇到左括号：压入栈底（等待匹配）。
• 遇到右括号：检查栈顶。如果栈顶是对应的左括号，则弹出（匹配成功）；否则匹配失败。
• 遍历结束：如果栈为空，则全部匹配；如果栈不为空，说明有左括号多余。
  

代码实现

#include<stdio.h>#include<stdbool.h>#include<string.h>#defineMaxSize10// 定义栈中最大元素的个数 若存满了 可使用 链栈typedefstruct{chardata[MaxSize];// 静态数组存放栈中元素inttop;// 栈顶指针：指向栈顶元素（初始为-1）}SqStack;// 基础操作// 考试中可直接使用基本操作，建议简要说明接口作用// 1.初始化栈 初始化空栈，指针指向数组下标 -1（无效位置）voidInitStack(SqStack&S){S.top=-1;// 空栈标志}// 2.判断栈是否为空 判断栈是否为空（top 是否为 -1）boolStackEmpty(SqStack S){returnS.top==-1;}// 3.新元素入栈 入栈：先移指针（top++），再放元素boolPush(SqStack&S,charx){if(StackFull(S))returnfalse;// 栈满报错S.data[++S.top]=x;// 先移指针，再存数据returntrue;}// 4.栈顶元素出栈，用 x 返回 出栈：先取元素，再移指针（top--）boolPop(SqStack&S,char&x){if(StackEmpty(S))returnfalse;// 栈空报错x=S.data[S.top--];// 先取数据，再移指针returntrue;}// 核心逻辑函数boolbracketCheck(charstr[],intlength){SqStack S;InitStack(S);// 初始化栈for(inti=0;i<length;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个元素；栈底始终是{。

方式二：考察“失败”的边界条件（三种失败模式）

(选择题)算法会在以下三种情况返回false：

方式三：算法的时间/空间复杂度

• 时间复杂度：O(n)（只需遍历一次字符串，每个元素入栈/出栈一次）。
• 空间复杂度：O(n)（最坏情况下全是左括号，栈需要n个空间）。

用栈实现括号匹配：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。
匹配失败的情况：①左括号单身②右括号单身③左右括号不匹配