Beispielerklärung der PHP-Stack-Datenstruktur und des Bracket-Matching-Algorithmus

Dieser Artikel stellt hauptsächlich die auf PHP basierende Stapeldatenstruktur und den Bracket-Matching-Algorithmus vor. Er analysiert die PHP-Array-Operation, um das Push und Pop der Stack-Datenstruktur sowie die stapelbasierte Klammer zu realisieren Passende Anwendungsfähigkeiten können Freunde, die es benötigen. Als Referenz hoffe ich, dass es allen helfen kann.

Stack spiegelt Last-In-First-Out wider, also LIFO. Die Warteschlange verkörpert das First-In-First-Out-Prinzip, also FIFO.

Stapeloperation:

array_pop() //尾出
array_push() //尾进

oder

array_shift()//头进
array_unshift()//头出

Anwendungsfall: Überprüfen Sie, ob eine mathematische Berechnung korrekt ist, z. B. {2*3[x*y+ 5+m *(i-j)/3]+k*(4+(t+9))}.

Analyse: Die Richtigkeit einer Berechnung spiegelt sich in der Übereinstimmung verschiedener Klammern wider. Wie kann man also die Übereinstimmung der Klammern in einer Berechnung überprüfen? über die Verwendung regelmäßiger Regeln. Ich kann einfach nicht herausfinden, wie ich diesen regulären Ausdruck schreiben und die verschachtelte Beziehung implementieren soll. Hier kommt der Stapel zum Einsatz. Schauen Sie sich den Code unten an.

function checkMatch($str){
  if(!$str)return false;
  $arr = str_split($str);
  $left = array('{','[','(');
  $right = array('}',']',')');
  $stack = array();
  reset($arr);  //使用while遍历数组需要先reset()，防止遍历不完整
  while(list($key, $val) = each($arr)){
    if(in_array($val,$left,true)){
      //入栈
      array_push($stack,$val); //把出现的全部左括号压入栈中
    }else if(in_array($val,$right,true)){
      $topStack = end($stack); //如果出现右括号，则栈顶的元素肯定是与其匹配的左括号(因为括号是对应的)，先取出栈顶元素。
      if(isset($topStack) && !empty($topStack)){
        if(array_search($val,$right,true) === array_search($topStack,$left,true)){ //判断当前右括号是不是与左括号匹配
          //出栈
          array_pop($stack); //匹配的话就pop出栈
        }else{
          //
          return false; //左右不匹配
        }
      }else{
        //
        return false; //右括号多，因为没取出对应的左括号
      }
    }
  }
  return empty($stack) ? true : false;  //循环完成后判断$stack中是否还有值，有的话证明左括号多
}
$test = '{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}';
var_dump ( checkMatch ( $test ) );

Der Stapel im obigen Code wird durch array_pop und array_push implementiert; in ähnlicher Weise kann er auch durch array_shift und array_unshift implementiert werden.

Anhang: Warteschlangenbetrieb

array_shift() //头出
array_push() //尾进

oder

array_unshift //头进
array_pop //尾出

Verwandte Empfehlungen;

Beispiel einer von PHP implementierten Stapeldatenstruktur【 Enter Stack, Pop, Traverse Stack]_php-Fähigkeiten

Umfassende und detaillierte Erklärung, wie PHP Beispiele für Stack-Datenstrukturen implementiert

Verwendung von Arrays zur Implementierung Stapeldaten im PHP-Strukturcode_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonBeispielerklärung der PHP-Stack-Datenstruktur und des Bracket-Matching-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!