Sunday, December 2, 2012

CalcJS: Evaluating complex math expressions in JavaScript in 120 lines


Sometimes it’s useful to express our math thought more explicitly, so instead of saying: x = 10 * 1.1 * 1.3 we’d prefer to say: cost = 10, price = cost * 1.1, RRP = price * 1.3. CalcJS helps you to evaluate complex math expressions described in human readable format.

Couple of days ago I’ve seen an interesting code snippet of a JavaScript evaluator. I thought the idea is great so I started to experiment: how hard would it be to create a framework that can evaluate complex math expressions that can use variables?

Humans usually express the math expressions in infix format, so I needed to create a simple stack based evaluator that is able to parse infix formulas. The algorithm I used was the Shunting-yard algorithm that was invented by Dijsktra (like so many other great algorithms).

The basic idea is to use two stacks, one for values and one for operators. When we see an operator that’s precedence is smaller than the previous (like + following a *), we evaluate what we've seen so far and keep on working:

4 * 3 + 2
Put 4 on StackNum
Put * on StackOp
Put 3 on StackNum
Evaluate stacks (popNum, popNum, popOp - 4*3) and put it on StackNum
Put + on StackOp
Evaluate stacks (12 + 2) and put it on StackNum
The result would be on StackNum.
(the process is a bit more complicated if we care for parenthesis “()” but the logic is the same).

Dynamic language helps

As JavaScript is a dynamic and very forgiving language, this process can be expressed very efficiently. Basically anything can be used as an array, stack, or object, so there is no need to create generic dictionaries and stacks, the code is much cleaner:

In Java:
LinkedList<Integer> stackNum = new LinkedList<Integer>();
stackNum.push(1);
Hashtable<String, Integer> variables = new Hashtable<String, Integer>();
variables.put(“abc”,11);
Integer i = variables.get(“abc”);

In JavaScript:
var stackNum = [];
stackNum.push(1);
var variables = {};
variables[‘abc’] = 11;
var i = variables[‘abc’];

Using these tricks, the code is much less noisy and the whole framework was not longer than 120 lines (uncompressed, unoptimized) which was a pleasant surprise.

CalcJS usage

The evaluator will treat everything as a variable if it’s not a well-known operator or number, so there is no need for any fancy syntax. The calc() function accepts a list of (one or more) { 'variable' : 'expression'} pairs. These expressions can be added later on too:

var m = new CalcJS();

m.calc({ 'compAprice': '23' });
m.calc({ 'compBprice': '11' });
m.calc({ 'shoploss': '11' });

m.calc({ 'prodloss': '(shoploss + 1 ) / 4' });

m.calc({
    'sellprice': '(compAprice + compBprice + prodloss ^ 2) * 1.6',
    'retailprice': '(sellprice + ( 2 * shoploss)) * 1.1'
})

console.log(m.variables.retailprice);

In the above example we are calculating the sell price and retail price for a product that consists of two main parts (compA and compB). If we wanted to express the same logic in one line using standard JavaScript, it would look like this:
((23+11+((11+1)/4)^2) * 1.6 + (2 * 11)) * 1.1
Using the former easy-to-read expressions, the code is much more maintainable. Even power-users could express and store their calculations in a web facing system, like a webshop.

CodeJS

The full source code is below, free to use.
Questions, suggestions? Please send a comment!

function CalcJS() {
this.opvalues = { '(': -1, ')': -1, '+': 0, '-': 0, '/': 1, '*': 1, '^': 2 };
this.variables = {};
var stackop = [];
var stacknum = [];

this.tokenize = function (str) {
            str = str.replace(/\s/g, '');
            for (var i in this.opvalues) {
                var regex = new RegExp("\\" + i, "g");
                str = str.replace(regex, '#' + i + '#');
            }
            return str.split('#');
        }

this.compareOps = function (curr, prev) {
            var currvalue = this.opvalues[curr];
            var prevvalue = this.opvalues[prev];
            if (currvalue < prevvalue) return -1;
            if (currvalue > prevvalue) return 1;
            return 0;
        }

this.calculateStack = function (stopchar) {
            while (stackop.length > 0 && stackop[stackop.length - 1] != '(') {
                var op = stackop.pop();
                var right = stacknum.pop();
                var left = stacknum.pop();

                switch (op) {
                    case '+':
                        stacknum.push(left + right);
                        break;
                    case '-':
                        stacknum.push(left - right);
                        break;
                    case '/':
                        stacknum.push(left / right);
                        break;
                    case '*':
                        stacknum.push(left * right);
                        break;
                    case '^':
                        stacknum.push(Math.pow(left, right));
                        break;
                    default:
                        throw new Error('Unknown operator: ' + op);
                }
            }

            if (stopchar && stackop[stackop.length - 1] == '(') {
                stackop.pop();
            }
        }

this.processTokens = function (arr, variables) {
    for (var i = 0; i < arr.length; i++) {
        var a = arr[i];
        if (a == '') continue;
        if (variables[a]) {
            a = variables[a];
        }

        var parsed = parseFloat(a);
        if (isNaN(parsed)) {
            if (stackop.length == 0 || a == '(') {
                stackop.push(a);
                continue;
            }

            if (a == ')') {
                this.calculateStack('(');
                continue;
            }

            var prev = stackop[stackop.length - 1];

            var comp = this.compareOps(a, prev);

            if (comp < 0) {
                this.calculateStack();
            }

            stackop.push(a);
        }
        else {
            stacknum.push(parsed);
        }
    }

    this.calculateStack();

    if (stacknum.length != 1) throw new Error('Invalid expression');

    return stacknum.pop();
}

this.calc = function (input) {
            for (var i in input) {
                var variablename = null;
                var expr = null;

                if (!variablename) {
                    variablename = i;
                    expr = input[variablename];

                    var arr = this.tokenize(expr);
                    var result = this.processTokens(arr, this.variables);
                    this.variables[variablename] = result;

                    variablename = null;
                    expr = null;
                }
            }

            if (stackop.length != 0) throw new Error('Invalid expression');
            return this.variables;
        }
}

// Sample usage

var m = new CalcJS();
m.calc({ 'compAprice': '23' });
m.calc({ 'compBprice': '11' });
m.calc({ 'shoploss': '11' });
m.calc({ 'prodloss': '(shoploss + 1 ) / 4' });
m.calc({
'sellprice': '(compAprice + compBprice + prodloss ^ 2) * 1.6',
'retailprice': '(sellprice + ( 2 * shoploss)) * 1.1'
});
console.log(m.variables.retailprice);
// Outputs 99.88000000000001


No comments:

Post a Comment