PHP implémente la structure de données de la pile et la correspondance entre crochets

La pile incarne le dernier entré, premier sorti, c'est-à-dire LIFO. La file d'attente incarne le premier entré, premier sorti, c'est-à-dire FIFO. Cet article présente principalement l'implémentation de la structure de données de pile et de l'algorithme de correspondance de parenthèses en PHP.Il analyse le push et le pop de la structure de données de pile via le fonctionnement de tableau PHP sous forme d'exemples, ainsi que les compétences d'application de correspondance de parenthèses basées sur la pile. j'en ai besoin, je peux y faire référence. J'espère que cela pourra aider tout le monde.

L'exemple de cet article décrit l'implémentation d'une structure de données de pile et d'un algorithme de correspondance entre crochets basé sur PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Opération de pile :

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

ou

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

Cas d'utilisation : Vérifiez si une formule mathématique est correcte, telle que {2*3[x*y+5+m*(i-j )/3]+k* (4+(t+9))}.

Analyse : L'exactitude d'un calcul se reflète dans la correspondance des différentes parenthèses. Si les parenthèses correspondent complètement, le calcul sera correct. Alors, comment vérifier la correspondance des parenthèses dans un calcul ? sur l'utilisation de règles régulières. Je n'arrive tout simplement pas à comprendre comment écrire cette expression régulière et comment implémenter la relation imbriquée. C'est là que la pile s'avère utile. Regardez le code ci-dessous.

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

La pile dans le code ci-dessus est implémentée par array_pop et array_push de la même manière, elle peut également être implémentée par array_shift et array_unshift ;

Pièce jointe : Opération de file d'attente

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

ou

array_unshift //头进
array_pop //尾出

Recommandations associées :

Explication complète de la façon dont PHP implémente des exemples de structure de données de pile

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!