PHP 逆ポーランド記法

逆ポーランド記法とは

• 被演算子の後ろに演算子を表記する演算記法。
• 後置記法（Reverse Polish Notation, RPN）という。
• 10+20 → 10 20 +

主な手順

• 式を一つ一つ分割し、演算子以外であればスタックに積む(PUSH)。
• 演算子であればスタックから数字を取り出す(POP)。
• 演算結果をスタックに積む。

<?php
function calcRPN($str)
{
    // 式を空白文字でトークンに分割する
    $tokens = preg_split('#\s+#', trim($str));
    $stack = []; // スタックを準備
    foreach ($tokens as $t) {
        // 数値
        if (preg_match('#^[0-9\.]+$#', $t)) {
            $stack[] = floatval($t);
            continue;
        }
        // 四則演算
        $b = array_pop($stack); //スタックの末尾から要素を取り除く
        $a = array_pop($stack);
        switch ($t) {
            case '+':
                $c = ($a + $b);
                break;
            case '-':
                $c = ($a - $b);
                break;
            case '*':
                $c = ($a * $b);
                break;
            case '/':
                $c = ($a / $b);
                break;
            case '%':
                $c = ($a % $b);
                break;
            default:
                return "error";
        }
        $stack[] = $c; //演算結果をスタック末尾に入れる
    }
    return array_pop($stack);
}

$str = '10 20 30 * + 40 - 50 +';
echo calcRPN($str); //620