How to validate brackets with * equation string in PHP

You can check for balance validity with 4 conditions:

• If there is a ), we should have at least 1 ( or * in our account so far, both would work.

• If there are enough * for ( to be paired with ).

• If there are still any * left, we can either use them as ( and ) pair or use them as empty spaces. Here, whether the leftover count is even or odd won't matter since we can substitute them as empty space.

• There could be leftover open braces at the end. For this to be balanced, we need to have * after them to pair them with ). So, we do another run in the end to check for it's validity.

Snippet:

<?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

This is a different approach than both the OP and @nice_dev's answer, namely to construct a lookup table once in case more than one validity check has to be done:

// 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
      )
  );
}

Generate all 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] => ***
)

Build array of pattern / validity pairs from the generated patterns:

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

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

Usage as lookup table:

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

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

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

Array of all valid patterns:

$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] => ***
)

Array of all invalid patterns:

$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] => )**
)