基于栈结构的贪心策略在有效括号问题中的应用与实现

摘要

有效括号问题是算法领域的经典基础问题，其核心要求是判断给定括号字符串是否满足类型匹配与顺序匹配的双重约束。本文提出一种基于栈结构的贪心算法解决方案，通过局部最优选择（即遇到右括号时立即匹配最近的左括号），实现全局有效性的判定。该算法时间复杂度为 O(n)，空间复杂度为 O(n)，在处理长度为 10^4 量级的字符串时仍具备高效性，可广泛应用于表达式解析、代码语法检查等场景。

关键词

有效括号；栈结构；贪心算法；字符串匹配

一、引言

在程序设计与数据结构领域，括号匹配是语法分析、表达式求值等功能的基础模块。有效括号的判定规则包含三点核心要求：一是左括号必须与同类型的右括号闭合；二是括号的闭合顺序必须正确；三是每个右括号都存在对应的左括号。

传统暴力枚举法通过嵌套循环检查括号的匹配关系，时间复杂度高达 O(n^2)，在处理长字符串时效率低下。而贪心算法的核心思想是每一步都做出局部最优的选择，从而希望最终得到全局最优解，恰好契合括号匹配“就近匹配”的内在逻辑。结合栈“后进先出”的特性，能够高效实现贪心策略的落地。

二、贪心算法设计思路

2.1 核心贪心策略

对于有效括号字符串，其任意一个右括号必须且只能与它左侧最近的未匹配左括号是同类型。这一局部最优特性是贪心策略的核心依据：遍历字符串时，遇到左括号则暂存，遇到右括号则立即匹配最近的左括号，若匹配失败则直接判定字符串无效。

2.2 数据结构选择

栈是实现该贪心策略的理想数据结构。原因如下：

1. 栈的“后进先出”特性，能够完美存储左括号的顺序，保证右括号优先匹配最近的左括号；

2. 栈的压入（push）与弹出（pop）操作的时间复杂度均为 O(1)，不会增加算法的额外时间开销。

三、算法实现

3.1 算法步骤

1. 初始化一个空的字符栈，用于存储遍历过程中遇到的左括号；

2. 遍历输入字符串的每个字符：

◦ 若当前字符是左括号 (、[、{，则将其压入栈中，等待后续匹配；

◦ 若当前字符是右括号 )、]、}，则执行以下操作：

◦ 检查栈是否为空，若为空则说明无匹配的左括号，直接返回 false；

◦ 弹出栈顶元素，判断其是否与当前右括号类型匹配，若不匹配则返回 false；

3. 遍历结束后，检查栈是否为空。若不为空，说明存在未闭合的左括号，返回 false；否则返回 true。