【数据结构与算法】LeetCode 20.有效的括号

文章目录

• 有效的括号问题详解
• • 问题描述
  • 问题背景与重要性
  • 问题分析
  • • 为什么选择栈结构？
    • 算法选择的原因
  • 算法思路
  • • 算法正确性证明
  • 代码实现解析
  • • 栈数据结构定义
    • 栈操作函数详细解析
    • 核心算法函数
  • 程序源码
  • 复杂度分析
  • • 复杂度证明
  • 示例演示
  • • 有效字符串示例
    • 无效字符串示例
  • 边界情况处理
  • 实际应用场景
  • 扩展思考
  • • 支持更多括号类型
    • 错误定位与反馈
    • 非栈解决方案
    • 性能优化
  • 总结

有效的括号问题详解

问题描述

给定一个只包含括号字符 \'(\', \')\', \'{\', \'}\', \'[\', \']\' 的字符串 s，判断该字符串是否有效。

有效字符串需要满足以下三个条件：

1. 左括号必须用相同类型的右括号闭合

2. 左括号必须以正确的顺序闭合

3. 每个右括号都有一个对应的相同类型的左括号

   

问题背景与重要性

括号匹配是计算机科学中的基础问题，它出现在许多实际应用场景中。从编程语言的语法解析到数学表达式的计算，再到配置文件和数据格式（如JSON、XML）的验证，括号匹配都扮演着重要角色。

问题分析

这是一个经典的栈应用问题。括号匹配需要遵循\"后进先出\"的原则，这与栈的特性完全吻合。

为什么选择栈结构？

括号匹配的核心要求是：最后打开的括号必须最先关闭。这与栈的\"后进先出\"(LIFO)特性完美匹配。

想象一下日常生活中的例子：

• 我们穿脱衣服的顺序是最后穿上的衣服最先脱下
• 叠放盘子时，最后放上去的盘子最先被取用
• 文档编辑中的\"撤销\"功能也是后进先出的典型应用

括号匹配也是同样的道理。当我们遇到嵌套的括号时，最后打开的括号必须最先关闭，这正是栈数据结构的典型应用场景。

算法选择的原因

为什么使用栈而不是其他数据结构？

• 数组：需要维护额外的指针来跟踪最近打开的括号，实质上就是在模拟栈
• 队列：先进先出的特性与括号匹配的后进先出需求相反
• 链表：可以实现栈的功能，但代码复杂度较高

因此，直接使用栈是最自然和高效的选择。

算法思路

1. 初始化一个空栈
2. 遍历字符串中的每个字符
   • 如果是左括号（\'(\', \'[\', \'{\'），将其压入栈中
   • 如果是右括号（\')\', \']\', \'}\'），则：
     • 检查栈是否为空（空栈表示没有与之匹配的左括号）
     • 弹出栈顶元素并与当前右括号比较是否匹配
     • 如果不匹配，则字符串无效
3. 遍历完成后
   • 如果栈为空，说明所有括号都正确匹配
   • 如果栈不为空，说明有未匹配的左括号，字符串无效

算法正确性证明

该算法的正确性可以通过循环不变式来证明：

• 初始化：栈为空，表示尚未遇到任何未匹配的左括号
• 保持：每次处理右括号时，都与最近未匹配的左括号（栈顶）进行比较，确保匹配的正确性
• 终止：遍历完成后，栈为空当且仅当所有括号都正确匹配

代码实现解析

栈数据结构定义

typedef char STDataType;typedef struct Stack{ STDataType* a; // 动态数组存储栈元素 int top; // 栈顶指针 int capacity; // 栈容量}ST;

栈操作函数详细解析

1. 初始化栈：设置初始状态，指针和容量都为0

   void STInit(ST* pst){ assert(pst); pst->a = 0; pst->capacity = 0; pst->top = 0;}

2. 销毁栈：释放动态分配的内存，防止内存泄漏

   void STDestroy(ST* pst){ assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0;}

3. 入栈操作：检查容量并扩容，然后添加元素

   void STPush(ST* pst, STDataType x){ assert(pst); // 扩容逻辑 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror(\"realloc fail\"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++;}

4. 出栈操作：简单地将栈顶指针减1

   void STPop(ST* pst){ assert(pst); assert(pst->top > 0); // 确保栈不为空 pst->top--;}

5. 获取栈顶元素：返回栈顶指针前一个位置的元素

   STDataType STTop(ST* pst){ assert(pst); assert(pst->top > 0); // 确保栈不为空 return pst->a[pst->top - 1];}

6. 判断栈空：检查栈顶指针是否为0

   bool STEmpty(ST* pst){ assert(pst); return pst->top == 0;}

7. 获取栈大小：返回栈顶指针的值

   int STSize(ST* pst){ assert(pst); return pst->top;}

核心算法函数

bool isValid(char* s) { // 处理空指针情况 if (s == NULL) { return true; // 空指针视为有效，与空字符串处理一致 } ST st; STInit(&st); // 初始化栈 while(*s) // 遍历字符串 { // 左括号入栈 if(*s==\'(\'||*s==\'[\'||*s==\'{\') { STPush(&st,*s); } else // 处理右括号 { // 栈为空说明没有匹配的左括号 if(STEmpty(&st)) { STDestroy(&st); return false; } char top = STTop(&st); // 获取栈顶元素 STPop(&st); // 弹出栈顶元素 // 检查括号是否匹配 if((top==\'(\'&&*s!=\')\') ||(top==\'[\'&&*s!=\']\') ||(top==\'{\'&&*s!=\'}\')) { STDestroy(&st); return false; } } s++; // 移动到下一个字符 } // 检查栈是否为空（所有左括号都已匹配） bool ret = STEmpty(&st); STDestroy(&st); return ret;}

程序源码

typedef char STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;//初始化和销毁void STInit(ST* pst);void STDestroy(ST* pst);//入栈出栈void STPush(ST* pst, STDataType x);void STPop(ST* pst);//取栈顶数据STDataType STTop(ST* pst);//判空bool STEmpty(ST* pst);//获取数据个数int STSize(ST* pst);void STInit(ST* pst){assert(pst);pst->a = 0;pst->capacity = 0;pst->top = 0;}void STDestroy(ST* pst){assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}//入栈出栈void STPush(ST* pst, STDataType x){assert(pst);//扩容if (pst->top == pst->capacity){int newcapcacity =pst->capacity==0 ? 4 : pst->capacity * 2;//起始空间为0则申请4个空间 不为0则二倍STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));//pst->a为NULL时，realloc相当与mallocif (tmp == NULL){perror(\"realloc fail\");}pst->a = tmp;pst->capacity = newcapcacity;}pst->a[pst->top] = x;pst->top++;//top指向栈顶下一个元素}void STPop(ST* pst){assert(pst);pst->top--;}//取栈顶数据STDataType STTop(ST* pst){assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];}//判空bool STEmpty(ST* pst){assert(pst);return pst->top == 0;//==0就是空}//获取数据个数int STSize(ST* pst){assert(pst);return pst->top;}bool isValid(char* s) { ST st; STInit(&st); while(*s) { //左括号入栈 if(*s==\'(\'||*s==\'[\'||*s==\'{\') { STPush(&st,*s); } else//右括号 取栈顶左括号与右括号作比较 { //如果栈为空 说明不匹配 if(STEmpty(&st)) { STDestroy(&st); return false; } char top=STTop(&st); STPop(&st);  //如果判断匹配，还要继续比较，所以判断不匹配的情况 //栈不为空才能取 if((top==\'(\'&&*s!=\')\') ||(top==\'[\'&&*s!=\']\') ||(top==\'{\'&&*s!=\'}\')) {  STDestroy(&st);  return false;  }  }  s++; } bool ret=STEmpty(&st); STDestroy(&st); return ret; }

复杂度分析

• 时间复杂度：O(n)，其中n是字符串长度。每个字符最多被处理一次（入栈或与栈顶比较）。
• 空间复杂度：O(n)，最坏情况下需要将所有左括号都压入栈中。平均情况下，空间复杂度取决于括号的嵌套深度。

复杂度证明

时间复杂度为O(n)是显然的，因为算法只对字符串进行了一次线性扫描。

空间复杂度最坏情况下为O(n)，当输入字符串全是左括号时，需要将全部n个字符压入栈中。最好情况下为O(1)，当字符串是空或只有右括号时（会立即返回false）。平均情况下，空间复杂度取决于括号的嵌套深度，而不是字符串总长度。

示例演示

有效字符串示例

输入: “()[]{}”

执行过程:

1. ‘(’ 入栈 → 栈: [‘(’]
2. ‘)’ 与栈顶 ‘(’ 匹配 → 弹出 → 栈: []
3. ‘[’ 入栈 → 栈: [‘[’]
4. ‘]’ 与栈顶 ‘[’ 匹配 → 弹出 → 栈: []
5. ‘{’ 入栈 → 栈: [‘{’]
6. ‘}’ 与栈顶 ‘{’ 匹配 → 弹出 → 栈: []
7. 栈为空 → 返回 true

输入: “{[]}”

执行过程:

1. ‘{’ 入栈 → 栈: [‘{’]
2. ‘[’ 入栈 → 栈: [‘{’, ‘[’]
3. ‘]’ 与栈顶 ‘[’ 匹配 → 弹出 → 栈: [‘{’]
4. ‘}’ 与栈顶 ‘{’ 匹配 → 弹出 → 栈: []
5. 栈为空 → 返回 true

无效字符串示例

输入: “([)]”

执行过程:

1. ‘(’ 入栈 → 栈: [‘(’]
2. ‘[’ 入栈 → 栈: [‘(’, ‘[’]
3. ‘)’ 与栈顶 ‘[’ 不匹配 → 返回 false

输入: “((())”

执行过程:

1. ‘(’ 入栈 → 栈: [‘(’]
2. ‘(’ 入栈 → 栈: [‘(’, ‘(’]
3. ‘(’ 入栈 → 栈: [‘(’, ‘(’, ‘(’]
4. ‘)’ 与栈顶 ‘(’ 匹配 → 弹出 → 栈: [‘(’, ‘(’]
5. ‘)’ 与栈顶 ‘(’ 匹配 → 弹出 → 栈: [‘(’]
6. 遍历结束，栈不为空 → 返回 false

边界情况处理

算法考虑了多种边界情况：

1. 空字符串：栈初始为空，最终也为空，返回true
2. 只有左括号：遍历结束后栈不为空，返回false
3. 只有右括号：遇到右括号时栈为空，立即返回false
4. 交错括号：如\"([)]\"，会检测到不匹配的情况
5. 空指针输入：增加了对空指针的检查，返回true（与空字符串一致）

实际应用场景

括号匹配算法不仅在编程问题中出现，还有许多实际应用：

1. 编译器语法检查：检查代码中的括号是否匹配，是语法分析的重要组成部分
2. 表达式求值：确保算术表达式中的括号正确嵌套，是计算器程序的核心功能
3. JSON/XML解析：验证文档结构是否正确，是数据交换格式处理的基础
4. 文本编辑器：提供括号高亮和匹配功能，改善编程体验
5. 配置文件的解析：许多配置文件使用嵌套结构，需要括号匹配验证
6. 正则表达式引擎：处理正则表达式中的分组和捕获

扩展思考

支持更多括号类型

当前算法只支持三种括号类型，但可以轻松扩展以支持更多类型的括号，如尖括号、引号\" \"或\' \'等。只需要修改判断左括号和匹配条件的部分即可。

错误定位与反馈

在实际应用中，我们可能不仅需要知道字符串是否有效，还需要知道哪里出错。可以修改算法以提供更详细的错误信息，如错误位置和错误类型（缺少右括号、缺少左括号或括号不匹配）。

非栈解决方案

虽然栈是最自然的解决方案，但也可以使用其他方法：

• 递归下降：对于特别深的嵌套，递归可能更直观，但有栈溢出风险
• 计数器方法：对于只有一种括号的情况，可以使用简单的计数器，但对于多种括号不适用

性能优化

对于非常长的字符串，可以考虑：

• 提前终止：当发现不匹配时立即返回，不需要处理剩余字符
• 内存池：预先分配足够大的栈空间，避免多次扩容
• 并行处理：对于超长字符串，可以尝试分块并行处理（但括号匹配本质是顺序相关的，并行化困难）

总结

通过栈数据结构解决括号匹配问题是一个经典且高效的算法。该算法的时间复杂度和空间复杂度都是线性的，适用于大多数实际场景。理解这个问题的解决方案不仅有助于解决类似的栈应用问题，还能加深对数据结构选择和应用的理解。

掌握这种算法思维，能够帮助我们更好地解决许多需要\"后进先出\"处理顺序的问题，是编程中一种重要的思维方式。括号匹配问题虽然简单，但蕴含的栈思想却是许多复杂算法的基础，如深度优先搜索、递归函数的调用栈、回溯算法等。