ホームページ > 記事 > バックエンド開発 > PHP における逆ポーランド語アルゴリズムの原理と使用法

PHP における逆ポーランド語アルゴリズムの原理と使用法

墨辰丷オリジナル: 2018-06-08 10:13:102435ブラウズ

この記事では主に PHP 逆ポーランド語アルゴリズムの原理と使用法を紹介します。興味のある方はぜひ参考にしてください。

通常の inorder 式を逆ポーランド式に変換するための一般的なアルゴリズムは次のとおりです。

まず、2 つのスタックを割り当てる必要があります。1 つは一時記憶演算子スタック S1 (End シンボルを含む) として割り当てられます。 )、逆ポーランド語スタック S2 (空のスタック) が入力として使用されます。S1 スタックは、最初に優先順位の低い演算子 # に入れることができます。中置式は優先順位の最も低い演算子で終わる必要があることに注意してください。 # である必要はなく、他の文字も指定できます。中置式の左端から文字を取り出し、次のように順番に処理します。

(1) 取り出した文字がオペランドの場合、完全なオペランドが分析され、オペランドが直接関数に送信されます。 S2 スタック; 取り出されたものが演算子であり、S1 スタックの現在の先頭が ( の場合、現在の演算子は直接 S1 スタックに入れられます。

(2) 取り出された文字がの場合演算子の場合、その演算子は S1 スタックの最上位と結合されます。要素の比較。演算子の優先順位が S1 スタックの最上位の演算子の優先順位より大きい場合、演算子は S1 スタックにプッシュされます。それ以外の場合、S1 スタックの最上位の演算子がポップアウトされ、S1 スタックがその演算子よりも優先順位が低い (等しいを除く) まで S2 スタックに送信されます。 S1 スタックに送信

(3) 取り出した文字が「(」の場合は、そのまま S1 に送信されます。スタックの先頭です。

(4) 文字が「(」の場合、S1 に直接送信されます。取り出されるのが ")" の場合、S1 スタックの先頭に近い "(" の間の演算子が 1 つずつスタックからポップされ、順番に S2 スタックに送られます。このとき、"(" は破棄します。

(5) 入力文字がすべて揃うまで上記 1 ～ 4 を繰り返す

(6) 取り出した文字が "#" の場合、S1 スタックにあるすべての演算子 (" を除く) をポップします。 #") を 1 つずつ実行し、順番に 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 における逆ポーランド語アルゴリズムの原理と使用法

関連記事