はじめに
ユーザが入力した数式を解析して計算する処理を実装しました。
実装にあたって、数式解析の代表的な手法である「逆ポーランド記法」と「抽象構文木」について調査したので、その内容と最終的なアプローチを備忘録として書き残しておきます。
実現したいこと
一言で言うと、Excelの数式やSQLのSELECT句のような機能です。アプリケーション内でテーブル形式のデータを扱う際に、ユーザが独自の計算式を定義して集計できるようにすることを目指します。
1. 四則演算と演算子の優先順位
ユーザが入力した 1 + 2 * 3 という文字列を 7 と正しく計算できるように、演算子の優先順位（乗除算が先、など）や括弧を考慮した計算処理が必要です。
# ユーザー入力例
1 + (2 + 3) / 4
# 期待する計算結果
2.25
2. 変数(テーブルの列) の利用
テーブルの各列の値を、変数として数式に組み込めるようにします。
これにより、データに基づいた動的な計算が可能になります。
# "col1"列の値が10, "col2"が20, "col3"が30の場合...
col1 + (col2 + col3) / 4
# 期待する計算結果
10 + (20 + 30) / 4 = 22.5
3. 集計関数のサポート
ExcelやSQLのように、複数の値から1つの結果を算出する集計関数も利用できると、表現の幅が広がり非常に便利です。
# テーブル全体の各列に対して集計を行う場合...
MAX(col1) + (AVG(col2) + AVG(col3)) / COUNT(col4)
4. エラーハンドリング
一方で、文法的に破綻した数式が入力された場合は、それをエラーとして適切にハンドリングする必要があります。
# 括弧が閉じていないなど、不正な入力
col1 + (col2 + col3 /
どう実現するか
ユーザが入力した文字列は、プログラムにとっては単なる文字の並びでしかありません。これを計算可能な形式に変換するために、構文解析 という処理が必要になります。
構文解析とは、文字列をその構造（文法）に従って分解し、プログラムが意味を解釈できるデータ構造に変換することです。今回は、その変換先のデータ構造として代表的な2つの形式を検討しました。
逆ポーランド記法 (Reverse Polish Notation):
1 + 2 を 1 2 + のように、「値 値 演算子」の語順に変換する。
抽象構文木 (Abstract Syntax Tree, AST):
1 + 2 を + という演算を根(ルート)とし、その子として 1 と 2 を持つ木構造で表現する。
逆ポーランド記法
操車場アルゴリズム
一般的な数式（中置記法）を逆ポーランド記法に変換する有名なアルゴリズムが、ダイクストラによって考案された操車場アルゴリズム (Shunting-yard algorithm) です。
文字列を左から読んでいき、数値はそのまま出力キューへ、演算子はスタックを利用して優先順位を考慮しながら並べ替えて出力キューへ送ります。
| 入力 | スタック | 出力キュー |
|---|---|---|
| 1 | − | 1 |
| + | + | 1 |
| 2 | + | 1 2 |
| * | + * | 1 2 |
| 3 | + * | 1 2 3 |
| （処理後） | − | 1 2 3 * + |
計算ロジック
逆ポーランド記法は、1つのスタックを利用して、以下の手順で計算します。
- リストを左から順に見ていく
- 数値であれば、スタックに積む (push)
- 演算子であれば、スタックから必要な数（二項演算子なら2つ）の数値を取り出し (pop)、計算する
- 計算結果を再びスタックに積む (push)
- リストの最後までこれを繰り返すと、スタックには最終的な計算結果だけが残る
| 処理対象 | スタックの状態 | 説明 |
|---|---|---|
1 |
[1] | 1をスタックに積む |
2 |
[1, 2] | 2をスタックに積む |
3 |
[1, 2, 3] | 3をスタックに積む |
* |
[1, 6] | 3と2を取り出し 2 * 3 を計算、結果の6を積む |
+ |
[7] | 6と1を取り出し 1 + 6 を計算、結果の7を積む |
| (終了) | [7] | 最終結果は7 |
メリット:
- アルゴリズムが比較的シンプルで、実装しやすい
- 生成された逆ポーランド記法は、スタック一つで簡単に計算できる
デメリット:
- 式の構造がフラットなリストになるため、人間にとって直感的ではない
- 後から式の最適化や、複雑な構文を追加する際の拡張が少し難しい場合がある
抽象構文木
再帰下降法
抽象構文木 (AST) は、数式の構造そのものを木で表現するデータ構造です。このASTを構築するための代表的な手法が再帰下降法 (Recursive Descent Parsing) です。
文法のルール（例: 「式は項の足し算または引き算である」「項は因子の掛け算または割り算である」…）ごとに対応する関数を作成し、互いを再帰的に呼び出しながら木を構築していきます。
通常、最初に字句解析 (Lexical Analysis) を行い、文字列をトークン（数値、演算子、変数名などの意味のある最小単位）の列に分割してから構文解析に進みます。
計算ロジック
ASTの計算は、再帰的な木構造の探索によって行います。
- 木の根（ルート）から評価を開始する
- 現在のノードが数値（葉）であれば、その値を返す
- 現在のノードが演算子（節）であれば、まずその子ノード（左の子、右の子）を再帰的に評価する
- 子ノードの評価結果が返ってきたら、それらを使って自身のノードの演算を実行し、結果を親に返す
- これを繰り返すと、最終的にルートノードで計算結果が求まる
evaluate(+)
│
├─ evaluate(1) => 1を返す
│
└─ evaluate(*)
│
├─ evaluate(2) => 2を返す
│
└─ evaluate(3) => 3を返す
│
└─ (*)の結果として 2 * 3 = 6 を返す
│
└─ (+)の結果として 1 + 6 = 7 を返す
メリット:
- 式の構造がデータ構造として明確に表現されるため、非常に直感的
- 木の形を保ったまま変換や分析ができるため、機能拡張（新しい関数の追加、コードの最適化など）がしやすく、拡張性に優れている
- 構文エラーの位置を特定しやすく、詳細なエラーメッセージを生成しやすい
デメリット:
- 操車場アルゴリズムに比べると、実装が少し複雑になる傾向がある
- 左再帰な文法(
式 -> 式 + 項のように、定義の先頭で自身を呼び出すこと) をそのまま実装すると無限ループに陥るため、文法の設計に注意が必要
どちらを選択したか
今回は抽象構文木 (AST) を再帰下降法で構築するアプローチを選択しました。
主な理由は以下の通りです。
拡張性:
当初の要件は四則演算と単純な集計関数ですが、将来的により複雑な関数をサポートする可能性を考慮すると、式の構造を柔軟に扱えるASTが有利と考えました。
保守性:
式の構造が木として視覚的にイメージしやすく、デバッグや機能追加が比較的楽になると考えました。
エラー表示の親切さ:
ASTを構築する過程で、例えば「括弧が閉じられていない」や「予期しない文字が現れた」といったエラーを具体的な場所（何文字目か）とともに特定しやすくなります。「) が足りません」のような、分かりやすいエラーメッセージを提示できるため、こちらの方がユーザ体験が良くなると考えました。
まとめ
ユーザ定義の数式を計算する機能を、構文解析の手法を用いて実装しました。
今回は、拡張性と保守性を重視して抽象構文木 (AST) を採用しました。
操車場アルゴリズムのような手法もシンプルで強力ですが、長期的な運用や機能追加を考えると、ASTによるアプローチが有効な場面は多いのかなと感じました。
同様の課題を持つ方の参考になれば幸いです。