本文介绍一种高效算法，用于判断包含普通括号 (、) 和通配符 *（可代表左括号、右括号或空字符）的字符串是否能构成合法括号序列。

核心思路是两次扫描：首次贪心匹配右括号，第二次逆序验证剩余左括号能否被右侧星号覆盖。

遇到带通配符的括号匹配问题，传统的单栈做法很难兼顾所有情况。因为 * 不是单一角色，它既可以当作 (，也可以当作 )，还可以当作空字符。

正因为存在这种多重含义，处理时不能只看一种状态。需要同时照顾“最少还可能剩下多少个未匹配左括号”和“最多还可能剩下多少个未匹配左括号”这两个边界。

不过，这里的解法选择了更容易理解的两遍扫描法。它思路更顺，逻辑更清楚，实现起来也更省心。

算法整体思路

整个判断过程分为两个阶段：

• 第一遍正向扫描，优先处理所有 )；
• 第二遍逆向扫描，检查剩余 ( 是否都能被右侧的 * 覆盖。

第一遍解决“右括号有没有来源”，第二遍解决“剩余左括号能不能闭合”。

第一遍：正向扫描，优先消耗明确的右括号

遍历字符串时，维护两个变量：

• $open：存储所有 ( 出现位置的索引数组；
• $star：累计遇到的 * 数量。

字符处理规则

• 遇到 )：优先弹出一个 (（array_pop($open)）；
• 如果没有 (，则消耗一个 *（$star--）；
• 如果两者都没有，直接返回 false；
• 遇到 (：压入其索引到 $open；
• 遇到 *：$star++。

这一阶段的目标很明确：确保所有 ) 都能找到左侧支撑。这个支撑可以来自真实的 (，也可以来自 *。

第二遍：逆向扫描，验证剩余 ( 是否可被右侧 * 匹配

如果第一遍结束后 $open 已经为空，说明括号已经完全匹配，可以直接返回 true。

如果还有剩余的 (，就必须继续检查：它们右侧是否存在足够的 *，并且这些 * 能够充当 )。

具体做法

• 先将 $open 索引数组反转，使索引从大到小排列；
• 从字符串最右端开始遍历；
• 用 $ptr 指向当前待匹配的 (；
• 遇到 * 时，$star++，表示积累一个可用的右括号资源；
• 遇到 ( 且位置正好等于 $open[$ptr] 时，必须消耗一个 *；
• 如果此时没有可用的 *，直接返回 false。

这里的关键限制是：用于补右括号的 * 必须出现在对应 ( 的右侧。

完整实现代码

 0) {
$star--;
} else {
return false; // 无 '(' 也无 * 可配对 ')'
}
break;
case '(':
$open[] = $i;
break;
case '*':
$star++;
break;
}
}

// 若无剩余 '('，直接有效
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 → ')' 开头，无左侧支撑
?>

为什么单栈做法不够用

只记录 ( 的单栈方法，在普通括号匹配中没有问题。但面对 * 时，情况会复杂很多。

因为 * 可能扮演三种角色。若强行用单栈 + 映射表去覆盖所有组合，会导致状态快速膨胀，逻辑也会变得难以控制。

相比之下，两遍扫描法把问题拆开处理，更容易保证正确性，也更适合实际编码。

注意事项与总结

• 该算法时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况下存储所有 ( 索引）；
• * 的灵活性体现在两阶段分工：第一遍用作“兜底右括号”，第二遍用作“定向右括号”；
• 切勿尝试用单栈 + 映射表（如原提问中的 $mapping）模拟所有组合，会导致状态爆炸且逻辑不可控；
• 实际应用中，建议增加输入校验（如仅允许 (, ), * 字符），避免意外行为。

通过这种结构化两遍扫描，我们既能保证正确性，又保持了代码的可读性与可维护性，是解决通配符括号匹配问题的推荐实践。