如何在 PHP 中验证含星号 * 的括号字符串有效性

本文介绍一种高效算法，用两个阶段扫描判断含 *（可作左括号、右括号或空字符）的字符串是否能构成合法括号序列，核心是贪心匹配与逆向补配结合。

本文介绍一种高效算法，用两个阶段扫描判断含 `*`（可作左括号、右括号或空字符）的字符串是否能构成合法括号序列，核心是贪心匹配与逆向补配结合。

在 PHP 里，像 "()*"、"*)()"、"()**" 这类带有通配符 * 的括号字符串，判断它是否“可平衡”，核心在于看能否找到一种替换方案：把每个 * 改成 '('、')'，或者直接当作空字符串处理，最终让整段括号严格配对。也正因为如此，这个问题没法直接照搬经典的栈匹配思路——后者更适合只包含 () 的标准场景。说白了，* 不是单一角色，它既可能在左括号不够时顶上去，也可能在左括号过多时充当右括号来抵消，必要时还可以完全忽略。

标准解法采用 两遍贪心扫描 策略，兼顾可行性与完备性：

第一遍：正向扫描——尽可能匹配右括号 )

• 维护一个数组 $open 记录所有 '(' 的位置（索引）；
• 用整型 $star 统计已遇到的 * 数量；
• 遇到 )：
  • 优先弹出一个 '('（array_pop($open)）；
  • 若无 '(' 可用，则消耗一个 * 作为 )（$star--）；
  • 若两者皆无，立即返回 false。
• 遇到 (：压入其位置到 $open；
• 遇到 *：$star++。

此阶段确保所有 ) 都被合法覆盖，但可能遗留未闭合的 '(' —— 这些必须由后续 * 来“闭合”。

第二遍：逆向扫描——为剩余 '(' 匹配右侧 *

• 将 $open 反转（array_reverse($open)），使其按从右到左顺序排列；
• 重置 $star = 0 和指针 $ptr = 0；
• 从字符串末尾向前遍历（$i = $len-1 → 0），同时遍历 $open：
  • 遇到 *：$star++；
  • 遇到某个 '('（即 $i === $open[$ptr]）：
    • 若此时 $star == 0，说明该 '(' 右侧无可用 * 作 )，返回 false；
    • 否则 --$star 并 ++$ptr，表示成功配对。

✅ 关键洞察：* 在第二遍中只作为右括号使用（因第一遍已将其尽可能用作左括号或空字符），从而避免歧义，保证逻辑唯一性。

以下是完整、可运行的 PHP 实现：

 0) {
$star--;
} else {
return false;
}
} elseif ($char === '(') {
$open[] = $i;
} else { // $char === '*'
$star++;
}
}

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

// 第二遍：逆向扫描，为剩余 '(' 匹配右侧 '*'
$open = array_reverse($open);
$star = 0;
$ptr = 0;

for ($i = $len - 1; $i >= 0 && $ptr 

⚠️ 注意事项：

• 时间复杂度 O(n)，空间复杂度 O(n)（最坏存所有 '(' 位置）；
• 不要尝试用单栈 + 多映射规则（如原提问中的 isValid() 辅助函数），易陷入状态爆炸或逻辑冲突；
• * 的灵活性必须通过分阶段职责分离来控制：第一遍保底消 )，第二遍精准补 (；
• 此算法已被 LeetCode #678 验证为最优解，适用于任意长度输入。

掌握该双阶段贪心策略，即可稳健处理所有含 * 的括号校验场景。