http://d.hatena.ne.jp/torazuka/20120829/stackmachine
で始まった逆ポ。
私も Java でも書いた方がいいような気がして、書いてみた。
今回の逆ポは、階乗を意味する「!」がある。
Rpn.java
import java.util.ArrayDeque;
import java.util.Deque;
class TestData {
final String input;
final double expected;
TestData(String i, double e) {
input = i;
expected = e;
}
static final TestData[] data = new TestData[]{
new TestData("1", 1),
new TestData("1 2 +", 3),
new TestData("3 1 -", 2),
new TestData("10 2 /", 5),
new TestData("2 5 8 + +", 15),
new TestData("2 5 8 + *", 26),
new TestData("2 5 8 * +", 42),
new TestData("1 2 + 3 4 + *", 21),
new TestData("2 3 * 4 5 * +", 26),
new TestData("3 ! !", 720),
new TestData("4 1 - ! 1 + ! 56 /", 90),
};
}
interface RpnItem {
void process(Deque<Double> items);
}
abstract class RpnUnaryOp implements RpnItem {
@Override
public void process(Deque<Double> items) {
double first = items.pop();
items.push(calc(first));
}
abstract double calc(double f);
}
class RpnFact extends RpnUnaryOp {
private double fact(double r) {
if (r <= 1) {
return 1;
}
return r * fact(r - 1);
}
@Override
double calc(double f) {
return fact(f);
}
}
abstract class RpnBiOp implements RpnItem {
@Override
public void process(Deque<Double> items) {
double first = items.pop();
double second = items.pop();
items.push(calc(first, second));
}
abstract double calc(double f, double s);
}
class RpnAdd extends RpnBiOp {
double calc(double f, double s) {
return f + s;
}
}
class RpnSub extends RpnBiOp {
double calc(double f, double s) {
return -f + s;
}
}
class RpnDiv extends RpnBiOp {
double calc(double f, double s) {
return s / f;
}
}
class RpnMul extends RpnBiOp {
double calc(double f, double s) {
return f * s;
}
}
class RpnNumber implements RpnItem {
private double number;
public RpnNumber(double v) {
number = v;
}
@Override
public void process(Deque<Double> items) {
items.push(number);
}
}
class RpnItemFactory {
static RpnItem create(String token) {
if (token.equals("+")) {
return new RpnAdd();
} else if (token.equals("-")) {
return new RpnSub();
} else if (token.equals("*")) {
return new RpnMul();
} else if (token.equals("/")) {
return new RpnDiv();
} else if (token.equals("!")) {
return new RpnFact();
} else {
return new RpnNumber(Double.parseDouble(token));
}
}
}
public class Rpn {
public static void main(String[] args) {
for (TestData td : TestData.data) {
double actual = solveRon(td.input);
if (actual != td.expected) {
System.out.printf("%s -> %f ( expected %f )\n", td.input, actual, td.expected);
} else {
System.out.printf("%s -> %f\n", td.input, actual);
}
}
}
private static double solveRon(String input) {
Deque<Double> items = new ArrayDeque<Double>();
for (String token : input.split("\\s")) {
RpnItemFactory.create(token).process(items);
}
return items.pop();
}
}
コメントをいっさい書かずに 140行。
テストデータのクラスなどを度外視しても100行を下回らないのはどうかとも思ったが、まあ普通にスタックマシンを書いたらこれぐらいじゃないかな。
トークンに分けるためのコードを書かずに済んでいるだけましとも思う。
RpnFactoryクラスが自分としては最大の不満なんだけれども、こういうもん？
Rpn と書くべきところを Ron とタイポしているのを発見。とほほ。