search
HomeBackend DevelopmentPHP TutorialPrinciple and usage of reverse Polish algorithm in PHP

This article mainly introduces the principle and usage of PHP reverse Polish algorithm. Interested friends can refer to it. I hope it will be helpful to everyone.

The general algorithm for converting an ordinary inorder expression into a reverse Polish expression is:

First, you need to allocate 2 stacks, one as a temporary storage operator stack S1 (including a End symbol), a reverse Polish stack S2 (empty stack) is used as input. The S1 stack can be put into the operator # with the lowest priority first. Note that the infix expression should end with the operator with the lowest priority. Other characters can be specified, not necessarily #. Take characters from the left end of the infix expression and proceed as follows in sequence:

(1) If the character taken out is an operand, the complete operand will be analyzed and the operand will be sent directly to the S2 stack; if What is taken out is an operator, and the current top of the S1 stack is (, then the current operator is directly put into the S1 stack.

(2) If the character taken out is an operator, then the operator is combined with the top of the S1 stack Element comparison, if the priority of the operator is greater than the priority of the operator on the top of the S1 stack, then the operator will be pushed into the S1 stack. Otherwise, the top operator on the S1 stack will be popped out and sent to the S2 stack until the S1 stack If the operator on the top of the stack has a priority lower than (excluding equal to) the operator's priority, the operator will be sent to the S1 stack.

(3) If the character taken out is "(", it will be sent directly to S1 The top of the stack.

(4) If the character taken out is ")", the operators between the "(" closest to the top of the S1 stack will be popped off the stack one by one and sent to the S2 stack in turn. At this time, discard "(".

(5) Repeat the above steps 1~4 until all input characters

(6) If the character taken out is "#", then Pop all the operators (excluding "#") in the S1 stack one by one and send them to the S2 stack in turn.

After completing the above steps, the S2 stack will output the result in reverse Polish style. However, S2 should do something Process in reverse order. Then you can calculate it according to the reverse Polish calculation method!

math_rpn.php file is as follows:

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

Summary: The above is The entire content of this article, I hope it will be helpful to everyone's study.

Related recommendations:

How to localize remote images in php

Testing methods and examples of PHP scripts

Summary sharing of PHP processing session functions

The above is the detailed content of Principle and usage of reverse Polish algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace("&nbsp;","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft