js解析字符串四则表达式

记得大学时学到过解析字符串四则表达式，好像是数据结构里的课程。具体的内容都忘掉了，也找不到数据机构课本，就在网上找了些相关资料，现在用js实现一下。具体思路是把普通的表达式转换为前置或者后置表达式，然后通过转换后的表达式来计算。

当然，是有需求了才这么做。在js中通过eval或着Function都可以实现类似功能。通过测试，在非ie浏览器中解析表达式的效率比eval（Function）高，在ie中正好相反。由于客户的大多使用的是ie，就采用了Function的方式。

代码如下：

 

(function () {
    var priority = {
        '*': 2,
        '/': 2,
        '+': 1,
        '-': 1
    }, strExpression2arrExpression = function (expression) {//字符串转换为数组
        var arr = [];
        for (var i = 0, s, t, l = expression.length; i < l; i++) {
            s = expression.charAt(i);
            if (isNaN(s)&&s!='.') {
                arr.push(s);
            } else {
                t = s;
                while (i < l) {
                    s = expression.charAt(i + 1);
                    if (!isNaN(s)||s=='.') {
                        t += s;
                        i++;
                    } else {
                        break;
                    }
                }
                arr.push(parseFloat(t));
            }
        }
        return arr;
    }, infixExpression2prefixExpression = (function () { //将中缀表达式转换为前缀表达式
        var s1 = [], s2 = [], operator = function (o) {
            var last = s1[s1.length - 1];
            if (s1.length == 0 || last == ')') {
                s1.push(o);
            } else if (priority[o] >= priority[last]) {
                s1.push(o);
            } else {
                s2.push(s1.pop());
                operator(o);
            }
        };
        return function (arrExpression) {
            s1.length = 0;
            s2.length = 0;
            for (var i = arrExpression.length - 1, o; i >= 0; i--) {
                o = arrExpression[i]
                if (!isNaN(o)) {
                    s2.push(o);
                } else {
                    if (o == '+' || o == '-' || o == '*' || o == '/') {//运算符
                        operator(o)
                    } else {//括号
                        if (o == ')') {//右括号
                            s1.push(o)
                        } else {//左括号
                            var s = s1.pop();
                            while (s != ')') {
                                s2.push(s);
                                s = s1.pop();
                            }
                        }
                    }
                }
            }
            if (s1.length > 0) {
                while (s1[0] != undefined) {
                    s2.push(s1.pop())
                }
            }
            s1.length = 0;
            return s2.slice();
        }
    })(), computePrefixExpression = (function () {
        var s1 = [], result;
        return function (prefixExpression) {
            s1.length = 0;
            //计算
            while (prefixExpression.length > 0) {
                var o = prefixExpression.shift();
                if (!isNaN(o)) {
                    s1.push(o);
                } else {
                    switch (o) {
                        case '+':
                        {
                            result = s1.pop() + s1.pop();
                            break;
                        }
                        case '-':
                        {
                            result = s1.pop() - s1.pop();
                            break;
                        }
                        case '*':
                        {
                            result = s1.pop() * s1.pop();
                            break;
                        }
                        case '/':
                        {
                            result = s1.pop() / s1.pop();
                            break;
                        }
                    }
                    s1.push(result);
                }
                //console.log(s2,s1)
            }
            //console.log(s1)
            return s1[0];
        }
    })();
    window.compute = function (expression) {
        //console.log(strExpression2arrExpression(expression))
        //console.log(infixExpression2prefixExpression(strExpression2arrExpression(expression)).reverse())
        return computePrefixExpression(infixExpression2prefixExpression(strExpression2arrExpression(expression)));
    }
})();

 

测试结果如下：

 

console.log(compute('100/(1.5+10/((2+3)*4)-5)*10'))
eval('console.log(100/(1.5+10/((2+3)*4)-5)*10)')

 

-333.33333333333337

 

-333.33333333333337

 

本文参考了antineutrino的文章《前缀、中缀、后缀表达式》，讲得很不错，具体原理大家可以学习一下。

有兴趣了可以看看本人的一个在线demo。