最近 Algorithms, Part I | Coursera の社内勉強会を開いている。そこで「Stacks and Queues」という章をみんなで学習し、議論したところ、中置記法の数式文字列から計算結果を求める操車場アルゴリズム(Shunting-yard algorithm)というものがあるということを知った。
操車場アルゴリズムというのは、中置記法の数式文字列から計算結果を求めるというようなことができるアルゴリズム。オペレータスタックと値スタックの二つがあるだけでトークンを一つずつ読みつつその都度計算するだけで計算結果を求めることができる。パースして構文木を作るというフローを取ることなく計算ができるというのが面白い。このアルゴリズムの説明は Wikipediaの操車場アルゴリズム - Wikipedia の説明が非常に分かりやすい。
このアルゴリズムを使うことで、例えば以下のような数式を計算する計算機を作ることができる。
1 + 21 / 2 + 2 * 3 - 11.8 * 3 - 2.1 + 0.51.8 * ( 3 - 2.1 ) + 0.5( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )
このアルゴリズム面白いなーと思い、実際に理解を深めるために、この操車場アルゴリズムを実装してみた。内容をブログに書いておく。
今回実装した仕様
操車場アルゴリズムの全てを実装しようとすると難しいので、今回は簡易版で実装してみた。実装した機能は次のとおり。
- 数値にはdoubleの数値が使える
- +, -, *, /の演算子が利用できる
- 括弧を使うことができる
もっと作り込めば右結合性の演算子(例えば^)や関数(例えばsqrt)にもこのアルゴリズムで対応できる。
基本的には数値や演算子、括弧といったトークンを一つずつ読み取り、読み取ったトークンに従ってそれぞれ次のように処理をするだけで良い。
- tokenが数値なら値スタックに積む
- tokenがオペレータ(o1)の時
- オペレータスタックのトップにオペレータo2 があり、o1 が左結合性で、かつ優先順位が o2 と等しいか低い場合、以下を繰り返す
-
- o2 をオペレータスタックからpopし、値スタックから値を二つpopし、演算し、結果を値スタックにpushする
- o1 をオペレータスタックにプッシュする。
- 注) 右結合性のオペレータは未実装
- トークンが左括弧の場合、オペレータスタックにプッシュする
- トークンが右括弧の場合
- オペレータスタックのトップにあるトークンが左括弧になるまで、オペレータスタックからオペレータをpopし、値スタックから値を二つpopし、それらを演算し、値スタックに結果をプッシュする
- 左括弧があったらスタックからpopし、何もせずに捨てる
全てのトークンの読み込みが終わったら、最後の処理として
- オペレータスタックが空になるまで、オペレータスタックからオペレータをpopし、値スタックから値を二つpopし、それらを演算し、値スタックに結果をプッシュする
- 値スタックに入っている値を返す
この流れで計算式の文字列から計算をして、結果を返すということができる。状態はスタック二つしかないのでそこまで複雑になっていない。
アルゴリズムの流れが分かったので、次は実装してみる。上の流れは明確なアルゴリズムとなっているので、そのまま実装すれば良い。
今回はJavaで実装してみた。コード上にコメントも書いているのでコードを読めばスムーズに理解できると思う。
https://github.com/shibayu36/algorithms/blob/master/src/main/java/org/shibayu36/algorithms/FormulaCalculator.java
package org.shibayu36.algorithms;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import org.apache.commons.lang3.math.NumberUtils;
public class FormulaCalculator {
private static final Map<String, Integer> opPriority = new HashMap<String, Integer>() {
{
put("+", 2);
put("-", 2);
put("*", 3);
put("/", 3);
}
};
数式の文字列を与えると計算結果を返す
@param formula
@return
public static double calculate(String formula) {
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
String[] tokens = formula.split(" ");
for (String token: tokens) {
if (NumberUtils.isCreatable(token)) {
vals.push(Double.parseDouble(token));
}
else if (isOperator(token)) {
while (ops.size() > 0) {
String lastOp = ops.pop();
if (isOperator(lastOp) && getOpPriority(token) <= getOpPriority(lastOp)) {
double val2 = vals.pop();
double val1 = vals.pop();
vals.push(applyOperator(lastOp, val1, val2));
}
else {
ops.push(lastOp);
break;
}
}
ops.push(token);
}
else if (token.equals("(")) {
ops.push(token);
}
else if (token.equals(")")) {
while (ops.size() > 0) {
String op = ops.pop();
if (op.equals("(")) {
break;
}
else {
double val2 = vals.pop();
double val1 = vals.pop();
vals.push(applyOperator(op, val1, val2));
}
}
}
}
while (ops.size() > 0) {
String op = ops.pop();
if (isOperator(op)) {
double val2 = vals.pop();
double val1 = vals.pop();
vals.push(applyOperator(op, val1, val2));
}
}
return vals.pop();
}
private static double applyOperator(String op, double val1, double val2) {
BigDecimal b1 = new BigDecimal(String.valueOf(val1));
BigDecimal b2 = new BigDecimal(String.valueOf(val2));
switch (op) {
case "+":
return b1.add(b2).doubleValue();
case "-":
return b1.subtract(b2).doubleValue();
case "*":
return b1.multiply(b2).doubleValue();
case "/":
return b1.divide(b2).doubleValue();
}
throw new RuntimeException("Unexpected operator: " + op);
}
private static int getOpPriority(String token) {
return opPriority.getOrDefault(token, 0);
}
private static boolean isOperator(String token) {
return opPriority.containsKey(token);
}
}
さらにテストでうまく動いているか確認する。
https://github.com/shibayu36/algorithms/blob/master/src/test/java/org/shibayu36/algorithms/FormulaCalculatorTest.java
package org.shibayu36.algorithms;
import static org.assertj.core.api.Assertions.assertThat;
import org.junit.Test;
public class FormulaCalculatorTest {
@Test
public void calculate() throws Exception {
double result;
result = FormulaCalculator.calculate("1 + 2");
assertThat(result).isEqualTo(3);
result = FormulaCalculator.calculate("1 / 2 + 2 * 3 - 1");
assertThat(result).isEqualTo(5.5);
result = FormulaCalculator.calculate("1.8 * 3 - 2.1 + 0.5");
assertThat(result).isEqualTo(3.8);
result = FormulaCalculator.calculate("1.8 * ( 3 - 2.1 ) + 0.5");
assertThat(result).isEqualTo(2.12);
result = FormulaCalculator.calculate("( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )");
assertThat(result).isEqualTo(3.85);
}
}
これでテストが通ったので、操車場アルゴリズムを実装し、中置記法の数式文字列から計算結果を求めることができた。
まとめ
今回は操車場アルゴリズム(Shunting-yard algorithm)というものを実際に実装してみた。単純にスタックを二つ使うだけで、構文木などを作らなくとも、パースしながら同時に計算することで計算結果を得られるというのが面白かった。
実際に実装してみるとアルゴリズムについて理解が深まり、かつ知識が定着するので、今後も面白そうなアルゴリズムがあったら実装してみたい。
【補足】実行しながらスタックの様子を眺めてみる
理解度を深めるために、実行しながらスタックの様子を眺めてみる。部分部分に注釈を書いた。
実装してみるとこんな感じで自由に動かしてさらに理解が深められるので良いですね。
( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )
formula: ( 10 + 2.2 * 5.5 / 2.2 * ( 1.2 - 0.6 * 3.0 ) / 2 + 4.5 * ( 2.0 - 3 ) )
===============
token: (
ops: [(]
vals: []
------------
token: 10
ops: [(]
vals: [10.0]
------------
token: +
ops: [(, +]
vals: [10.0]
------------
token: 2.2
ops: [(, +]
vals: [10.0, 2.2]
------------
token: *
ops: [(, +, *]
vals: [10.0, 2.2]
------------
token: 5.5
ops: [(, +, *]
vals: [10.0, 2.2, 5.5]
------------
# *と/の優先度が一緒なので*を計算して/をpush
token: /
ops: [(, +, /]
vals: [10.0, 12.1]
------------
token: 2.2
ops: [(, +, /]
vals: [10.0, 12.1, 2.2]
------------
# /と*の優先度が一緒なので、/を計算して*をpush
token: *
ops: [(, +, *]
vals: [10.0, 5.5]
------------
token: (
ops: [(, +, *, (]
vals: [10.0, 5.5]
------------
token: 1.2
ops: [(, +, *, (]
vals: [10.0, 5.5, 1.2]
------------
token: -
ops: [(, +, *, (, -]
vals: [10.0, 5.5, 1.2]
------------
token: 0.6
ops: [(, +, *, (, -]
vals: [10.0, 5.5, 1.2, 0.6]
------------
token: *
ops: [(, +, *, (, -, *]
vals: [10.0, 5.5, 1.2, 0.6]
------------
token: 3.0
ops: [(, +, *, (, -, *]
vals: [10.0, 5.5, 1.2, 0.6, 3.0]
------------
# )があったので、最初に(が見つかるまで、つまり*と-を計算して値をpush
token: )
ops: [(, +, *]
vals: [10.0, 5.5, -0.6]
------------
token: /
ops: [(, +, /]
vals: [10.0, -3.3]
------------
token: 2
ops: [(, +, /]
vals: [10.0, -3.3, 2.0]
------------
# /より+のほうが優先度が低いので、/を計算して+をpush
token: +
ops: [(, +]
vals: [8.35]
------------
token: 4.5
ops: [(, +]
vals: [8.35, 4.5]
------------
token: *
ops: [(, +, *]
vals: [8.35, 4.5]
------------
token: (
ops: [(, +, *, (]
vals: [8.35, 4.5]
------------
token: 2.0
ops: [(, +, *, (]
vals: [8.35, 4.5, 2.0]
------------
token: -
ops: [(, +, *, (, -]
vals: [8.35, 4.5, 2.0]
------------
token: 3
ops: [(, +, *, (, -]
vals: [8.35, 4.5, 2.0, 3.0]
------------
token: )
ops: [(, +, *]
vals: [8.35, 4.5, -1.0]
------------
token: )
ops: []
vals: [3.85]
------------
