Jak zweryfikować wsporniki w równaniu ciąg w PHP

Question

Chodziłam jeśli ktoś dobry w PHP mógłby doradzić, w jaki sposób sprawdzić poprawność wsporniki w użądleniu ekspresyjnym tak:

(5 * 3 [ 6) - 6] 

który jest niewłaściwy wyraz. Potrzebuję do tego funkcji. Oto, co próbowałem do tej pory:

<?php 
function hasMatchedParenthesis($string) { 

$counter1 = 0; 
$counter2 = 0; 

$length = strlen($string); 

for ($i = 0;$i < $length; $i++) { 
    $char = $string[$i]; 
    if($char == '(') { 
     $counter1 ++; 
    } elseif($char == ')') { 
     $counter1 --; 
    } 

     for($j =0;$j < $length; $j++) { 
      $char = $string[$j]; 
      if($char == '[') { 
       $counter2 ++; 
     } elseif($char == ']') { 
       $counter2 --; 
     } 

     } 


    if($counter1 < 0 || $counter2 < 0) { 
     return false; 
    } 

} 

echo 'ok';; 

} 


hasMatchedParenthesis('[5] * 3 - (4 - 7 * [3-6])'); // this is ok! 

hasMatchedParenthesis('(5 * 3 [ 6) - 6]'); // this returns as TRUE, but it is not! 

?> 

Zarzuty pomogły mi rozwiązać problem "[6]"! Nie wiem jak to zrobić :(

Answer 1

Pierwszy pomysł, który przychodzi mi do głowy to użycie stosu. PHP udostępnia dwie funkcje do traktowania tablicy jako stosu: array_push i array_pop. Możemy wykorzystać je do stworzenia stos 0 (jesteśmy wewnątrz otworu () i 1 (jesteśmy wewnątrz [) i sprawdzić, kiedy wspornik zamykający mecze z ostatniej wartości możemy brzmieniu:

function hasMatchedParenthesis($string) { 
    $len = strlen($string); 
    $stack = array; 
    for ($i = 0; $i < $len; $i++) { 
     switch ($string[$i]) { 
      case '(': array_push($stack, 0); break; 
      case ')': 
       if (array_pop($stack) !== 0) 
        return false; 
      break; 
      case '[': array_push($stack, 1); break; 
      case ']': 
       if (array_pop($stack) !== 1) 
        return false; 
      break; 
      default: break; 
     } 
    } 
    return (empty($stack)); 
} 

Zauważmy, że można przedłużyć ten jakiejkolwiek innej pary znaków ze { i }:

case '{': array_push($stack, 2); break; 
case '}': 
    if (array_pop($stack) !== 2) 
     return false; 
break; 

Answer 2

Zwykłym sposobem sprawdzania poprawności takich reguł składniowych jest użycie Context-free grammar - zobacz examples, a znajdziesz dokładnie to, co próbujesz zrobić jako przykład :-) A ty może zastosować zasady takiej gramatyki za pomocą lexera, jak zauważył Mark Baker.
W swoim kodzie upewnisz się tylko, że liczba nawiasów otwierających odpowiada liczbie nawiasów zamykających i jest to usterka. Również jak już wskazano w moim komentarzu twój ostatni warunek powinien być

if ($counter1 != 0 || $counter2 != 0){ 
    return false; 
} 

W obecnym przypadku true zostanie zwrócone, gdy każdy z liczników jest >=0. Wypróbuj prosty przypadek hasMatchedParenthesis('[5] * 3 - (4 - 7 * [3-6');, który zwróci true, mimo że jest nieprawidłowy.

Answer 3

pisałem następujące realizację.

function check_brackets_balance($string, $bracket_map = false) { 
    $bracket_map = $bracket_map ?: [ '[' => ']', '{' => '}', '(' => ')' ]; 
    $bracket_map_flipped = array_flip($bracket_map); 
    $length = mb_strlen($string); 
    $brackets_stack = []; 
    for ($i = 0; $i < $length; $i++) { 
     $current_char = $string[$i]; 
     if (isset($bracket_map[$current_char])) { 
      $brackets_stack[] = $bracket_map[$current_char]; 
     } else if (isset($bracket_map_flipped[$current_char])) { 
      $expected = array_pop($brackets_stack); 
      if (($expected === NULL) || ($current_char != $expected)) { 
       return false; 
      } 
     } 
    } 
    return empty($brackets_stack); 
} 

Używa również stosu, ale pobiera mniej kodu i ma dodatkowy parametr dla własnego zestawu nawiasów.

check_brackets_balance('[5] * 3 - (4 - 7 * [3-6])'); // true 
check_brackets_balance('(5 * 3 [ 6) - 6]')); // false