[PHP]逆ポーランド記法への変換と計算

「1 * (2 + 3) * 4 – 5」のような数式が書かれた文字列を計算する場合、eval() を使ってしまうのが最も簡単ですが、状況によっては危険な関数を使われてしまうおそれがあるため利用できないことがあります。
自力で計算しなければならないときは一般的に「逆ポーランド記法（後置記法）」に変換してから計算を行うとプログラムが作りやすくなります。

例えば「1 + 2」を逆ポーランド記法で書くと「1 2 +」となります。「1 * (2 + 3) * 4 – 5」の場合は「1 2 3 + * 4 * 5 -」と書きます。
計算の仕方は、先頭から順に読み進め、算術演算子（+-*/）が現れるまで数字を１つずつ配列に格納していきます。
算術演算子が現れたら配列の後ろから２つ取り出し、その演算子で計算して置き換えます。「1 2 3 + *」であれば 1, 2, 3 を配列に格納し、後ろから 3 と 2 を取り出し、最初に現れた「+」で計算した結果で置き換えるとまずは「1 5 *」となります。再度配列の後ろから２つ(5, 1)取り出し、次に現れる演算子「*」で計算すると結果は 5 となります。詳細に関しては末尾に参考リンクを掲載しているのでそちらを読んで下さい。

こちらに変換を行うPHPプログラムを掲載しました。toRpn() で計算式の文字列を逆ポーランド記法の文字列に変換します。
逆ポーランド記法の計算式の計算結果を得るには calcRpn() を使います。

<?php
$expression = '1 * (2 + 3) * 4 - 5';

echo $rpn = toRpn($expression);
echo " = ";
echo calcRpn( $rpn );

function toRpn($expression) {
    $expression = preg_replace('/\s/', '', $expression);
    preg_match_all('/[0-9]+|\+|-|\*|\/|\(|\)/', $expression, $matches);
    $parts = $matches[0];
    
    $stack = [];
    $output = [];
    
    $priorities = [ '/' => 2, '*' => 2, '+' => 1, '-' => 1, '(' => -1, ')' => -1 ];
    
    foreach ($parts as $part) {
        if (is_numeric($part)) {
            $output[] = $part;
        } elseif ($part == '(') {
            $stack[] = $part;
        } elseif ($part == ')') {
            while (count($stack) > 0) {
                $end = end($stack);
                if ($end == '(') {
                    array_pop($stack);
                    break;
                } else {
                    $output[] = array_pop($stack);
                }
            }
        } else {
            if (!empty($stack)) {
                while (true) {
                    $end = end($stack);
                    if ($end && $priorities[$part] <= $priorities[$end]) {
                        $output []= array_pop($stack);
                    } else {
                        break;
                    }
                }
            }
            $stack[] = $part;
        }
    }
    
    while (count($stack) > 0) {
        $output[] = array_pop($stack);
    }
    
    return implode(' ', $output);
}

function calcRpn($expression) {
    $parts = preg_split('/\s/', $expression, -1, PREG_SPLIT_NO_EMPTY);
    $stack = [];

    foreach ($parts as $part) {
        if (is_numeric($part)) {
            $stack[] = $part;
        } else {
            $b = (float)array_pop($stack);
            $a = (float)array_pop($stack);
            
            switch ($part) {
                case "+":
                    $x = $a + $b;
                    break;
                case "-":
                    $x = $a - $b;
                    break;
                case "*":
                    $x = $a * $b;
                    break;
                case "/":
                    $x = $a / $b;
            }
			array_push($stack, $x);
        }
    }

    return $stack[0];
}

出力結果:
1 2 3 + * 4 * 5 - = 15

参考: さくらのナレッジ「日曜プログラミングで電卓を作ってみる」

PHP Archive

Webサイト開発初心者の備忘録

[PHP]逆ポーランド記法への変換と計算

コメントを残す