【Java】式を逆ポーランド記法(後置記法)に変換する

　情報技術系の本を見ているとよく扱われている逆ポーランド記法。Ruby や JavaScript、PHP など、「eval()」関数がある言語なら必要もないのだが、簡単な計算式くらいパースできるものが欲しかったので、資料を見ながら実装してみた。実際、Java には ScriptEngine などを利用すれば、外部言語の eval() を使えるのだが、実行速度は物凄く重くて、オンラインジャッジなどにはとても使えない。その点、逆ポーランド記法なら軽いので問題なく使えるようだ。スタックの使い方としてもよく用例として使われるので、覚えておいても損はないだろう。

※逆ポーランド記法の式を計算したい場合は → こちら

●式を逆ポーランド記法(Reverse Polish Notation)[=後置記法：postfix notation]に変換する

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/** 逆ポーランド記法用の演算子優先順位 */
@SuppressWarnings("serial")
static final Map<Character, Integer> rpnRank = new HashMap<Character, Integer>() {
    {
        put('(', 4);    //※数値が高いほど、優先順位が高いとする
        put('#', 3);    //オペランド(数値)[キーはダミー]
        put('*', 2);
        put('/', 2);
        put('+', 1);
        put('-', 1);
        put(')', 0);
    }
};

/**<h1>式を逆ポーランド記法(Reverse Polish Notation)[=後置記法：postfix notation]に変換する</h1>
 * <p>スペースを含まない "10+20*30-40+50" のような式。空白文字は全て除去される。
 * <br>四則演算(+, -, *, /)と括弧のみ。除算は整数除算(小数点以下切り捨て)。</p>
 * @param expression ： 変換する式
 * @return<b>String</b> ： 逆ポーランド記法に変換された式
 */
public static final String toRPN(final String expression) {
    final Deque<Character> stack = new ArrayDeque<Character>();

    String s = expression.replaceAll("\\s+", "");    //空白文字を取り除く
    s = "(" + s + ")";                //末尾に")"を付けることで、最後にスタックを吐き出させる
    final int len = s.length();

    String ans = "";    //戻値用(RPN式)バッファ
    String tmp = "";    //数字用バッファ
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if ('0' <= c && c <= '9') {
            tmp += c;    //数字１文字ずつのため
        } else {
            if (!tmp.equals("")) {
                if (ans.length() > 0) {
                    ans += " ";
                }
                ans += tmp;
                tmp = "";
            }

            while (!stack.isEmpty() && rpnRank.get(stack.peek()) >= rpnRank.get(c) && stack.peek() != '(') {
                if (ans.length() > 0) {
                    ans += " ";
                }
                ans += stack.pop();
            }
            if (c == ')') {
                stack.pop();    //'('
            } else {
                stack.push(c);
            }
        }
    }

    return ans;
}


//メインでは...
String expr = "(10+20)*(30-40)+50/2";
System.out.println(toRPN(expr));

10 20 + 30 40 - * 50 2 / +

　アルゴリズムの本などには演算子とオペランドを別々のスタックに入れる方法なども載っているが、今回は文字列の式にするだけなので、スタックは演算子用だけにした。演算子の優先順位は「rpnRank」という Map で定義してあって、数値が高いほど優先順位が高くしてあるが、色々増やしたいのなら、単純な if 文で分岐させるのも良いだろう。

　スタックは例によって Deque（デック：双方向キュー）で実装（ArrayDeque）してあるが、Stack というクラスは Vector クラスの拡張のため、現在では非推奨となっているためだ。それに ArrayDeque は動作も高速なので、通常の Queue としてもオススメだ。

　引数の式は空白は除去して、式の前後を括弧「( )」でくくるようにしてあるが、こうしておくと最後にスタックを全て吐き出させるのに便利なだけで、手動で吐き出させても良い。ただしその分、少しコードが長くなる（while の後に スタックが残っていたら stack.pop() する方法でも良い）。

　あと、除算は整数となるので（3/2 = 1 のように）、実数にするのも良いだろう（その場合は型の変更が必要になる）。またゼロ除算（div /0：エラー）などもチェックしてないので、必要あれば付け加えるのも良いだろう。また演算子としてではなく、負の値（(-3) のような）も特に対応させてないので気をつけよう。あと、剰余も実装していない（ちなみに負の剰余は、Java では 5 % -3 = 2 のように正の値となり、Ruby では 5 % -3 = -1 と負の値となるように、言語によって左項と右項の符号で結果が違うので、パースする式の仕様などを予め確認しておいて実装する必要がある）。

　逆ポーランド記法自体の解説はググればいくらでも出てくるので割愛するが、参考までに図解されているサイトを資料として掲載しておこう。実際に私はこれらと手持ちの資料を見ながら実装した(笑)。簡単な四則演算だけならパフォーマンスも良いし、これだけでも十分だ。

（参考）
・数式を逆ポーランド法に変換するための事柄
・逆ポーランド記法への変換２
・よくわかる逆ポーランド記法(後置記法)問題の解き方＆検算ルール


　逆ポーランド記法をパースして、実際に計算するには「式を逆ポーランド記法(後置記法)で計算する」の記事を見て欲しい。


（関連記事）
【Java】式を逆ポーランド記法(後置記法)で計算する