PHP如何实现带*通配符的括号字符串有效性校验

给定测试用例预期结果 #

()*  -> 无效
()(* -> 有效
*)() -> 有效
()** -> 有效
)(   -> 无效
)*   -> 无效

基础规则 #

• 输入为仅包含(、)、*三种字符的字符串
• 字符*只能被当作左括号或者右括号参与匹配，不可作为空字符忽略
• 合法表达式需满足：所有左括号（包括*转换的左括号）必须有对应的右括号匹配，遍历全程不能出现无匹配的前置右括号

原有代码的问题 #

你之前写的实现存在几个核心逻辑错误，无法得到正确结果：

1. 自定义栈方法逻辑缺陷：pop方法里if ($count > 0)的判断会导致栈仅剩1个元素时无法弹出，且PHP数组使用unset删除尾元素后不会重建索引，后续取栈顶元素时容易取到已删除的内容
2. 匹配映射逻辑错误：仅通过栈顶元素和当前字符的映射关系决定弹栈/入栈，没有考虑括号匹配的顺序要求，也没有处理*的二义性问题
3. 单栈结构无法承载*的多可能性：*有两种转换方向，单栈只能记录确定的匹配状态，无法覆盖所有可能的合法匹配路径

最优实现方案（区间计数法） #

不需要使用栈，时间复杂度O(n)，空间复杂度O(1)，逻辑比栈实现更简洁。

核心原理 #

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

• $low：将所有*都当作右括号时，当前未匹配的左括号数量（即最少剩余未匹配左括号数）
• $high：将所有*都当作左括号时，当前未匹配的左括号数量（即最多剩余未匹配左括号数）
  所有合法的未匹配左括号数一定落在[$low, $high]区间内，遍历过程中只要区间没有出现全负（说明右括号多到所有当左括号都补不上），且最终区间能覆盖0，同时字符串长度为偶数（因为每个字符都要参与匹配，总括号数必须是偶数才能左右相等），就说明存在合法的转换方式让表达式有效。

PHP实现代码 #

function isBracketValid(string $str): bool
{
    $len = strlen($str);
    // 总长度为奇数时，左右括号数量不可能相等，直接返回无效
    if ($len % 2 !== 0) {
        return false;
    }
    $low = 0;
    $high = 0;
    for ($i = 0; $i < $len; $i++) {
        $char = $str[$i];
        if ($char == '(') {
            $low++;
            $high++;
        } elseif ($char == ')') {
            $low--;
            $high--;
        } else { // 遇到*，分别按当右括号、当左括号更新计数
            $low--;
            $high++;
        }
        // 就算所有*都当左括号，右括号还是多，直接判定无效
        if ($high < 0) {
            return false;
        }
        // 未匹配左括号数不能为负，负数说明多余的右括号不可能被匹配，将low重置为0
        $low = max($low, 0);
    }
    // 最终最少剩余未匹配左括号为0，说明存在合法匹配路径
    return $low == 0;
}

// 验证测试用例
$testCases = [
    "()*" => false,
    "()(*" => true,
    "*)()" => true,
    "()**" => true,
    ")(" => false,
    ")*" => false
];

foreach ($testCases as $case => $expect) {
    $result = isBracketValid($case);
    echo sprintf(
        "输入：%s，判定结果：%s，预期结果：%s，校验%s\n",
        $case,
        $result ? "有效" : "无效",
        $expect ? "有效" : "无效",
        $result === $expect ? "通过" : "不通过"
    );
}

执行逻辑说明 #

1. 先做奇偶校验快速剪枝，长度为奇数直接返回无效
2. 逐字符遍历更新高低计数位，一旦$high小于0说明右括号溢出，直接返回无效
3. 每步将$low和0取最大值，排除不可能合法的负数值
4. 遍历完成后判断$low是否为0，为0则说明可以通过调整*的角色让所有括号完全匹配

如果更习惯栈的实现思路，也可以用双栈方案：一个栈存储真实左括号的索引，一个栈存储*的索引，遇到右括号时优先匹配真实左括号栈，左括号栈为空则匹配*栈，两个栈都空直接返回无效；遍历完成后再依次弹出两个栈的元素，要求左括号的索引必须小于*的索引（保证*在左括号右侧，可以当右括号匹配），最终左括号栈为空则判定有效，逻辑和计数法一致但空间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者Nauman Ilyas