続きです。

前回は、計算式がどのように認識されて実行されるかを書きました。今日は、具体的にそれぞれの構成要素をどうやって実装したかを書いていきます。

トークナイザー

"1 + 1 * (1 + 1)" を [1, "+", 1, "*", "(", 1, "+", 1, ")"] に変換します。

入力は文字列。出力は、トークンの配列になります。トークナイザーは、複雑なことをしないため、これで十分です。

ただし、大事なこととしては、例えばスペースで区切られていなくとも、正しくトークンに分割できる必要があります。つまり、 "1+1*(1+1)" も上記の例と同等に扱う必要があります。

トークンを分割する方法

泥臭く、テキストを左から読んでいくだけです。トークンの種類は、四則演算子（4）とかっこ（2）、数字の7種類です。

このなかで数字以外のトークンを見つけたら、その文字を一つのトークンとして扱えばよいです。スペースや改行は無視するだけです。トークナイザーでは、数式として正しいかどうかはチェックしません。とにかくテキストを分割するだけということにしました。

テキストを読み込んでいく中で数字を見つけた場合はスペースや数字以外のトークンを見つけるまでは数字の一部として扱います。

ほんとに泥臭く、for文を使って読んでいくことになります。

参考: https://github.com/naoki-tomita/calculator/blob/5fb6af5/ts/tokenizer.ts#L21-L45

パーサー

トークン列を受け取り、ASTを出力します。

ここでは、計算順序も考慮したASTを出力すべきです。ASTを実行する際には、ASTを素直に実行するだけであるべきなので、パーサー内でかっこや四則演算の優先度を考慮したASTを出力します。ここが面倒でした。

今回のプログラムでは、ASTへの変換前に、トークン列を中間のデータに変換することで、計算順序を中間データに保持させることにしました。

具体的には、 ["1", "+", "2", "*", "3"] というのは、先に2 * 3 = 6を計算したのちに1 + 6 = 7を計算することになります。そこで、トークン列の中で優先度が高いものを入れ子にすることで計算優先度を表すことにしました。つまり ["1", "+", ["2", "*", "3"]] とすることで、先に計算をすべき項目がわかるようになりました。かっこなどがある場合も同様に入れ子にします。

さらに、中間データからASTへ変換することで、うまく計算順序を考慮してASTを作れるようになりました。

最終的に、次のような流れでASTへの変換を行うことになりました。

1. トークン列から括弧の計算優先度を考慮した中間データを作ります。
2. 中間データから四則演算をもとに計算優先度を考慮した中間データを作ります。
3. 最終的な中間データからASTを構築します。

参考: https://github.com/naoki-tomita/calculator/blob/5fb6af5/ts/parser.ts#L88-L92

実行

実行は簡単です。ASTをもとに、一つ一つの葉を評価していけばよいです。

実装を見ていただければわかりますが、再帰的に処理を実行しています。

参考: https://github.com/naoki-tomita/calculator/blob/5fb6af5/ts/executor.ts

まとめ

TypeScriptで計算機を作りました。現実のコードはもっと洗練されていてまとまったアルゴリズムになっているのだと思いますが、自分で作るのは楽しいものです。

以上です。よろしくお願いします。