職場のネット寸断が激しかったので久しぶりのネット活動です
タイトルは今のQiitaではあまり受けが良くなさそうな硬そうな命名にしてみました
要件で求められるパフォーマンスの関係で、再帰下降構文解析法で四則計算する解析器を作成しました
誰かの参考になるかもしれないので置いておきます
要件
バッチアプリで数式が文字列で取得されるので、それを計算して結果を返却したかったらしいのですが、その数が膨大でした
元々は、JavaからJavaScriptを呼び出して数式をそのまま渡して計算してもらうつもりだったそうなのですが、対象の式の数が何万何十万単位のため1日で終了しなかったようです
しかもこれからもどんどん増えるそうなのです！
当然次のジョブもあるので、その開始時間までに処理が終わるようにしなければなりません
そこで僕に何とかしてほしいと話がまわってきました
最初に話を聞いたときは、外部プログラム呼び出しでしかもJavaScriptで高速な計算処理ができるわけないがな、と思いましたが
ようは、高速な四則計算が可能な解析器を作成すればよいわけです
除算時の丸め誤差も制御したいらしいので、それも考える必要があります
まあ全部Javaで実装すれば速度面は問題ないだろうと予想して、取り合えず単純な実装のわりにそこそこ強力な再帰下降構文解析法でいくことに決めました
コード
以下Java8で実装しています
FormulaParser.java
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class FormulaParser {
private static final int HIGH_PRIORITY = 3;
private static final int MID_PRIORITY = 2;
private static final int LOW_PRIORITY = 1;
private static final Pattern EMPTY_BRACKET = Pattern.compile("\\(\\)");
private static final Pattern NOT_CLOSE_BRACKET = Pattern.compile("\\)\\(");
private static final int NO_EXIST = -1;
private static final String ZERO = "0";
private static final String BRACKET_AND_ZERO = "(0";
private String expression; // 式
private FormulaParser left; // 左子ノード
private FormulaParser right; // 右子ノード
private int scale;
/**
* スケールありコンストラクタ
* ※除算の場合のみscaleを考慮する
*
* @param expression 計算式
* @param scale 除算時切り落とし小数点位置
*/
public FormulaParser(String expression, int scale) {
this.expression = format(expression);
this.scale = scale;
}
/**
* 式を二分木に分割し計算する
*
* @throws FormulaParseException
*/
public String execute() throws FormulaParseException {
// 最も外側の括弧を消す
String exp = delMostOuterBrackets(this.expression);
// 式から演算子を探して位置を取得
int opePos = getOpePos(exp);
// 式に演算子が含まれないなら項であるとみなす
if (opePos < 0) {
left = null;
right = null;
return new BigDecimal(exp).toPlainString();
}
// 演算子位置が式の先頭か末尾の場合、不正扱い
if (opePos == 0 || opePos == exp.length() - 1) {
throw new FormulaParseException(exp);
}
// 演算子の左側を左の部分式としてノードを作成
left = new FormulaParser(exp.substring(0, opePos), scale);
// 演算子の右側を右の部分式としてノードを作成
right = new FormulaParser(exp.substring(opePos + 1), scale);
// 残った演算子をこのノートに設定
expression = exp.substring(opePos, opePos + 1);
return calculate(left.execute(), OPERATOR.getEnum(expression), right.execute(), scale);
}
/**
* 演算子の位置を取得
*
* @param exp 式
* @return 演算子位置(0始まり)/ない場合は-1を返す
*/
private static int getOpePos(String exp) {
int opePos = NO_EXIST;
int curPriority = Integer.MAX_VALUE;
int nest = 0;
for (int i = 0, len = exp.length(); i < len; i++) {
int priority = 0;
switch (OPERATOR.getEnum(String.valueOf(exp.charAt(i)))) {
case PLUS:
case MINUS:
priority = MID_PRIORITY;
break;
case MULTIPLY:
case DIVIDE:
priority = HIGH_PRIORITY;
break;
case LEFT_BRACKET:
nest++;
continue;
case RIGHT_BRACKET:
nest--;
continue;
default:
continue;
}
if (nest == 0 && priority <= curPriority) {
curPriority = priority;
opePos = i;
}
}
return opePos;
}
/**
* 計算処理
*
* @param lExp 左項
* @param ope 演算子
* @param rExp 右項
* @param scale スケール
*/
private String calculate(String lExp, OPERATOR ope, String rExp, int scale) throws FormulaParseException {
BigDecimal left = new BigDecimal(lExp);
BigDecimal right = new BigDecimal(rExp);
switch (ope) {
case PLUS:
return left.add(right).toPlainString();
case MINUS:
return left.subtract(right).toPlainString();
case MULTIPLY:
return left.multiply(right).toPlainString();
case DIVIDE:
return left.divide(right, scale, RoundingMode.DOWN).toPlainString();
default:
throw new FormulaParseException(left + ope.val + rExp);
}
}
/**
* フォーマット
* 半角スペースは排除
* 正負記号と加減算演算子の区別がつけ難いため、0埋めして簡単にする
*
* @param exp 式
* @return フォーマットされた式 ex) -3 + 1 → 0-3+1
*/
private static String format(String exp) {
// 半角スペースは排除する
StringBuilder e = new StringBuilder(exp.replaceAll(" ", ""));
int cur = 0;
for (; ; ) {
int plusIndex = e.indexOf(OPERATOR.PLUS.val, cur);
int minusIndex = e.indexOf(OPERATOR.MINUS.val, cur);
if (plusIndex == NO_EXIST && minusIndex == NO_EXIST) {
break;
}
// 演算子が存在しかつ前にある方をのインデックスを取得
if (plusIndex < minusIndex) {
cur = (plusIndex == NO_EXIST) ? minusIndex : plusIndex;
} else {
cur = (minusIndex == NO_EXIST) ? plusIndex : minusIndex;
}
if (cur == 0) {
e.insert(cur, ZERO);
cur = cur + ZERO.length() + 1;
continue;
}
// 演算子の一つ前の文字が数値ではなく、閉じ括弧や乗算、除算演算子でもない場合0を追加
char preChar = e.charAt(cur - 1);
if (!Character.isDigit(preChar)
&& preChar != OPERATOR.RIGHT_BRACKET.cVal) {
if (preChar == OPERATOR.MULTIPLY.cVal
|| preChar == OPERATOR.DIVIDE.cVal
|| preChar == OPERATOR.MINUS.cVal) {
int endDigits = 0;
for (int i = cur + 1, len = e.length(); i < len; i++) {
char c = e.charAt(i);
if (!Character.isDigit(c) && c != '.') {
break;
}
endDigits = i;
}
e.insert(cur, BRACKET_AND_ZERO).insert(endDigits + BRACKET_AND_ZERO.length() + 1, OPERATOR.RIGHT_BRACKET.cVal);
cur = endDigits + BRACKET_AND_ZERO.length();
} else {
e.insert(cur, ZERO);
cur = cur + ZERO.length();
}
}
cur++;
if (cur > e.length()) break;
}
return e.toString();
}
/**
* 丸括弧削除処理
* 式から最も外側の括弧を削除する
* (1+2)+(3+4)のような式はそのまま返す
* 括弧が閉じていないなら不正な式として例外をスロー
*
* @param exp 式
* @return 丸括弧を削除した式 ex) (4*2) → 4*2, ((3+4)) → 3+4, (1+2)+(3+4) → (1+2)+(3+4)
* @throws FormulaParseException
*/
private static String delMostOuterBrackets(String exp) throws FormulaParseException {
if (matchFirst(exp, EMPTY_BRACKET).isPresent()) throw new FormulaParseException(exp);
if (matchFirst(exp, NOT_CLOSE_BRACKET).isPresent()) throw new FormulaParseException(exp);
if (exp.charAt(0) == OPERATOR.RIGHT_BRACKET.cVal) throw new FormulaParseException(exp);
boolean hasMostOuterBrackets = false;
int nest = 0;
// 1文字目を検証
if (exp.charAt(0) == OPERATOR.LEFT_BRACKET.cVal) {
hasMostOuterBrackets = true;
nest++;
}
// 1文字目以降を1文字ずつずつ検証
for (int i = 1, len = exp.length(); i < len; i++) {
if (exp.charAt(i) == OPERATOR.LEFT_BRACKET.cVal) {
nest++;
} else if (exp.charAt(i) == OPERATOR.RIGHT_BRACKET.cVal) {
nest--;
if (nest == 0 && i < len - 1) {
hasMostOuterBrackets = false;
}
}
}
// 括弧が閉じていないなら不正な式
if (nest != 0) throw new FormulaParseException(exp);
// 括弧がないならそのまま返す
if (!hasMostOuterBrackets) return exp;
// 最初と最後の括弧を取り除く
String ret = exp.substring(1, exp.length() - 1);
// まだ括弧があるならもう一度処理
if (ret.charAt(0) == OPERATOR.LEFT_BRACKET.cVal
&& ret.charAt(ret.length() - 1) == OPERATOR.RIGHT_BRACKET.cVal) {
return delMostOuterBrackets(ret);
}
return ret;
}
/**
* 検索
*
* @param s 検索対象
* @param p 正規表現
* @return 検索結果
*/
private static Optional<String> matchFirst(String s, Pattern p) {
Matcher m = p.matcher(s);
return m.find() ? Optional.of(m.group(0)) : Optional.empty();
}
/**
* 演算子
*/
private enum OPERATOR {
PLUS("+", '+'),
MINUS("-", '-'),
MULTIPLY("*", '*'),
DIVIDE("/", '/'),
LEFT_BRACKET("(", '('),
RIGHT_BRACKET(")", ')'),
NO_OPE(" ", ' ');
public String val;
public char cVal;
private final static Map<String, OPERATOR> m = new HashMap<>();
static {
for (OPERATOR o : OPERATOR.values()) {
m.put(o.val, o);
}
}
private OPERATOR(String val, char cVal) {
this.val = val;
this.cVal = cVal;
}
public static OPERATOR getEnum(String val) {
return m.getOrDefault(val, NO_OPE);
}
}
}
FormulaParseException.java
public class FormulaParseException extends Exception {
public FormulaParseException(String msg) {
super(msg);
}
}
例外はそれっぽいのを適当に実装しました
パーサによる解析と、計算処理は分けずに一つのクラスにまとめています
正負記号と加減演算子の区別が面倒なので0埋めしてます
必要に応じて括弧も追加しているのもポイントです
解析もそれなりにコストがかかるので、本来のアプリは事前チェックもそれなりに手厚くしています
あと、Math関数や変数も処理できるようにしているのですが、思い出してコードを書くのがしんどいので省きました
matchFirst()メソッドはその名残ですね
他にも便利なユーティリティーを実装して色々やっていました
変数は適当に置換すればいいだけです
Math関数についてはヒントだけ言うと、↑のコードだとMath関数は項として扱われます
なので下記のコードあたりに、Math関数か判別してMath関数ならそれを処理するメソッドを呼び出すようにすればいいです
return new BigDecimal(exp).toPlainString();
Math関数を処理するメソッドは、delMostOuterBrackets()やformat()みたいに地道に文字をチェックして処理すればいいです
つまり、記事に書いたコードを応用すればいけるので必要なら自力で作ってみてください
終わりに
とりあえず実装して動かしてみたら要件を満たしてくれたのでそこで終了です
件数が何千万から億までいくと怪しいですが、そこまではいかないそうなので大丈夫のようです
テストは山ほど書きましたが、思い出して移植するのがしんどいので省きます
まあ式の想定結果をチェックするだけなのでJUnitも不要なぐらいですが
僕はCS専攻ではなく独学で学んでいる口なので、実務でこの手の設計実装をじっくり考えるのは結構ためになりました
またアルゴリズムとデータ構造の知識がないと太刀打ちできないような案件がでてきてくれることを祈って記事は終わりです
ノシ