Parse arithmetic expression with javascript

Question

Is there a simple way, with javascript, to convert the following expression

e*((a*(b+c))+d)

into something like

multiply(e, add(multiply(a, add(b,c)), d))

The expression would be stored in a string. I'm open to any solution that will avoid me to write my own parser (library, buitl-in capabilities, ...)

EDIT: I should have precised that I don't actually want to use multiply and add functions, the purpose of this is to define my own function to replace multiply and add and perform custom operations on the variables

Answer 1

The expression you are trying to parse into an abstract syntax tree is a context-free expression. This means that you need a context-free grammar to be able to parse it. So let's create a parser.

To simplify the parsing we'll separate the lexical analysis phase. Hence the first thing we need is to create a lexer. Luckily there are a lot of handy lexer libraries available. We'll use the this one:

https://github.com/aaditmshah/lexer

So here's the lexical analyzer:

var lexer = new Lexer;

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

lexer.addRule(/[a-z]/, function (lexeme) {
    return lexeme; // symbols
});

lexer.addRule(/[\(\+\-\*\/\)]/, function (lexeme) {
    return lexeme; // punctuation (i.e. "(", "+", "-", "*", "/", ")")
});

Next we create a parser. We'll use the following implementation of Dijkstra's shunting yard algorithm for parsing:

https://gist.github.com/aaditmshah/6683499

So here's the parser:

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

var term = {
    precedence: 1,
    associativity: "left"
};

var parser = new Parser({
    "+": term,
    "-": term,
    "*": factor,
    "/": factor
});

Finally we create a parse function as follows:

function parse(input) {
    lexer.setInput(input);
    var tokens = [], token;
    while (token = lexer.lex()) tokens.push(token);
    return parser.parse(tokens);
}

Now you simply call parse to get a parsed stream of tokens in postfix notation:

var output = parse("e*((a*(b+c))+d)");
alert(output.join(" "));               // "e a b c + * d + *"

The advantage of postfix form is that you can easily manipulate it using a stack:

1. Push e onto the stack.
2. Push a onto the stack.
3. Push b onto the stack.
4. Push c onto the stack.
5. Pop b and c and push b + c onto the stack.
6. Pop a and b + c and push a * (b + c) onto the stack.
7. Push d onto the stack.
8. Pop a * (b + c) and d and push a * (b + c) + d onto the stack.
9. Pop e and a * (b + c) + d and push e * (a * (b + c) + d) onto the stack.

Similarly it's easy to create the output you want using stacks too. It the same steps. You only push different values back onto the stack for different operations.

See the demo: http://jsfiddle.net/d2UYZ/2/

Edit 1: I was so bored that I solved the problem for you:

var stack = [];

var operator = {
    "+": "add",
    "-": "subtract",
    "*": "multiply",
    "/": "divide"
};

parse("e*((a*(b+c))+d)").forEach(function (c) {
    switch (c) {
    case "+":
    case "-":
    case "*":
    case "/":
        var b = stack.pop();
        var a = stack.pop();
        stack.push(operator[c] + "(" + a + ", " + b + ")");
        break;
    default:
        stack.push(c);
    }
});

var output = stack.pop();

alert(output);

The output is (as you expect) the string "multiply(e, add(multiply(a, add(b,c)), d))". See the demo: http://jsfiddle.net/d2UYZ/4/

Edit 2: If you need to evaluate the expression you could do that easily too. All you need is a context mapping symbols to values and functions for each operator:

var stack = [];

var context = {
    "a": 1,
    "b": 2,
    "c": 3,
    "d": 4,
    "e": 5
};

var operator = {
    "+": function (a, b) { return a + b; },
    "-": function (a, b) { return a - b; },
    "*": function (a, b) { return a * b; },
    "/": function (a, b) { return a / b; }
};

parse("e*((a*(b+c))+d)").forEach(function (c) {
    switch (c) {
    case "+":
    case "-":
    case "*":
    case "/":
        var b =+ stack.pop();
        var a =+ stack.pop();
        stack.push(operator[c](a, b));
        break;
    default:
        stack.push(context[c]);
    }
});

var output = stack.pop();

Thus the expression e*((a*(b+c))+d) becomes 5*((1*(2+3))+4) which evaluates to 45. See the demo: http://jsfiddle.net/d2UYZ/6/

Answer 2

You cannot do this with eval as has been suggested, because you would not be able to use your custom add and multiply functions that way. You could parse out all of the operators with regular expressions, but it would not be easy.

You would have to make sure you got the order of operations correct, and break it into many steps.

The basic logic of it would be:

1. Define your add and multiply functions.

2. Define a function that takes a string of numbers and operators (without parentheses) and splits it into binary operations (ie. '1 + 7' or '5 * 3') with regular expressions, that can be passed to your add and multiply functions. This would have to be done recursively, following your desired order of operations for your custom math, in other words, if you get '5 + 3 * 2' you will have parse out '3 * 2' and evaluate that before using its result to add to 5 (assuming your order would be multiply first).

3. Define a function that looks for parentheses and recursively finds the innermost set and passes it to function 2 above to be evaluated.

4. Pass your input string to function 3 above and hope that you got all of the recursive logic and regular expressions correct.

Answer 3

I think the better way is define your own functions like this:

multiply = function(a, b) {
    return a *  b;
}

add = function(a, b) {
    return a +  b;
}

This examples is limited to only two numbers, but it can be scaled using arguments.

Fiddle