PHP implements stack data structure and bracket matching

The stack reflects last-in-first-out, that is, LIFO. Queue embodies first-in-first-out, that is, FIFO. This article mainly introduces the implementation of stack data structure and bracket matching algorithm in PHP. It analyzes the push and pop of stack data structure through PHP array operation in the form of examples, as well as stack-based bracket matching application skills. Friends who need it can refer to it. I hope it can Help everyone.

The example in this article describes the implementation of stack data structure and bracket matching algorithm based on PHP. Share it with everyone for your reference, the details are as follows:

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:

Comprehensive and detailed explanation of how PHP implements stack data structure examples

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