Parsing operators and evaluating them in JavaScript [closed]

Question

I wanted to parse a string which has an if statement and evaluate its output.

I can get with evaluation part but other one is getting too complicated for me.

Take the following examples:

• if $a == 10 && ($b == '5' || $c == 'test')
• if $x != 10 || $y == false
• if $z < 10

I want to get them in array -- that is, the output that I want for the corresponding example would be:

• [ [ '$a', '==', '10' ], '&&', [ [ '$b', '==', '5' ], '||', [ '$c', '==', 'test' ] ] ]
• [ [ '$x', '!=', '10' ], '||', [ '$y', '==', 'false' ] ]
• [ '$z', '<', '10' ]

I guess I'm asking for far too much logic/code but it would be great if anyone could help me with this. Use of regular expressions or normal string parsing is okay.

Answer 1

If you simply want to parse your string then there are a lot of JavaScript parsing libraries which can do that for you. For example you can parse valid JavaScript code using acorn into a Mozilla AST. You can also convert it back to a string using escodegen.

Unfortunately your string doesn't appear to be valid JavaScript code, but if you remove the if at the beginning of each string then you can definitely parse the string using acorn. The output will be an AST, which is not what you're looking for, but you can easily convert it into the format you desire.

Using a full fledged parser however for such a trivial use case is in my humble opinion an overkill. For example if you simply want to evaluate your string then you can use the Function constructor as follows:

function read(expression) {
    var variables = expression.match(/\$\w+/g);
    var length = variables.length;
    var uniqueVariables = [];
    var index = 0;

    while (index < length) {
        var variable = variables[index++];
        if (uniqueVariables.indexOf(variable) < 0)
            uniqueVariables.push(variable);
    }

    return Function.apply(null, uniqueVariables.concat("return " + expression));
}

This read function allows you to read expressions as follows:

var condition = read("$a == 10 && ($b == '5' || $c == 'test')");

You may now use the condition function as follows:

alert(condition(10, "10", "test")); // true
alert(condition(5, "10", "test")); // false

See the demo for yourself: http://jsfiddle.net/ZnUh2/

Of course you'll need to remove the if at the beginning of all your strings to read them. This can easily be done by using string.slice(2) to remove the if.

If you're hell bent on converting your string into an array though then that's going to take a little more work, but it can easily be done by using a lexical analyzer like Lexer. The first thing you'll need to do is write some rules for different types of tokens:

var lexer = new Lexer;

lexer.addRule(/\s+/, function () { /* skip whitespace */ });

lexer.addRule(/if\b/g, function () { /* skip the if keyword */ });

// match opening parentheses
lexer.addRule(/\(/, function () { return "("; });

// match closing parentheses
lexer.addRule(/\)/, function () { return ")"; });

// match any other token
lexer.addRule(/[^\s\(\)]+/, function (lexeme) { return lexeme; });

Note that this lexer expects every token (except parentheses) to have whitespace in between them. For example $a==10 would be considered one token but $a == 10 would be considered as 3 tokens.

The next thing you need is a rudimentary parser. You could implement one by hand but it would be a pain to write all the operator precedence rules yourself. Instead I would suggest that you use the following parser based on Dijkstra's shunting yard algorithm.

We can now create a parser as follows:

var relational = {
    precedence: 3,
    associativity: "left"
};

var equality = {
    precedence: 2,
    associativity: "left"
};

var parser = new Parser({
    "<":  relational,
    "<=": relational,
    ">":  relational,
    ">=": relational,
    "==": equality,
    "!=": equality,
    "&&": {
        precedence: 1,
        associativity: "right"
    },
    "||": {
        precedence: 0,
        associativity: "right"
    }
});

Finally we write the code to connect the lexer to the parser and generate the desired output:

function parse(string) {
    lexer.setInput(string);

    var tokens = [], token;

    while (token = lexer.lex()) tokens.push(token);
    tokens = parser.parse(tokens);

    var stack = [], length = tokens.length, index = 0;

    while (index < length) {
        token = tokens[index++];

        switch (token) {
        case "<":
        case "<=":
        case ">":
        case ">=":
        case "==":
        case "!=":
        case "&&":
        case "||":
            var b = stack.pop();
            var a = stack.pop();
            stack.push([a, token, b]);
            break;
        default:
            stack.push(token);
        }
    }

    return stack.length && stack[0];
}

That's it. Now you can parse your string into an array as follows:

var array = parse("if $a == 10 && ($b == '5' || $c == 'test')");

To see the output you can use JSON.stringify. See the demo for yourself: http://jsfiddle.net/d2UYZ/3/