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

2016/06/02 Thu [edit]

　今度は前回「逆ポーランド記法(後置記法)への変換」で変換された文字列を実際に計算して数値にする関数を作ろう。

　といってもコードは非常にシンプルなので驚くかも知れない。これが逆ポーランド記法がコンピュータと相性が良いと言われる所以かも知れない。ただひたすらスタックからオペランドと演算子を取り出し、その結果を再びスタックに積むという動作を繰り返すだけだ。

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

import java.util.ArrayDeque;
import java.util.Deque;

/**<h1>逆ポーランド記法(Reverse Polish Notation)[=後置記法：postfix notation]を計算する</h1>
 * <p>スペースで区切った "10 20 30 * +" のような形式。連続した空白は１つ分の空白として処理される。
 * <br>四則演算(+, -, *, /)と括弧のみ。</p>
 * @param rpn ： 逆ポーランド記法での計算式
 * @return<b>int</b> ： 計算された値
 */
public static final int parseRPN(final String rpn) {
    final Deque<Integer> stack = new ArrayDeque<Integer>();

    String s = rpn.replaceAll("\\s+", " ");    //連続した空白文字をスペース１つ分に置き換える
    final String[] arr = s.trim().split(" ");

    for (String e : arr) {
        if ('0' <= e.charAt(0) && e.charAt(0) <= '9') {    //数字
            stack.push(Integer.parseInt(e));
        } else {
            int a = stack.pop();
            int b = stack.pop();
            if (e.equals("*")) {
                stack.push(b * a);
            } else if (e.equals("/")) {
                stack.push(b / a);        //div/0 に注意
            } else if (e.equals("+")) {
                stack.push(b + a);
            } else if (e.equals("-")) {
                stack.push(b - a);
            }
        }
    }

    return stack.pop();
}


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

-275

　注意点は前回と同じなので「式を逆ポーランド記法(後置記法)変換する」の記事を参照して欲しい。

　計算される値はとりあえず int 型になっているので、long で算出したいなら、型を修正するのも良いだろう。ゼロ除算（エラー）や剰余などは付けてないので、必要あれば追加しても良いだろう。特に負の除算や剰余に関しては、言語によって仕様が違うので、実装前に予めパースする式の符号などを確認しておく必要がある。以下に参考ページも載せておこう。参考は「負の剰余」がテーマになっているが、商と剰余は２つで１セットのようなものなので、どちらも確認しておいた方が良いだろう。

（参考）
・負数の剰余を計算してはならない
・こんなプログラムはいやだ: 負の剰余
・負の剰余

　また、前回の「逆ポーランド記法への変換」と今回の「逆ポーランド記法を計算」の両方を同時に行うと、簡単な数式をパースして計算する関数にもなる。これは簡易的な eval() 関数やインタプリタなどにも使える。実は元々はそのために作ったものだったりする(笑)。コードを見てもらえばわかると思うが、本当にそのまま２つの関数を混ぜあわせただけだ。

●数式をパースして計算する

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

//※rpnRank は前回の Map をそのまま利用なので割愛。

/**<h1>数式をパースして計算する</h1>
 * <p>逆ポーランド法で計算する。使える演算子は四則演算と括弧のみ。
 * <br>スペースを含まない "(10+20)*30-(40+50)/2" のような式。空白文字は全て除去される。</p>
 * @param expression ： 数式の文字列
 * @return<b>int</b> ： 計算値
 */
public static final int parseExpression(final String expression) {
    final Deque<Character> stack = new ArrayDeque<Character>();
    final Deque<Integer> val = new ArrayDeque<Integer>();

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

    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("")) {
                val.push(Integer.parseInt(tmp));
                tmp = "";
            }

            while (!stack.isEmpty() && rpnRank.get(stack.peek()) >= rpnRank.get(c) && stack.peek() != '(') {
                char e = stack.pop();
                int a = val.pop();
                int b = val.pop();
                if (e == '*') {
                    val.push(b * a);
                } else if (e == '/') {
                    val.push(b / a);        //div/0 に注意
                } else if (e == '+') {
                    val.push(b + a);
                } else if (e == '-') {
                    val.push(b - a);
                }
            }
            if (c == ')') {
                stack.pop();    //'('
            } else {
                stack.push(c);
            }
        }
    }

    return val.pop();
}


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

-275

　解説は同じものなので特に必要はないだろう。

　せっかくなので、この関数を使って練習問題を解いてみよう。問題は「プログラマ脳を鍛える数学パズル」から抜粋させて頂いた。この本では主に Ruby, JavaScript, C で解答ソースが書かれているが、アルゴリズムの本質というものは言語とは特に関係ないので（考え方の方法なので）、理解してしまえば色々応用できる。今回は Ruby ソースを Java に移植したものと考えても良いだろう。

●Q42 1つの数字で作る 1234 (IQ:100 目標時間:30分) ★★★

1つの数字だけで、四則演算によってある数を作ることを考えます。
例えば「1000」を作るとき、「1」だけを7個使って「1111-111」で表現できます。
「8」だけなら8個使って「8+8+8+88+888」、「9」だけであれば5個使って「9÷9÷999」で1000になります。
使用できるのは加減乗除だけとし、括弧は使用不可とします。また「÷」は整数の商のみとします(端数切捨て)。

「1234」を1つの数字だけで、できるだけ少ない個数で表現するとき、最も少ない個数で表現できる数字を求め、
その式をすべて答えて下さい。

●上記の parseExpression() を使った Java での解法

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

public class Q42 {
    public static void main(String[] args) throws Exception {
        new Q42();
    }

    public Q42() throws Exception {
//      n = 1000;    //9/9+999, 999+9/9
        n = 1234;    //99999/9/9
//      n = 4321;    //6/6+66*66-6*6, 6/6-6*6+66*66, 66*66+6/6-6*6, 66*66-6*6+6/6
//      n = 2016;    //9+9+999+999, 9+999+9+999, 9+999+999+9, 999+9+9+999, 999+9+999+9, 999+999+9+9

        solve();
    }

    static final String[] op = {"+", "-", "*", "/", ""};
    int n;            //作る数
    boolean found = false;

    void solve() {
        int len = 1;    //使用する桁数
        while (!found) {
            for (int i = 1; i <= 9; i++) {
                check(len, String.valueOf(i), i);
            }
            len++;
        }
    }

    //remain:桁残り, expr:ここまでの式, num:使用する数字
    void check(int remain, String expr, int num) {
        if (remain == 0) {
            if (parseExpression(expr) == n) {    //※上記の関数を使う
                System.out.println(expr);
                found = true;
            }
        } else {
            for (String o : op) {    //演算子 or ""
                check(remain - 1, expr + o + String.valueOf(num), num);
            }
        }
    }

    //※parseExpression() は割愛（上記のものを使う）
}

99999/9/9

　paiza.io(オンラインIDE)で試してみると、問題の「1234」の場合、約 500ms くらいなので、ギリギリといったところか(笑)。「4321」や「2016」のように答えが多いものは 1s を超えるので、オンラインジャッジでは少しマズイ（１つだけで良いのなら、探索を中断すれば問題ない）。

　ちなみに「ScriptEngine」で外部言語として eval() を使うには以下のようなコードになる。

●「ScriptEngine」で JavaScript の eval() を使って数式を計算する

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

public class Main {
    public static void main(String[] args) throws Exception {
        new Main();
    }

    public Main() throws Exception {
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("JavaScript");

        String expr = "(10+20)*(30-40)+50/2";
        System.out.println(engine.eval(expr));;
    }
}

-275

　ただし、非常に重いので（数式２つ以上で 1s 超える(paiza.io)）全探索で利用するのは難しいだろう。

　また、この「parseExpression()」を使えば、「Q02 数列の四則演算」の問題も同じような方法で解けるので挑戦してみるのも良いだろう。

●Q02 数列の四則演算 (IQ:70 目標時間:10分) ★

並んでいる数字の各桁の間に四則演算の演算子を入れて計算した結果「元の数を桁を逆から並べた数字」
と同じになるものを考えます（演算子は入れない場所があっても構いませんが、最低でも１つは入れるものとします）。
例えば、100～999 (3桁の数字) の場合、以下の 3つがあります。

351 → 3×51 = 153
621 → 6×21 = 126
886 → 8×86 = 688

1000～9999 (4桁の数字) のうち、上記の条件を満たす数を求めて下さい。

[答え] 5931 （→ 5×9×31 = 1395）
[＞＞クリックでコードを見る]

※なお、問題文などは以下の書籍からお借りしている（ただし、書籍の解答例は Ruby, JavaScript, C などで書かれているので購入の際はご注意）。パズルっぽい問題の解法パターンを勉強するには良いかも。