読者です 読者をやめる 読者になる 読者になる

シンプルな数式のパーサー(操車場アルゴリズム)

構文解析

構文解析にちょこっと興味が出てきたので、単純な数式をパースする関数を Node.js で書いた。参考にしたのは 操車場アルゴリズム(Wikipedia)JavaScript で数式パーサを書いてみた。 です。

数式の定義

できるだけ実装をシンプルにしたいので、数式の定義もシンプルにする。数式を以下のように定義する。

  1. 1文字以上の単語構成文字は数式である。(例: 1, 3, a, x, hoge など)
  2. st が数式のとき、 (s+t), (s-t), (s*t), (s/t) も数式である。
  3. 上記以外は数式でない。

空白文字は入れても良いが無視する。たとえば以下のようなものが数式である。

  • 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項演算を括弧でくくっているので、演算の優先順位を考えなくていい。とりあえず文字列を逆ポーランド記法の配列にパースするアルゴリズムを考える。逆ポーランド記法が得られれば、そこから抽象構文木を得るのは楽勝だ。作業は 2 つの段階にわけられる。

  1. 文字列をトークンに分ける
  2. トークンを次々に読み込んで逆ポーランド記法の配列をつくる

トークンというのは意味のある最小単位のこと。

入力文字列
'(a + (9 * b))'
トークンの配列
['(', 'a', '+', '(', '9', '*', 'b', ')', ')']

作業1(トークンに分ける)は正規表現でババっとできる。操車場アルゴリズムを使うのは作業2だ。

Wikipedia そのままなんだけど、数式を単純にしたのでアルゴリズムも簡略化して書ける。作業用のスタックと出力用のキューを用意する。スタックには演算子をつめこむ。

  1. トークンを先頭から1つずつ読み込んで、トークンが尽きるまで以下を繰り返す。
  2. トークンが数値の場合、出力キューにプッシュする。
  3. トークンが演算子の場合、スタックにプッシュする。
  4. トークンが左括弧の場合、トークンを捨てる。
  5. トークンが右括弧の場合、スタックから1つ演算子をポップして出力キューにプッシュする。

これでいい。

実装

ソースコードGithub に置いた。