本文介绍一种高效算法，用于判断包含 *（可替代左括号、右括号或空字符）的字符串是否能构成合法括号序列，如 ()(* 有效而 ()* 无效，并提供完整可运行的 PHP 实现与关键逻辑解析。

本文介绍一种高效算法，用于判断包含 *（可替代左括号、右括号或空字符）的字符串是否能构成合法括号序列，如 ()(* 有效而 ()* 无效，并提供完整可运行的 PHP 实现与关键逻辑解析。

为什么单栈思路不够用

一旦括号匹配里引入了通配符 *，只靠传统的单栈思路（只记录 '('）就不够用了。

原因并不复杂。* 不是单一身份，它可以当作 '('，也可以当作 ')'，还可以直接视为空字符。

正因为如此，这类问题更适合用双阶段贪心策略处理。第一遍从前往后扫描，模拟“能早匹配就尽早匹配”；第二遍再从后往前检查，确认剩下的 '(' 是否都能被右侧的 '*' 兜住。

核心思路分两步

正向扫描（处理 ')' 优先匹配）

• 遇到 '('：压入索引栈，记录其位置，便于后续校验。
• 遇到 '*'：计数器 star++，暂存为备用资源。
• 遇到 ')'：优先弹出栈顶 '('；若栈空，则消耗一个 '*' 作为左括号；若两者皆无，直接返回 false。

反向校验（确保剩余 '(' 有足够右侧 '*' 匹配）

• 将 '(' 索引栈反转，使其按从右到左顺序排列。
• 从字符串末尾向前遍历，遇到 '*' 则 star++。
• 当遇到某个 '('（按栈中逆序位置），必须有至少一个 '*' 可用作其右括号，否则返回 false。
• 所有 '(' 均成功匹配，则返回 true。

完整可运行代码

 0) {
$star--;
} else {
return false;
}
}
}

// 若无剩余 '('，直接有效
if (empty($open)) {
return true;
}

// 第二阶段：反向扫描，验证剩余 '(' 是否能被右侧 '*' 匹配
$open = array_reverse($open); // 使索引从大到小排列
$star = 0;
$ptr = 0; // 指向下一个待匹配的 '(' 索引

for ($i = $len - 1; $i >= 0 && $ptr < count($open); $i--) {
if ($str[$i] === '*') {
$star++;
} elseif ($i === $open[$ptr]) {
if ($star === 0) {
return false; // 无可用 '*' 匹配该 '('
}
$star--;
$ptr++;
}
}

return true;
}

//  测试用例
var_dump(isValid("()*")); // false
var_dump(isValid("()(*"));// true
var_dump(isValid("*)()"));// true
var_dump(isValid("()**"));// true
var_dump(isValid(")("));// false
var_dump(isValid(")*"));// false
?>

关键特点与优势

• 核心策略清晰：先处理当前可匹配的右括号，再回头验证未匹配的左括号。
• 兼顾灵活性与正确性：充分利用 * 的三种可能身份，但不破坏括号匹配顺序。
• 适合实际开发：逻辑直观，代码可直接运行，便于在 PHP 项目中落地。

注意事项与优化提示

• 时间复杂度：O(n)，仅两次线性扫描；空间复杂度：O(k)，k 为 '(' 的数量（最坏情况为全 '('）。
• array_pop() / array_push() 在 PHP 中对索引数组高效，但若追求极致性能，可用整型变量替代栈（仅需计数），但本题需记录位置以支持第二阶段校验，故保留索引栈。
• 该算法严格遵循括号嵌套规则：* 不可“跨层”替代，即每个 * 最多服务一个 '(' 或 ')'，且匹配方向符合实际语法结构（左→右成对）。
• 实际项目中建议添加输入校验，如 is_string($str)、ctype_print($str) 等，避免非预期字符干扰逻辑。

通过此方案，你不仅能正确判定所有给定样例，还可稳健扩展至更复杂的含通配符表达式校验场景。

《夸克》非常好用的免费AI浏览器

下载APP查看