PHP uses reverse Polish method to calculate salary_php tips

The example in this article describes how PHP uses reverse Polish to calculate wages. 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 a terminator), and one as an input reverse Polish stack S2 (empty stack). The S1 stack can be put into the stack with the lowest priority first. Operator #, note that the infix expression should end with this lowest precedence operator. Other characters can be specified, not necessarily #. Starting from the left end of the infix expression, take the characters and perform the following steps in sequence:

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

.

(2) If the character taken out is an operator, compare the operator with the top element of the S1 stack. If the priority of the operator is greater than the priority of the operator on the top of the S1 stack, add the operator to S1. stack, otherwise, pop the top operator of the S1 stack and send it to the S2 stack. Until the top operator of the S1 stack is lower than (not including equal to) the priority of the operator, then send the operator to the S1 stack. .

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

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

(6) If the character taken out is "#", then all operators in the S1 stack (excluding "#") will be popped out of the stack one by one and sent to the S2 stack in sequence.

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

math_rpn.php file is as follows:

<&#63;php
/**
 * math_rpn 
 *
 * 实现逆波兰式算法
 *  
 */
class math_rpn {
  //初始的计算表达式
  private $_expression = '';
  //处理后的逆波兰表达式
  private $_rpnexp = array();
  //模拟栈结构的数组
  private $_stack = array('#');
  //正则判断
  //private $_reg  = '/^([A-Za-z0-9\(\)\+\-\*\/])*$/';
  //优先级
  private $_priority = array('#' => 0, '(' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);
  //四则运算
  private $_operator = array('(', '+', '-', '*', '/', ')');
  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 == '(') {
        $this->_stack[] = $char;
        continue;
      } else if ( ! in_array($char, $this->_operator)) {
        $this->_rpnexp[] = $char;
        continue;
      } else if ($char == ')') {
        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) == '#') 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*/

I hope this article will be helpful to everyone’s PHP programming design.