如何在PHP中验证带有*运算符的括号字符串

Question

如何在PHP中验证带有*运算符的括号字符串

3

()*  -> 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);

- Nauman Ilyas

1

你能解释一下这背后的逻辑吗？如何判断某个东西是有效还是无效？ - nice_dev

嗨@nice_dev，我添加了我正在尝试解决这个问题的代码。 - Nauman Ilyas

有趣的尝试，但我认为有一种更简单的方法可以在不需要堆栈的情况下完成。*也可以被视为空格值，还是只能替换为(或)？ - nice_dev

1

是的，* 也可以被视为空格。 - Nauman Ilyas

1

(()()) 是有效的，因为在数学中每个开括号都有相应的闭括号，但如果我们改变顺序，那么就是无效的，比如 )()()(。@KevinY - Nauman Ilyas

显示剩余4条评论

2个回答

0

这是一种不同的方法，与原帖和@nice_dev的答案不同，即构建一个查找表，以防需要进行多个有效性检查：

// Generate an array of all possible patterns with length from minSize to maxSize
function generatePatterns(array $chars, int $minSize, int $maxSize): array {
  $count = count($chars);
  return array_map(
      fn($value) => implode('', $value),
      array_merge(
          ...array_map(
              fn($value) => array_map(
                  fn($element) => array_map(
                      fn($item) => $chars[intdiv($element, $count ** $item) % $count],
                      $range = range(0, $value - 1)
                  ),
                  range(0, ( count($chars) ** $value ) - 1)
              ),
              range($minSize, $maxSize)
          )
      )
  );
}

// Generate an array of pattern & validity pairs (key = pattern, value = true|false)
function getPatternsValidity(array $patterns): array {
  return array_merge(
      ...array_map(
          function ($pattern) {
            $countOfStars = substr_count($pattern, '*') ?? 0;
            if ($countOfStars === 0) {
              $tests = [ [ $pattern ] ];
            } else {
              $tests = array_map(
                  fn($value) => str_split($value),
                  array_filter(
                      generatePatterns([ '(', ')', ' ' ], $countOfStars, $countOfStars),
                      fn($item) => count(str_split($item)) === $countOfStars
                  )
              );
            }
            $retval[$pattern] = false;
            foreach ($tests as $test) {
              $testPattern = $pattern;
              foreach ($test as $char) {
                $offset = strpos($testPattern, '*');
                if ($offset !== false) {
                  $testPattern = substr_replace($testPattern, $char, $offset, 1);
                }
              }
              $sum = 0;
              $runningSum = array_map(
                  function ($value) use (&$sum) {
                    if ($value === '(') return ++$sum;
                    if ($value === ')') return --$sum;
                    return 0;
                  },
                  str_split($testPattern)
              );
              if ($sum === 0 && min($runningSum) >= 0) {
                $retval[$pattern] = true;
                break;
              }
            }
            return $retval;
          },
          $patterns
      )
  );
}

生成所有模式：

$allPatterns = generatePatterns([ '(', ')', '*' ], 1, 3);
print_r($allPatterns);

Array
(
    [0] => (
    [1] => )
    [2] => *
    [3] => ((
    [4] => )(
    [5] => *(
    [6] => ()
    [7] => ))
    [8] => *)
    [9] => (*
    [10] => )*
    [11] => **
    [12] => (((
    [13] => )((
    [14] => *((
    [15] => ()(
    [16] => ))(
    [17] => *)(
    [18] => (*(
    [19] => )*(
    [20] => **(
    [21] => (()
    [22] => )()
    [23] => *()
    [24] => ())
    [25] => )))
    [26] => *))
    [27] => (*)
    [28] => )*)
    [29] => **)
    [30] => ((*
    [31] => )(*
    [32] => *(*
    [33] => ()*
    [34] => ))*
    [35] => *)*
    [36] => (**
    [37] => )**
    [38] => ***
)

从生成的模式中构建模式/有效性对的数组：

$patternsValidity = getPatternsValidity($allPatterns);
print_r($patternsValidity);

Array
(
    [(] => 
    [)] => 
    [*] => 1
    [((] => 
    [)(] => 
    [*(] => 
    [()] => 1
    [))] => 
    [*)] => 1
    [(*] => 1
    [)*] => 
    [**] => 1
    [(((] => 
    [)((] => 
    [*((] => 
    [()(] => 
    [))(] => 
    [*)(] => 
    [(*(] => 
    [)*(] => 
    [**(] => 
    [(()] => 
    [)()] => 
    [*()] => 1
    [())] => 
    [)))] => 
    [*))] => 
    [(*)] => 1
    [)*)] => 
    [**)] => 1
    [((*] => 
    [)(*] => 
    [*(*] => 1
    [()*] => 1
    [))*] => 
    [*)*] => 1
    [(**] => 1
    [)**] => 
    [***] => 1
)

用作查找表的使用方法：

$isPatternValid1 = $patternsValidity['(*)'] ? 'yes' : 'no';
echo "isPatternValid1 '(*)' –> $isPatternValid1\n";

$isPatternValid2 = $patternsValidity[')**'] ? 'yes' : 'no';
echo "isPatternValid2 ')**' –> $isPatternValid2\n";

isPatternValid1 '(*)' –> yes
isPatternValid2 ')**' –> no

所有有效模式的数组：

$validPatterns = array_keys(array_filter($patternsValidity, fn($value) => $value, ARRAY_FILTER_USE_BOTH));
print_r($validPatterns);

Array
(
    [0] => *
    [1] => ()
    [2] => *)
    [3] => (*
    [4] => **
    [5] => *()
    [6] => (*)
    [7] => **)
    [8] => *(*
    [9] => ()*
    [10] => *)*
    [11] => (**
    [12] => ***
)

所有无效模式的数组：

$invalidPatterns = array_keys(array_filter($patternsValidity, fn($value) => !$value, ARRAY_FILTER_USE_BOTH));
print_r($invalidPatterns);

Array
(
    [0] => (
    [1] => )
    [2] => ((
    [3] => )(
    [4] => *(
    [5] => ))
    [6] => )*
    [7] => (((
    [8] => )((
    [9] => *((
    [10] => ()(
    [11] => ))(
    [12] => *)(
    [13] => (*(
    [14] => )*(
    [15] => **(
    [16] => (()
    [17] => )()
    [18] => ())
    [19] => )))
    [20] => *))
    [21] => )*)
    [22] => ((*
    [23] => )(*
    [24] => ))*
    [25] => )**
)

- lukas.j

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nice_dev · Accepted Answer

您可以使用以下 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;
}

在线演示