Detailed code example of how PHP implements stack data structure and bracket matching algorithm

This article mainly introduces the stack data structure and bracket matching algorithm based on PHP. It analyzes the PHP array operation to realize the push and pop of the stack data structure in the form of examples, as well as the stack-based bracket matching application skills. Required Friends can refer to the following

The example of 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 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 example: 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 //尾出

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