如何在 PHP 中验证含星号 * 的括号字符串有效性-php教程-PHP中文网

如何在 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
编写健壮的PHP代码，规避类型转换陷阱、数组怪癖及常见安全漏洞。

下载

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

<?php function isValid(string $str): bool
{
    $star = 0;
    $open = []; // 存储 '(' 的索引
    $len = strlen($str);

    // 第一遍：正向扫描，处理 ')'
    for ($i = 0; $i < $len; ++$i) {
        $char = $str[$i];
        if ($char === ')') {
            if (!empty($open)) {
                array_pop($open);
            } elseif ($star > 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

⚠️ 注意事项：