萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實作四則運算表達式解析器:遞迴下降與運算子優先序處理

核心演算法:遞迴下降解析器

此實作採用「遞迴下降」架構,支援括號巢狀、乘除優先於加減、左結合性。核心流程:

  1. 將字串拆解為字元陣列並反轉(方便 array_pop 取首字元)
  2. calcexp() 遞迴處理運算式,維護兩個堆疊:數值堆疊 $arr_n、運算子堆疊 $arr_op
  3. 遇到 ( 遞迴解析子運算式直到對應 )
  4. 乘除運算子即時結合前一數值與後一數值運算
  5. 加減運算子暫存至運算子堆疊,最後由左至右處理

完整可執行代碼

<?php
error_reporting(E_ALL);

$exp = '(1+2*(3+5)/4)*(3+(5-4)*2)';
$tokens = array_reverse(str_split($exp)); // 字串轉字元陣列並反轉
$result = calcexp($tokens);
echo $exp . ' = ' . $result; // 輸出:(1+2*(3+5)/4)*(3+(5-4)*2) = 21

function calcexp(array &$exp): float {
    $valStack = [];   // 數值堆疊
    $opStack = [];    // 運算子堆疊 (+ -)

    while (($token = array_pop($exp)) !== null) {
        if ($token === '(') {
            // 遞迴處理括號內運算式
            $subExp = [];
            $depth = 1;
            while (($t = array_pop($exp)) !== null) {
                if ($t === '(') $depth++;
                if ($t === ')') {
                    $depth--;
                    if ($depth === 0) break;
                }
                $subExp[] = $t;
            }
            $subExp = array_reverse($subExp);
            $valStack[] = calcexp($subExp);
        }
        elseif ($token === '*' || $token === '/') {
            // 取得右運算元(可能為子運算式)
            $right = getNextOperand($exp);
            $left = array_pop($valStack);
            $valStack[] = operate($left, $token, $right);
        }
        elseif ($token === '+' || $token === '-') {
            $opStack[] = $token;
        }
        else {
            // 數字字元
            $valStack[] = (float)$token;
        }
    }

    // 處理剩餘加減運算
    $result = array_pop($valStack);
    while ($op = array_pop($opStack)) {
        $left = array_pop($valStack);
        $result = operate($left, $op, $result);
    }
    return $result;
}

function getNextOperand(array &$exp): float {
    $token = array_pop($exp);
    if ($token === '(') {
        $subExp = [];
        $depth = 1;
        while (($t = array_pop($exp)) !== null) {
            if ($t === '(') $depth++;
            if ($t === ')') {
                $depth--;
                if ($depth === 0) break;
            }
            $subExp[] = $t;
        }
        $subExp = array_reverse($subExp);
        return calcexp($subExp);
    }
    return (float)$token;
}

function operate(float $a, string $op, float $b): float {
    return match ($op) {
        '+' => $a + $b,
        '-' => $a - $b,
        '*' => $a * $b,
        '/' => $b != 0 ? $a / $b : throw new DivisionByZeroError('Division by zero'),
        default => throw new InvalidArgumentException("Unknown operator: $op"),
    };
}
?>

關鍵設計細節

課題處理方式
字元流處理用 array_pop 從陣列尾部取字元,配合 array_reverse 實現左到右掃描
括號巢狀計數器 $depth 追蹤層級,遇到對應右括號才結束遞迴
運算子優先序乘除即時運算(高優先序),加減延後處理(低優先序)
左結合性加減最後由堆疊順序自然實現左結合
錯誤處理除零拋出 DivisionByZeroError,未知運算子拋出異常

擴展方向

  • 支援負數(一元減號)、冪次方 ^、取模 %
  • 加入變數支援:$x = 2; calc('3*$x+1')
  • 整合 Tokenzier 類別分離詞法分析與語法分析
  • 參考 Doctrine Lexer 或 Symfony ExpressionLanguage 成熟方案
copyright © 萬盛學電腦網 all rights reserved