[JavaScript]数式から構文木を生成する数式パーサ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[JavaScript]数式から構文木を生成する数式パーサ

一元一次方程式を解釈して、未知数の値を求めるプログラムが書きたくなったので、まずは数式パーサを書いてみることにした。

id:amachangのコードを参考に、JavaScriptを使って数式を構文木に変換する数式パーサを書いてみた。

仕様などはほとんどamachangのものと同じだけど、↓の点が異なる。

  • 括弧が使える
  • 単項演算子の+-と数値との間に空白を置いてはいけない
  • 逆に、二項演算子の+-と数値との間には空白を置かなければいけない

ソースコード

var parse = function(source) {
    var binary = {'+': 1, '-': 1, '*': 2, '/': 2};

    var tokens = source.match(/[-+]?\d+(?:\.\d+)?(?:[Ee]\d+)?|[-+*/()]/g);
    return (function(start, end) {
        var index = start, stack = [];
        while (index < end) {
            var operand, token = tokens[index++];
            if (token == '(') {
                var depth = 0, open = index;
                do {
                    token = tokens[index];
                    if (token == '(') {
                        depth++;
                    } else if ((token == ')') && !depth--) {
                        operand = arguments.callee(open, index++);
                        break;
                    }
                } while (index++);
            } else {
                operand = Number(token);
            }

            var operator = tokens[index++], precedence = binary[operator] || 0;
            while (stack.length && precedence <= binary[stack[stack.length - 1]]) {
                operand = [stack.pop(), stack.pop(), operand];
            }
            stack.push(operand, operator);
        }
        return stack.shift();
    })(0, tokens.length);
};

動作サンプル

console.log(parse('1.2 * (2e3 + 4 / 5.3e1) - 2 * 4 / 19'));
// ["-", ["*", 1.2, ["+", 2000, ["/", 4, 53]]], ["/", ["*", 2, 4], 19]]

メモ

04: var tokens = source.match(/[-+]?\d+(?:\.\d+)?(?:[Ee]\d+)?|[-+*/()]/g);

↑トークン化。数値と演算子に分ける。この時点で単項演算子は数値に含めてしまう。

05: return (function(start, end) {

31: })(0, tokens.length);

↑括弧の中身を再帰的に処理する関数。最初は式全体を1つの括弧とみなして、最初と最後の位置を引数として渡す。

08: var operand, token = tokens[index++];
09: if (token == '(') {
10:     var depth = 0, open = index;
11:     do {
12:         token = tokens[index];
13:         if (token == '(') {
14:             depth++;
15:         } else if ((token == ')') && !depth--) {
16:             operand = arguments.callee(open, index++);
17:             break;
18:         }
19:     } while (index++);
20: } else {
21:     operand = Number(token);
22: }

↑括弧の開始を感知したときは、対応する終了括弧を探して、括弧処理関数を再帰的に呼び出す。

24: var operator = tokens[index++], precedence = binary[operator] || 0;
25: while (stack.length && precedence <= binary[stack[stack.length - 1]]) {
26:     operand = [stack.pop(), stack.pop(), operand];
27: }
28: stack.push(operand, operator);

↑amachangのコードと同じ。

まとめ

このコードを元に改良していこうと思う。

パーサとかの勉強はしたことがないから、ほとんど何もわかっていない><

JavaScriptでなんか新しいことをやってみようと思うと、かならず先にamachangがやってる><

スポンサーサイト

関連記事

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/89-49906f21

トラックバック

[JavaScript] 実数を分数のまま計算するクラス
前回の記事と同じ目的で、値を分数のまま計算するクラスを作った。 細かいエラー処理などはしていないのでどうなるかはわからないが、何らか...
  • 2008-03-09
  • 発信元: 文系大学的IT系の悲哀

コメント

コメントの投稿

お名前
コメント
編集キー
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。