>  기사  >  백엔드 개발  >  PHP는 스택 데이터 구조와 대괄호 일치를 구현합니다.

PHP는 스택 데이터 구조와 대괄호 일치를 구현합니다.

小云云
小云云원래의
2018-01-30 10:01:311508검색

스택은 후입선출 방식, 즉 LIFO를 구현합니다. 큐는 선입선출(FIFO)을 구현합니다. 이번 글에서는 주로 PHP에서 스택 데이터 구조와 대괄호 매칭 알고리즘을 구현하는 방법을 소개하며, PHP 배열 연산을 통해 스택 데이터 구조의 푸시와 팝을 예제 형식으로 분석하고, 스택 기반 대괄호 매칭 응용 기술도 소개합니다. 참조할 수 있어야 합니다. 모두에게 도움이 되기를 바랍니다.

이 문서의 예에서는 PHP를 기반으로 스택 데이터 구조와 대괄호 일치 알고리즘의 구현을 설명합니다. 참조를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

스택 작업:


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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.