PHP reverse Polish salary calculation example

PHP How to use reverse Polish notation for salary calculation. This article mainly introduces the method of calculating wages using reverse Polish algorithm in PHP, and analyzes the principles and related usage techniques of PHP reverse Polish algorithm with examples. I hope to be helpful.

The example in this article describes the method of calculating wages using reverse Polish style in PHP. Share it with everyone for your reference. The details are as follows:

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 an end symbol), a reverse Polish stack S2 (empty stack) 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, the operator will be sent to the S1 stack

(3) If the character taken out is "(", it will be sent directly to S1. 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 out 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 have been processed

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

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

Related recommendations:

php Binary tree traversal algorithm and examples

php Algorithm to split array without array_chunk()_PHP tutorial

php implements event candidate lottery function code

The above is the detailed content of PHP reverse Polish salary calculation example. For more information, please follow other related articles on the PHP Chinese website!