PHP 使用逆波蘭表示法計算薪資表達式

PHP 使用逆波蘭表示法計算薪資表達式

逆波蘭表示法（RPN，後綴表達式）無需括號即可明確運算優先序，適合電腦解析執行。本文展示如何將中序表達式（如 (A*(B+C)-E+F)*G）轉換為 RPN，並以堆疊機制完成計算，適用於薪資公式、報表引擎等動態運算場景。

中序轉後綴演算法步驟

1. 準備兩個堆疊：運算符堆疊 S1（含結束符 #）、輸出堆疊 S2
2. 從左至右掃描中序表達式字元
3. 運算元直接進 S2
4. 運算符與 S1 核心比較優先級：高則進 S1，低則彈出 S1 核心至 S2 直到優於核心
5. 左括號直接進 S1；右括號彈出 S1 至左括號並捨棄括號
6. 掃描結束（遇 #），將 S1 剩餘運算符彈出至 S2
7. S2 逆序即為 RPN 序列

PHP 類別實作 math_rpn

<?php
class math_rpn {
    private $_expression = '';
    private $_rpnexp = [];
    private $_stack = ['#'];
    private $_priority = ['#' => 0, '(' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30];
    private $_operator = ['(', '+', '-', '*', '/', ')'];

    public function __construct($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;
            } elseif (!in_array($char, $this->_operator)) {
                $this->_rpnexp[] = $char;
                continue;
            } elseif ($char == ')') {
                for ($j = count($this->_stack); $j >= 0; $j--) {
                    $tmp = array_pop($this->_stack);
                    if ($tmp == "(") break;
                    $this->_rpnexp[] = $tmp;
                }
                continue;
            } elseif ($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());
/* 輸出範例：
string(17) "(A*(B+C)-E+F)*G"
array(7) {
  [0]=> string(1) "A"
  [1]=> string(1) "B"
  [2]=> string(1) "C"
  [3]=> string(1) "+"
  [4]=> string(1) "*"
  [5]=> string(1) "E"
  [6]=> string(1) "-"
  ...
} */
?>

後續計算

取得 RPN 陣列後，再以一個堆疊掃描：遇運算元入堆疊，遇運算符彈出兩個運算元運算並將結果入堆疊，最終堆疊頂即為運算結果。此處略過計算類別，開發者可依需求擴展支援變數替換、函數呼叫等。

應用場景

• 薪資/獎金動態公式引擎
• 報表計算欄位自定義
• 規則引擎條件運算

逆波蘭式將複雜的優先序邏輯轉化為簡單的堆疊操作，是實現動態運算引擎的經典選擇。