[JavaScript] 分数で計算する中置記法電卓

スポンサーサイト

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

[JavaScript] 分数で計算する中置記法電卓

前回の記事前々回の記事で書いていた数式パーサと分数クラスを改良して、中置記法の数式を分数のまま計算する電卓を書いた。

最終的な目標は、移項のアルゴリズムを実装して、一元一次方程式を解く電卓を作ることだけど、とりあえずは一段落。

設計

数式パーサを書いた前々回の記事では、数式を解釈して配列を使った構文木を返していたが、今回は配列ではなく、operatoroperand1operand2の3つのフィールドを持つBinaryOperationオブジェクトを使った二分木として返すようにした。

BinaryOperationオブジェクトのoperate()メソッドを呼ぶと、子要素のoperate()メソッドを呼びつつ、適切な演算を行って値を返す仕組み。最末端ノードは、operate()メソッドを実装したFractionクラスを使った。

サンプルコード

var operation = parse('1 + 2 * (3 - 4) / 5');
var answer = operation.operate();
alert(answer);              // 3 / 5
alert(answer.valueOf());    // 0.6

実動サンプル

パーサーの仕様は前々回の記事のものに準じる。

計算式
分数
3 / 5
小数
0.6
数式をeval()して得た値
0.6

計算が間違っている可能性もあるので、過度の信頼は禁物。

ソースコード

後々、一元一次方程式を解くことを目標にしてるので、UnknownクラスやhasX()メソッドがあったりする。UnaryOperationクラスも用意したので、いずれはparseのほうを書き換えて、'1+2*-2'のような記述に対応できるようにしたい。

function extend(d, s) { for (var p in s) d[p] = s[p]; }

/** 数式パーサ */
var parse = function(source) {
    var binary = {'+': 1, '-': 1, '*': 2, '/': 2};
    var tokens = source.match(/x|[-+]?\d+(?:\.\d+)?(?:e\d+)?|[-+*/()]/ig);
    return (function parseGroup(index, end) {
        var operand, stack = [];
        while (index < end) {
            var token = tokens[index++];
            if (token != '(') {
                operand = token.match(/x/i) ? new Unknown('x') : new Fraction(token);
            } else {
                var depth = 0, start = index;
                while (token = tokens[index++]) {
                    if (token == '(') depth++;
                    else if ((token == ')') && !depth--) {
                        operand = parseGroup(start, index - 1);
                        break;
                    }
                }
            }

            var operator = tokens[index++], precedence = binary[operator] || 0;
            while (stack.length && precedence <= binary[stack[0]])
                operand = new BinaryOperation(stack.shift(), stack.shift(), operand);
            stack.unshift(operator, operand);
        }
        return operand;
    })(0, tokens.length);
};


/** 分数クラス */
var Fraction = function(num, den) {
    var isFraction = num instanceof arguments.callee;
    this.num = Number(isFraction ? num.num : num || 0);
    this.den = Number(isFraction ? num.den : den || 1);
    this.reduce();
};

extend(Fraction.prototype, {
    valueOf: function() { return this.num / this.den; },
    toString: function() { return this.num + ' / ' + this.den; },
    /** 約分 */
    reduce: function() {
        var num = Math.abs(this.num), den = Math.abs(this.den);
        if (!isFinite(num) || !isFinite(den) || den === 0) throw 'Error';    //XXX
        if (num) {
            var sign = this.num / num * this.den / den;
            while ((num % 1) || (den % 1)) { num *= 10; den *= 10; }    //整数化
            var r, m = Math.max(num, den), n = Math.min(num, den);    //互除法
            while (r = m % n) { m = n; n = r; }
            this.num = sign * num / n;
            this.den = den / n;
        } else {
            this.num = 0;
            this.den = 1;
        }
        return this;
    },
    /** 加算 */
    add: function(n) {
        n = new Fraction(n);
    
        this.num = this.num * n.den + n.num * this.den;
        this.den *= n.den;
    
        return this.reduce();
    },
    /** 減算 */
    subtract: function(n) {
        n = new Fraction(n);
    
        this.num = this.num * n.den - n.num * this.den;
        this.den *= n.den;
    
        return this.reduce();
    },
    /** 乗算 */
    multiply: function(n) {
        n = new Fraction(n);
    
        this.num *= n.num;
        this.den *= n.den;
    
        return this.reduce();
    },
    /** 除算 */
    divide: function(n) {
        n = new Fraction(n);
    
        this.num *= n.den;
        this.den *= n.num;
    
        return this.reduce();
    }
});


/** 単項演算クラス */
var UnaryOperation = function(operator, operand) {
    this.operator = operator;
    this.operand = operand;
};

extend(UnaryOperation.prototype, {
    isAtom: function() { return false; },
    hasX: function() { return this.operand.hasX(); },
    operate: function() {
        switch (this.operator) {
            case '-':
                return this.operand.operate()['*'](-1);
            case '+':
            default:
                return this.operand.operate();
        }
    }
});


/** 二項演算クラス */
var BinaryOperation = function(operator, operand1, operand2) {
    this.operator = operator;
    this.operand1 = operand1;
    this.operand2 = operand2;
};

extend(BinaryOperation.prototype, {
    isAtom: function() { return false; },
    hasX: function() { return this.operand1.hasX() || this.operand2.hasX(); },
    operate: function() { return this.operand1.operate()[this.operator](this.operand2.operate()); }
});


/** 未知数クラス */
var Unknown = function(name) { this.name = name; };
extend(Unknown.prototype, {
    isAtom: function() { return true; },
    hasX: function() { return true; },
    operate: function() { throw 'This is an Unknown Value.'; }
});


/** 分数クラスを拡張 */
extend(Fraction.prototype, {
    '+': Fraction.prototype.add,
    '-': Fraction.prototype.subtract,
    '*': Fraction.prototype.multiply,
    '/': Fraction.prototype.divide,
    isAtom: function() { return true; },
    hasX: function() { return false; },
    operate: function() { return this; }
});

追記

parse()関数を↓のように少しいじるだけで、単項演算子の処理ができるようになった。これで、'1+2*-3.4/-(1+2)'のような数式も処理できるようになった。

/** 数式パーサ */
var parse = function(source) {
    var unary = {'+': 1, '-': 1}, binary = {'+': 1, '-': 1, '*': 2, '/': 2};
    var tokens = source.match(/x|\d+(?:\.\d+)?(?:e\d+)?|[-+*/()]/ig);
    return (function parseGroup(index, end) {
        var stack = [];
        while (index < end) {
            var operand = (function parseUnary(token) {
                if (unary[token]) {
                    return new UnaryOperation(token, parseUnary(tokens[index++]));
                } else if (token == '(') {
                    var depth = 0, start = index;
                    while (token = tokens[index++]) {
                        if (token == '(') depth++;
                        else if ((token == ')') && !depth--)
                            return parseGroup(start, index - 1);
                    }
                } else {
                    return token.match(/x/i) ? new Unknown('x') : new Fraction(token);
                }
            })(tokens[index++]);

            var operator = tokens[index++], precedence = binary[operator] || 0;
            while (stack.length && precedence <= binary[stack[0]])
                operand = new BinaryOperation(stack.shift(), stack.shift(), operand);
            stack.unshift(operator, operand);
        }
        return stack.pop();
    })(0, tokens.length);
};

実動サンプルの方も改良済み。

スポンサーサイト

関連記事

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/91-ed30d817

トラックバック

[JavaScript] 中置記法の一元一次方程式を解く電卓
前回の記事で書いた電卓を発展させて、簡単な一元一次方程式を解くことのできる電卓にしてみた。xを1つだけ含む一次方程式を解くことができる...
  • 2008-03-12
  • 発信元: 文系大学的IT系の悲哀

コメント


So good. & i like this code

v-10


  • 2008-10-23
  • by AJan
  • id:-

コメントの投稿

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