演算子順位解析(js)

parse-priority-operator.js

function parse(str) {
    /**
    演算子順位解析
    http://fujimura2.fiw-web.net/java/mutter/operator-precedence/index.html

    -1: x(パースエラー)
    0: shift
    1: reduce
    2: pop
    3: end
    */
    function priority(a, b) {
        a = a == "-" ? "+" : a == "/" ? "*" : a;
        b = b == "-" ? "+" : b == "/" ? "*" : b;

        // 許されない文法
        if ( a == "(" && b == "$" || a == ")" && b == "(" || a == "^" && b == ")" ) return -1;

        // 括弧の対応
        if ( a == "(" && b == ")" ) return 2;

        // 解析終了
        if ( a == "^" && b == "$" ) return 3;

        // その他
        if ( a == "+" ) { if ( /\+|\(|\)|\$/.test(b) ) return 1; return 0; }
        if ( a == "*" ) { if ( /\+|\*|\)|\$/.test(b) ) return 1; return 0; }
        if ( a == "(" ) return 0;
        if ( a == ")" ) { if ( /\+|\*|\)|\$/.test(b) ) return 1; return 0; }
        if ( a == "^" ) return 0;
    }

    function getFirstOperator(list) {
        for ( var i = list.length - 1; i >= 0; i-- ) {
            if ( !/\d+/.test(list[i]) ) return list[i];
        }
        return null;
    }

    var exec = {
            "+": function(a, b) { return a + b; },
            "-": function(a, b) { return a - b; },
            "*": function(a, b) { return a * b; },
            "/": function(a, b) { return a / b; }
        },
        stack = ["^"];

    str += "$";

    for ( var i = 0; i < str.length; i++ ) {
        var n = str[i];

        if ( /\d/.test(n) ) {
            // 数値ならスタックに詰む
            stack.push(+n);
        } else {
            // 演算子なら

            while(true) {
                // スタックの最も先頭の演算子を取得し入力と比較する
                var o = getFirstOperator(stack),
                    p = priority(o, n);

                if ( p == 0 ) {
                    stack.push(n);
                    break;

                } else if ( p == 1 ) {
                    var a = stack.pop(),
                        o = stack.pop(),
                        b = stack.pop();

                    stack.push(exec[o](a, b));
                    // breakしない(演算子の比較をもう一度)

                } else if ( p == 2 ) {
                    var a = stack.pop();

                    stack.pop(); // (を取り除く
                    stack.push(a);
                    break;

                } else if ( p == 3 ) {
                    return stack.pop();
                }
            }
        }
    }
}

var test1 = "1+2*3";    // ans:7
var test2 = "(1+2)*3";  // ans:9

console.log(parse(test1));
console.log(parse(test2));