Principe et utilisation de l'algorithme polonais inversé en PHP

Cet article présente principalement le principe et l'utilisation de l'algorithme PHP inversé. Les amis intéressés peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

L'algorithme général pour convertir une expression d'ordre ordinaire en une expression polonaise inverse est :

Tout d'abord, vous devez allouer 2 piles, une comme pile d'opérateur de stockage temporaire S1 (comprenant un symbole de fin ), une pile polonaise inversée S2 (pile vide) est utilisée comme entrée. La pile S1 peut être placée en premier dans l'opérateur # avec la priorité la plus basse. D'autres caractères peuvent être spécifiés, pas nécessairement #. Prenez les caractères à l'extrémité gauche de l'expression infixe, et procédez comme suit étape par étape :

(1) Si le caractère retiré est un opérande, l'opérande complet sera analysé et l'opérande sera envoyé directement dans la pile S2 ; si ce qui est retiré est un opérateur et que le sommet actuel de la pile S1 est (, alors l'opérateur actuel est directement placé dans la pile S1.

(2) Si le caractère retiré est un opérateur, alors l'opérateur est combiné avec le haut de la pile S1 Comparaison d'éléments, si la priorité de l'opérateur est supérieure à la priorité de l'opérateur au sommet de la pile S1, alors l'opérateur sera poussé dans la pile S1. Sinon, l'opérateur du haut de la pile S1 sera retiré et envoyé à la pile S2 jusqu'à la pile S1. Si l'opérateur en haut de la pile a une priorité inférieure (sauf égale à) l'opérateur, le l'opérateur sera envoyé vers la pile S1

(3) Si le caractère retiré est "(", il sera envoyé directement vers S1. Le haut de la pile.

(4) Si le caractère retiré est ")", les opérateurs entre les "(" les plus proches du haut de la pile S1 seront retirés de la pile un par un et envoyés tour à tour vers la pile S2. À ce moment, jetez "( ".

(5) Répétez les étapes 1 à 4 ci-dessus jusqu'à ce que tous les caractères saisis soient traités

(6) Si le caractère supprimé est "#", alors affichez tous les opérateurs dans le Empilez S1 (à l'exclusion de "#") un par un et envoyez-les à la pile S2 dans l'ordre

Après avoir terminé les étapes ci-dessus, la pile S2 affichera le résultat au format polonais inversé. Cependant, S2 devrait faire l'affaire. quelque chose. Processus dans l'ordre inverse. Ensuite, vous pouvez le calculer selon la méthode de calcul polonaise inversée ! Ce qui précède est l'intégralité du contenu de cet article, j'espère qu'il sera utile à l'apprentissage de tout le monde

Recommandations associées. :

<?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*/

Comment localiser des images distantes en PHP

Méthodes de tests et exemples de scripts PHP

Partage récapitulatif des fonctions de session de traitement PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!