Example explanation of PHP stack data structure and bracket matching algorithm

This article mainly introduces the implementation of stack data structure and bracket matching algorithm based on PHP. It analyzes PHP array operations to realize the push and pop of stack data structure in the form of examples, as well as stack-based bracket matching application skills. Friends who need it can For reference, I hope it can help everyone.

The stack reflects last-in-first-out, that is, LIFO. Queue embodies first-in-first-out, that is, FIFO.

Stack operation:

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

or

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

Use case: Verify whether a mathematical formula is correct, such as {2*3[x*y+5+m*(i-j) /3]+k*(4+(t+9))}.

Analysis: The correctness of a calculation is reflected in the matching of various brackets. If the brackets match completely, the calculation will be fine. So how to check the matching of brackets in a calculation? Many people think about using regular rules. I just can't figure out how to write this regular expression and how to implement the nested relationship. This is where the stack comes in handy. Look at the code below.

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

The stack in the above code is implemented by array_pop and array_push; similarly, it can also be implemented by array_shift and array_unshift.

Attachment: Queue operation

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

or

array_unshift //头进
array_pop //尾出

related recommendations;

Example of stack data structure implemented by PHP [Push into stack, pop out of stack , Traverse the stack]_php skills

Comprehensive and detailed explanation of how to implement the stack data structure in PHP

Code for using arrays to implement the stack data structure in PHP_ PHP tutorial

The above is the detailed content of Example explanation of PHP stack data structure and bracket matching algorithm. For more information, please follow other related articles on the PHP Chinese website!