Detailliertes Codebeispiel, wie PHP die Stack-Datenstruktur und den Bracket-Matching-Algorithmus implementiert

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 Anwendungskenntnisse, die benötigt werden. Freunde können sich auf

beziehen. Dieser Artikel beschreibt die Implementierung der Stapeldatenstruktur und des Bracket-Matching-Algorithmus basierend auf PHP. Die Details lauten wie folgt:

Der Stapel spiegelt „Last-In-First-Out“ wider, also LIFO. Die Warteschlange verkörpert das First-In-First-Out-Prinzip, also FIFO.

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 //尾出

Das obige ist der detaillierte Inhalt vonDetailliertes Codebeispiel, wie PHP die Stack-Datenstruktur und den Bracket-Matching-Algorithmus implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!