Exemple de code détaillé de la façon dont PHP implémente la structure de données de pile et l'algorithme de correspondance entre crochets

Cet article présente principalement la structure de données de la pile et l'algorithme de correspondance des supports basés sur PHP. Il analyse le fonctionnement du tableau PHP pour réaliser le push et le pop de la structure de données de la pile sous forme d'exemples, ainsi que le support basé sur la pile. compétences d'application correspondantes, qui sont nécessaires Les amis peuvent se référer à

Cet article décrit la mise en œuvre de la structure de données de pile et de l'algorithme de correspondance de crochets basé sur PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Stack reflète le dernier entré, premier sorti, c'est-à-dire LIFO. La file d'attente incarne le premier entré, premier sorti, c'est-à-dire FIFO.

Fonctionnement de la 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 //尾出

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!