シンプルな数式のパーサー（操車場アルゴリズム）
構文解析にちょこっと興味が出てきたので、単純な数式をパースする関数を Node.js で書いた。参考にしたのは 操車場アルゴリズム(Wikipedia) と JavaScript で数式パーサを書いてみた。 です。
数式の定義
できるだけ実装をシンプルにしたいので、数式の定義もシンプルにする。数式を以下のように定義する。
- 1文字以上の単語構成文字は数式である。(例： 1, 3, a, x, hoge など)
sとtが数式のとき、(s+t),(s-t),(s*t),(s/t)も数式である。- 上記以外は数式でない。
空白文字は入れても良いが無視する。たとえば以下のようなものが数式である。
1(x + 1)(a + (9 * b))(1 + (((x / 3) - 6) + (j + (k * n))))
逆ポーランド記法と抽象構文木
与えられた数式に対して、逆ポーランド記法と抽象構文木を出力したい。要するに機械にとって読みやすい形式にしようってこと。説明代わりに例示で済ませる。
入力文字列
'(a + (9 * b))'
逆ポーランド記法の配列
['a', '9', 'b', '*', '+']
抽象構文木をオブジェクトで表現したもの
{
operator: '+',
left: 'a',
right: {
operator: '*',
left: '9',
right: 'b'
}
}
操車場アルゴリズム
数式の構文解析には操車場アルゴリズムを使う。今回の数式ではすべての２項演算を括弧でくくっているので、演算の優先順位を考えなくていい。とりあえず文字列を逆ポーランド記法の配列にパースするアルゴリズムを考える。逆ポーランド記法が得られれば、そこから抽象構文木を得るのは楽勝だ。作業は 2 つの段階にわけられる。
- 文字列をトークンに分ける
- トークンを次々に読み込んで逆ポーランド記法の配列をつくる
トークンというのは意味のある最小単位のこと。
入力文字列
'(a + (9 * b))'
トークンの配列
['(', 'a', '+', '(', '9', '*', 'b', ')', ')']
作業1(トークンに分ける)は正規表現でババっとできる。操車場アルゴリズムを使うのは作業2だ。
Wikipedia そのままなんだけど、数式を単純にしたのでアルゴリズムも簡略化して書ける。作業用のスタックと出力用のキューを用意する。スタックには演算子をつめこむ。
- トークンを先頭から1つずつ読み込んで、トークンが尽きるまで以下を繰り返す。
- トークンが数値の場合、出力キューにプッシュする。
- トークンが演算子の場合、スタックにプッシュする。
- トークンが左括弧の場合、トークンを捨てる。
- トークンが右括弧の場合、スタックから1つ演算子をポップして出力キューにプッシュする。
これでいい。
