PHP 스택 데이터 구조 및 대괄호 일치 알고리즘에 대한 예제 설명

이 글에서는 주로 PHP 기반의 스택 데이터 구조와 대괄호 매칭 알고리즘을 소개하고, 스택 데이터 구조의 푸시와 팝을 구현하는 PHP 배열 연산과 스택 기반 대괄호 매칭 애플리케이션을 예시로 소개합니다. 도움이 필요한 친구들은 다음을 참고하여 모두에게 도움이 되기를 바랍니다.

스택은 후입선출 방식, 즉 LIFO를 구현합니다. 큐는 선입선출(FIFO)을 구현합니다.

스택 작업:

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

또는

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

사용 사례: 수학 공식이 올바른지 확인합니다(예: {2*3[x*y+5+m*(i-j)/3]+k*(4+) (t+ 9))}.

분석: 계산의 정확성은 다양한 괄호의 일치에 반영됩니다. 괄호가 완전히 일치하면 계산이 잘 될 것입니다. 그러면 계산에서 괄호의 일치를 확인하는 방법을 사용한다고 생각하는 사람들을 많이 만났습니다. 규칙적인 규칙. 이 정규 표현식을 작성하는 방법과 중첩 관계를 구현하는 방법을 알 수 없습니다. 이것이 스택이 유용한 곳입니다. 아래 코드를 보세요.

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

위 코드의 스택은 array_pop 및 array_push로 구현되며 마찬가지로 array_shift 및 array_unshift로도 구현할 수 있습니다.

첨부파일: 대기열 작업

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

또는

array_unshift //头进
array_pop //尾出

관련 권장 사항

PHP에서 구현한 스택 데이터 구조의 예 [스택에 밀어넣기, 스택에서 튀어나오기, 스택 트래버스]_php 기술

포괄적이고 자세한 설명 PHP가 스택 데이터 구조를 구현하는 방법 예제

PHP_PHP 튜토리얼에서 배열을 사용하여 스택 데이터 구조를 구현하는 코드

위 내용은 PHP 스택 데이터 구조 및 대괄호 일치 알고리즘에 대한 예제 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!