PHP에서 역 폴란드어 알고리즘의 원리와 사용법

이 글은 주로 PHP 역 폴란드어 알고리즘의 원리와 사용법을 소개합니다. 관심 있는 친구들이 참고하면 좋습니다.

일반 중위 표현식을 역 폴란드 표현식으로 변환하는 일반적인 알고리즘은 다음과 같습니다.

먼저 스택 2개를 할당해야 합니다. 하나는 임시 저장 연산자 스택 S1(끝 기호 포함)으로, 다른 하나는 입력 역으로 할당해야 합니다. 폴란드어 스택 S2(빈 스택), S1 스택은 우선 순위가 가장 낮은 연산자 #에 먼저 들어갈 수 있습니다. 중위 표현식은 우선 순위가 가장 낮은 연산자로 끝나야 합니다. 다른 문자를 지정할 수 있지만 반드시 #일 필요는 없습니다. 중위 표현식의 왼쪽 끝에서 문자를 가져와서 다음과 같이 단계별로 진행합니다.

(1) 빼낸 문자가 피연산자이면 전체 피연산자가 분석되고 피연산자가 S2 스택으로 직접 전송됩니다. 꺼낸 문자가 연산 문자이고 현재 S1 스택의 최상위가 (이면 현재 연산자가 S1 스택에 직접 푸시됩니다.

(2) 꺼낸 문자가 연산자인 경우 연산자를 다음과 비교합니다. S1 스택의 최상위 요소 연산자가 우선순위를 갖는 경우 S1 스택 맨 위에 있는 연산자의 우선순위가 S1 스택에 있는 연산자의 우선순위보다 높으면 S1 스택 맨 위에 있는 연산자가 우선순위가 됩니다. S1 스택 상단의 연산자가 다음보다 낮을 때까지(같지 않음) S2 스택으로 전송됩니다. 연산자 우선 순위는 S1 스택으로 전송됩니다.

(3) 가져온 문자가 "( "이면 S1 스택의 맨 위로 바로 전송됩니다.

(4) 꺼낸 문자가 "("이면 S1 스택의 맨 위로 전송됩니다. 문자가 ")"이면 연산자는 S1 스택의 최상단에 가장 가까운 "(" 사이에 있는 "("는 스택에서 하나씩 팝되어 S2 스택으로 차례로 전송됩니다. 이때 "("는 폐기됩니다.

(5) 위의 1단계를 반복합니다. 입력 문자가 모두 처리될 때까지 ~4단계

(6) 빼낸 문자가 "#"이면 S1 스택의 모든 연산자("#" 제외)를 하나씩 팝하고 차례로 S2 스택으로 보냅니다.

위 단계를 완료하면 S2 스택은 역폴란드 형식으로 결과를 출력합니다. 그러나 S2는 역폴란드 계산 방법에 따라 계산할 수 있습니다.

math_rpn.php 파일은 다음과 같습니다.

<?php
/**
 * math_rpn 
 *
 * 实现逆波兰式算法
 *  
 */
class math_rpn {
  //初始的计算表达式
  private $_expression = &#39;&#39;;
  //处理后的逆波兰表达式
  private $_rpnexp = array();
  //模拟栈结构的数组
  private $_stack = array(&#39;#&#39;);
  //正则判断
  //private $_reg  = &#39;/^([A-Za-z0-9\(\)\+\-\*\/])*$/&#39;;
  //优先级
  private $_priority = array(&#39;#&#39; => 0, &#39;(&#39; => 10, &#39;+&#39; => 20, &#39;-&#39; => 20, &#39;*&#39; => 30, &#39;/&#39; => 30);
  //四则运算
  private $_operator = array(&#39;(&#39;, &#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;, &#39;)&#39;);
  public function __construct($expression) {
    $this->_init($expression);
  }
  private function _init($expression) {
    $this->_expression = $expression;
  }
  public function exp2rpn() {
    $len = strlen($this->_expression);
    for($i = 0; $i < $len; $i++) {
      $char = substr($this->_expression, $i, 1);
      if ($char == &#39;(&#39;) {
        $this->_stack[] = $char;
        continue;
      } else if ( ! in_array($char, $this->_operator)) {
        $this->_rpnexp[] = $char;
        continue;
      } else if ($char == &#39;)&#39;) {
        for($j = count($this->_stack); $j >= 0; $j--) {
          $tmp = array_pop($this->_stack);
          if ($tmp == "(") {
            break; 
          } else {
            $this->_rpnexp[] = $tmp;
          }
        }
        continue;
      } else if ($this->_priority[$char] <= $this->_priority[end($this->_stack)]) {
        $this->_rpnexp[] = array_pop($this->_stack);
        $this->_stack[] = $char;
        continue;
      } else {
        $this->_stack[] = $char;
        continue;
      }
    }
    for($i = count($this->_stack); $i >= 0; $i--) {
      if (end($this->_stack) == &#39;#&#39;) break;
      $this->_rpnexp[] = array_pop($this->_stack); 
    }
    return $this->_rpnexp;
  }
}
//测试实例
$expression = "(A*(B+C)-E+F)*G";
var_dump($expression);
$mathrpn = new math_rpn($expression);
var_dump($mathrpn->exp2rpn());
/*End of php*/

요약: 위 내용은 이 기사의 전체 내용입니다. 모든 사람의 학습에 도움이 되기를 바랍니다.

관련 권장 사항:

php 원격 이미지 현지화 방법

PHP 스크립트 테스트 방법 예.

PHP 처리 세션 기능 요약 공유

위 내용은 PHP에서 역 폴란드어 알고리즘의 원리와 사용법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!