PHP implementiert die Stapeldatenstruktur und den Klammerabgleich

Der Stapel verkörpert Last-In-First-Out, also LIFO. Die Warteschlange verkörpert das First-In-First-Out-Prinzip, also FIFO. In diesem Artikel wird hauptsächlich die Implementierung der Stapeldatenstruktur und des Bracket-Matching-Algorithmus in PHP vorgestellt. Er analysiert anhand von Beispielen den Push- und Pop-Vorgang der Stack-Datenstruktur sowie die Fähigkeiten der Stack-basierten Bracket-Matching-Anwendung Ich brauche es und kann darauf verweisen. Ich hoffe, es kann jedem helfen.

Das Beispiel in diesem Artikel beschreibt die Implementierung der Stapeldatenstruktur und des Bracket-Matching-Algorithmus basierend auf PHP. Teilen Sie es allen als Referenz mit. Die Details lauten wie folgt:

Stapelbetrieb:

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

oder

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

Anwendungsfall: Überprüfen Sie, ob eine mathematische Formel 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. Ebenso kann er auch durch array_shift und array_unshift implementiert werden.

Anhang: Warteschlangenbetrieb

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

oder

array_unshift //头进
array_pop //尾出

Verwandte Empfehlungen:

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

Das obige ist der detaillierte Inhalt vonPHP implementiert die Stapeldatenstruktur und den Klammerabgleich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!