四則演算をするスタックマシン

さくらばさんのマカロンスタックの写真を見ていて、ふと書きたくなったので。

逆ポーランド記法を入力として四則演算を行い、結果を返します。

（追記: 2012/9/6） この記事のコードには、誤りが2箇所あります（1:除算のオペランドが逆、2:テストデータは"14+37+*5/"が正しい）。修正した次の記事を参照してください。http://d.hatena.ne.jp/torazuka/20120906/stackmachine

逆ポーランド記法とは？

こういう計算があったとして・・・

(1 + 2) * 4 + (4 - 2)

逆ポーランド記法で書くと、こうなります。

1 2 + 4 * 4 2 - +

括弧を使わずに四則演算を表現できます。

括弧を使わないということは、計算の途中結果を複数個保存しておく場所が必要がありません。つまり、使用するメモリを節約できるのだそうです。

package stackmachine;

import java.util.ArrayDeque;

interface Operator {
	Integer execute(Integer num0, Integer num1);
}

class Add implements Operator {
	@Override
	public Integer execute(Integer num0, Integer num1) {
		return num1 + num0;
	}
}

class Sub implements Operator {
	@Override
	public Integer execute(Integer num0, Integer num1) {
		return num1 - num0;
	}
}

class Mul implements Operator {
	@Override
	public Integer execute(Integer num0, Integer num1) {
		return num1 * num0;
	}
}

class Dev implements Operator {
	@Override
	public Integer execute(Integer num0, Integer num1) {
		// TODO: 0除算に対する処理があるべき
		return num0 / num1;
	}
}

public class StackMachine {

	protected Integer convertOperand(char c) throws NumberFormatException {
		Integer result = 0;
		try {
			Integer number = Integer.valueOf(String.valueOf(c));
			result = number;
		} catch (NumberFormatException e) {
			throw e;
		}
		return result;
	}

	protected Operator convertOperator(char c) {
		Operator result = null;
		if (c == '+') {
			result = new Add();
		} else if (c == '-') {
			result = new Sub();
		} else if (c == '*') {
			result = new Mul();
		} else if (c == '/') {
			result = new Dev();
		}
		return result;
	}

	protected int execute(String input) {
		ArrayDeque<Integer> stack = new ArrayDeque<>();

		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			Operator op = convertOperator(c);
			if (op == null) {
				// オペランドなら、スタックに入れる
				int num = convertOperand(c);
				stack.push(num);
				System.out.println("[スタック] <= " + num);
			} else {
				// オペレータなら、スタックから2個取り出して、計算した結果をスタックに入れる
				Integer tmp0 = stack.pop();
				System.out.println("[スタック] => " + tmp0);
				Integer tmp1 = stack.pop();
				System.out.println("[スタック] => " + tmp1);
				tmp0 = op.execute(tmp0, tmp1);
				stack.push(tmp0);
				System.out.println("[スタック] <= " + tmp0);
			}
		}
		return stack.pop();
	}

	public static void main(String[] args) {
		StackMachine stackMachine = new StackMachine();

		// (1 + 2) * 4 + (4 - 2) == 14
		System.out.println(stackMachine.execute("12+4*42-+"));

		// (1 + 4) * (3 + 7) / 5 == 10
		System.out.println(stackMachine.execute("14+37+5*/"));
	}
}

それだけです。

JavaのStackの実装クラスはArrayDequeだと聴いたので、使ってみました。

書いていて気づいたこと

スタックからか必ず2個ずつ取り出す

最初、次のような式に対応するためには、スタックに積んだ値の数をカウンタで保持しないといけないかと思ったのですが・・・

1 + 2 + 3

この記法を処理するときに、そんな必要はないのでした。こうではなく、

1 2 3 +

こうだからです。

1 2 3 + +

かならず2個取り出せばよいのですね。

たとえば、上のコードで、この計算を実行すると、結果は次のようになります。

[スタック] <= 1
[スタック] <= 2
[スタック] <= 3
[スタック] => 3 // ここで1つ目の「+」オペレータと出会い、値を取り出す
[スタック] => 2 // 同じく、値の取り出し
[スタック] <= 5 // 計算結果の格納
[スタック] => 5 // ここで2つ目の「+」オペレータと出会い、値を取り出す
[スタック] => 1
[スタック] <= 6
6