[JavaScript] 中置記法の一元一次方程式を解く電卓 / LiosK-free Blog

[JavaScript] 中置記法の一元一次方程式を解く電卓

前回の記事で書いた電卓を発展させて、簡単な一元一次方程式を解くことのできる電卓にしてみた。xを1つだけ含む一次方程式を解くことができる。

例

alert(calc('-x+1=2-3'));                   // 2 / 1
alert(calc('3*3/(2-x)=4+(2/3*4)+1.2'));    // 101 / 118
alert(calc('(8-5)/3=1/(x+2)-1.3*0.4'));    // -51 / 38

括弧と単項演算子を使うことができます。今のところ、xは数式中に1つだけしか含めることができません。

実動サンプルとソースコードは続きで。

動作サンプル

数式
分数解: 2 / 1
小数解: 2

前回の記事からの主な変更点

まず、UnaryOperationクラスとBinaryOperationクラスとFractionクラスとUnknownクラスに、typeフィールドを持たせ、それぞれ'Unary', 'Binary', 'Atomic', 'Atomic'という値を持たせた。そして、このtypeフィールドを見ながら、解を計算するsolve()関数を↓のように書いた。

var solve = function(left, right) {
    var hasLeftX = left.hasX();
    if (!hasLeftX == !right.hasX()) throw 'Error';    //XXX
    var variable =  hasLeftX ? left : right;
    var constant = (hasLeftX ? right : left).operate();

    switch (variable.type) {
        case 'Atomic':
            return constant;
        case 'Unary':
            return solve(variable.operand, new UnaryOperation(variable.operator, constant));
        case 'Binary':
            var canceler = ({'+': '-', '-': '+', '*': '/', '/': '*'})[variable.operator];
            switch (canceler) {
                case '+': case '*':
                    return solve(variable.operand1, new BinaryOperation(canceler, variable.operand2, constant));
                case '-': case '/':
                    return solve(variable.operand1, new BinaryOperation(canceler, constant, variable.operand2));
            }
    }
};

そして、生の数式を受け取って、パースした後にsolve()関数に渡すcalc()関数を↓のように定義。

function calc(source) {
    var sides = source.split('=');
    return solve(parse(sides[0]), parse(sides[1]));
}

`solve()`関数の解説

var hasLeftX = left.hasX();
if (!hasLeftX == !right.hasX()) throw 'Error';    //XXX
var variable =  hasLeftX ? left : right;
var constant = (hasLeftX ? right : left).operate();

最初の4行は、左辺式と右辺式を受け取って、未知数を含む辺と含まない辺とに分けてしまうところ。!hasLeftX == !right.hasX()は排他的論理輪の否定で、両辺ともに未知数を含んでいたり、逆に両辺ともに未知数を含まなかった場合に例外を投げる。未知数を含まない方の辺は、operate()メソッドを呼び出して計算してしまう。

switch文以下は、未知数を含む辺のtypeフィールドを見て動作を変える。UnaryOperationオブジェクトやBinaryOperationオブジェクトであれば、定数辺に打消演算をしつつ再帰的にsolve()を呼び出し、最後にUnknownオブジェクトにたどり着いたら、定数辺を方程式の解として返す仕組み。

case 'Atomic':
    return constant;

typeが'Atomic'の場合、その辺は未知数が単独で存在するだけの辺なので、定数辺を未知数の解として返す。

case 'Unary':
    return solve(variable.operand, new UnaryOperation(variable.operator, constant));

typeが'Unary'であれば、定数辺に同じ演算を行った後、オペランドと定数辺を再帰的にsolve()関数に渡す。

case 'Binary':
    var canceler = ({'+': '-', '-': '+', '*': '/', '/': '*'})[variable.operator];
    switch (canceler) {
        case '+': case '*':
            return solve(variable.operand1, new BinaryOperation(canceler, variable.operand2, constant));
        case '-': case '/':
            return solve(variable.operand1, new BinaryOperation(canceler, constant, variable.operand2));
    }

typeが'Binary'であれば、打消演算をされた定数辺とオペランドとを再帰的にsolve()関数に渡す。打消演算子が、+, *の場合と-, /の場合とで分けているのは、打消演算子が交換法則を満たすときに、constantとvariable.operand2とを入れ替えるため。この仕組みを実装しないと、variable.operand2が未知数を含むときに、再帰が止まらなくなる(variable.operand1が未知数を含むことを暗黙に仮定しているアルゴリズムであるため)。

ソースコード

まだまだ最適化の余地はありそう…

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

function calc(source) {
    var sides = source.split('=');
    return solve(parse(sides[0]), parse(sides[1]));
}

/** 数式パーサ */
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 isNaN(token) ? new Unknown(token) : 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);
};

/** 一元一次方程式を解く */
var solve = function(left, right) {
    var hasLeftX = left.hasX();
    if (!hasLeftX == !right.hasX()) throw 'Error';    //XXX
    var variable =  hasLeftX ? left : right;
    var constant = (hasLeftX ? right : left).operate();

    switch (variable.type) {
        case 'Atomic':
            return constant;
        case 'Unary':
            return solve(variable.operand, new UnaryOperation(variable.operator, constant));
        case 'Binary':
            var canceler = ({'+': '-', '-': '+', '*': '/', '/': '*'})[variable.operator];
            switch (canceler) {
                case '+': case '*':
                    return solve(variable.operand1, new BinaryOperation(canceler, variable.operand2, constant));
                case '-': case '/':
                    return solve(variable.operand1, new BinaryOperation(canceler, constant, variable.operand2));
            }
    }
};


/** 分数クラス */
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, {
    type: 'Unary',
    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, {
    type: 'Binary',
    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, {
    type: 'Atomic',
    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,
    type: 'Atomic',
    hasX: function() { return false; },
    operate: function() { return this; }
});

トラックバックURL

http://liosk.blog103.fc2.com/tb.php/92-746c4092

1 件のトラックバック

一次方程式を解ける電卓サイト

[JavaScript] 中置記法の一元一次方程式を解く電卓 http://liosk.blog103.fc2.com/blog-entry-92.html 中学1年あたりの皆さん、これは役立つと思いますよ。まあ、方程式が解ける電卓といったら、専門店などで買えるのですが、今回紹介するのは、「無料」�...

2009-09-23
発信元: 多分毎日更新！SUGAZINE！(シュガジン)

LiosK-free Blog