Come convalidare le staffe in stringa un'equazione in PHP

Question

mi aggiravo se qualcuno bene in PHP potrebbe consigliare su come convalidare le staffe in un pungiglione espressione come questa:

(5 * 3 [ 6) - 6] 

che è l'espressione sbagliata. Ho bisogno di una funzione per farlo. Ecco cosa ho provato fino ad ora:

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

?> 

Le parole mi aiutano a risolvere la convalida della cosa [6]! Non so come farlo :(

Answer 1

La prima idea che mi viene in mente è quello di utilizzare una pila. PHP fornisce due funzioni per trattare un array come una pila: array_push e array_pop. possiamo utilizzare per creare una pila di 0 (siamo all'interno un'apertura () e 1 (siamo dentro un [) e controllare ogni volta una staffa di chiusura corrisponde con l'ultimo valore abbiamo inserito:

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

noti che è possibile estendere questo a qualsiasi altra coppia di personaggi, tra cui { e }:

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

Answer 2

Il modo usuale di convalidare tali regole sintattiche è usare un Context-free grammar - vedere lo examples e troverai esattamente quello che stai cercando di fare come esempio :-) E tu può applicare le regole di una tale grammatica usando un lexer come indicato da Mark Baker.
In voi il codice si sta solo facendo in modo che il numero di staffe di apertura corrisponde al numero di parentesi di chiusura e che è il difetto. Inoltre, come ho sottolineato nel mio commento l'ultima condizione dovrebbe essere

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

Nel tuo caso attuale true verrà restituito quando uno qualsiasi dei contatori è >=0. Prova con un semplice caso hasMatchedParenthesis('[5] * 3 - (4 - 7 * [3-6');, che restituirà true anche se è sbagliato.

Answer 3

ho scritto successiva realizzazione.

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

Utilizza anche stack, ma richiede meno codice e ha parametri aggiuntivi per le proprie parentesi impostate.

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