文章目录
- 核心思想
- 代码实现
- 查考方式
- 方式一：手动模拟栈的变化（考察“栈内元素”）
- 方式二：考察“失败”的边界条件（三种失败模式）
- 方式三：算法的时间/空间复杂度
核心思想
逻辑本质：括号匹配是典型的“嵌套结构”。最后出现的左括号，必须最先被匹配（后进先出）。
括号具备就近匹配、后进先出的特性：后出现的左括号，必须先和最近的右括号配对，完美契合栈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个） |
| ) | 匹配 ( | { [ | 弹出 ( |
| ] | 匹配 [ | { | 弹出 [ |
| } | 匹配 { | 空 | 弹出 { |
| ( | 入栈 | ( | |
| ) | 匹配 ( | 空 | 弹出 ( |
答案：最多时有3个元素；栈底始终是{。
方式二：考察“失败”的边界条件（三种失败模式）
(选择题)算法会在以下三种情况返回false：
| 三种失败 | 对应代码行 | 通俗记忆 |
|---|---|---|
| ①左括号单身 | return StackEmpty(S);（返回 false） | “左剩了” —— 遍历完，栈底还有存货 |
| ②右括号单身 | if (StackEmpty(S))return false; | “右多了” —— 刚来右括号，栈却空了 |
| ③左右不匹配 | if (topElem != ...)return false; | “穿错鞋” —— 栈顶是圆括号，却来了方括号 |
方式三：算法的时间/空间复杂度
- 时间复杂度：
O(n)（只需遍历一次字符串，每个元素入栈/出栈一次）。 - 空间复杂度：
O(n)（最坏情况下全是左括号，栈需要n个空间）。
用栈实现括号匹配：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。
匹配失败的情况：①左括号单身②右括号单身③左右括号不匹配
