php - 如何在 PHP 中使用 * 等式字符串验证括号

Question

()*  -> In-valid
()(* -> valid
*)() -> valid
()** -> valid
)(   -> In-valid
)*   -> In-valid

我尝试并坚持执行代码，因为我知道我们必须与 Stack 打交道，但我只是坚持在那里，PHP 专家可以做到这一点并 :) 并解释它。

• 输入将是类似“()*”的字符串。
• “*”可用作左右括号
• 左(左)括号在有效表达式中应有右(右)括号。

我试着用下面的代码来做，不知道我的方向是否正确:)

$scenario = "()*";
$stackOne = str_split($scenario);
$stackTwo = array();
$counter = 1;
function push(array $arr, ?string $value)
{
    $arr[] = $value;
    return $arr;
}

function pop(array $arr)
{
    $count = count($arr) -1;
    if ($count > 0) unset($arr[$count]);
    return $arr;
}

function isValid(array $arr,string $value)
{
    $mapping= [
        "*" => ["(", ")", "*"],
        "(" => ["*", ")"],
        ")" => ["*", "("],
    ];
    if (empty($arr)) return "push";
    dd($arr[count($arr) - 1]);
    if(in_array($arr[count($arr) - 1] ,$mapping[$value])) return "pop";
}

foreach ($stackOne as $key => $value) {
    $output = isValid($stackTwo, $value);
    if ($output === "push") {
        $stackTwo = push($stackTwo, $value);
    } elseif ($output === "pop") {
        $stackTwo = pop($stackTwo);
    }
}

print_r($stackTwo);

Answer 1

您可以使用 4 个条件检查余额有效性:

• 如果有 )，那么到目前为止，我们的帐户中应该至少有 1 个 ( 或 *，两者都会工作。

• 如果有足够的 * 供 ( 与 配对)。

• 如果还有 * 剩余，我们可以将它们用作 ( 和 ) 对或将它们用作空空间。在这里，剩余的计数是偶数还是奇数都无关紧要，因为我们可以将它们替换为空白。

• 末尾可能有剩余的左大括号。为了达到平衡，我们需要在它们之后加上 * 以将它们与 ) 配对。因此，我们最后再运行一次以检查其有效性。

片段:

<?php

function isValid($str){
    $star = 0;
    $open = [];
    $len = strlen($str);
    
    for($i = 0; $i < $len; ++$i){
        if($str[ $i ] == ')'){
            if(count($open) > 0) array_pop($open);
            elseif($star > 0) $star--;
            else return false;
        }elseif( $str[ $i ] == '('){
            array_push($open, $i);
        }else{
            $star++;
        }
    }
    
    if(count($open) === 0) return true;
    // check leftover open braces from the back
    $star = $ptr = 0;
    $open = array_reverse($open);
    
    for($i = $len - 1; $i >= 0 && $ptr < count($open); --$i){
        if($str[ $i ] == '*'){
            $star++;
        }else if($i == $open[ $ptr ]){
            if($star == 0) return false;
            $star--;
            $ptr++;
        }
    }
    
    return true;
}

Online Demo