此實作採用「遞迴下降」架構,支援括號巢狀、乘除優先於加減、左結合性。核心流程:
array_pop 取首字元)calcexp() 遞迴處理運算式,維護兩個堆疊:數值堆疊 $arr_n、運算子堆疊 $arr_op( 遞迴解析子運算式直到對應 )<?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 類別分離詞法分析與語法分析