用javascript解析算术表达式

有没有一种简单的方法，用javascript来转换以下表达式

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

变成类似的东西

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

表达式将存储在字符串中。我愿意接受任何可以避免我编写自己的解析器的解决方案（库、内置功能……）

EDIT：我应该明确指出我实际上不想使用multiply and add函数，这样做的目的是定义我自己的函数来替换multiply and add并对变量执行自定义操作

您尝试解析为抽象语法树的表达式是上下文无关表达式。这意味着您需要上下文无关语法才能解析它。那么让我们创建一个解析器。

为了简化解析，我们将分离词法分析阶段。因此，我们需要的第一件事是创建一个词法分析器。幸运的是，有很多方便的词法分析器库可用。我们将使用这个：

https://github.com/aaditmshah/lexer https://github.com/aaditmshah/lexer

这是词法分析器：

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. "(", "+", "-", "*", "/", ")")
});

接下来我们创建一个解析器。我们将使用以下 Dijkstra 调车场算法的实现来进行解析：

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

所以这是解析器：

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

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

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

最后我们创建一个parse函数如下：

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

现在你只需调用parse以后缀表示法获取已解析的标记流：

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

后缀形式的优点是你可以使用堆栈轻松地操作它：

1. Push e到堆栈上。
2. Push a到堆栈上。
3. Push b到堆栈上。
4. Push c到堆栈上。
5. Pop b and c并推b + c到堆栈上。
6. Pop a and b + c并推a * (b + c)到堆栈上。
7. Push d到堆栈上。
8. Pop a * (b + c) and d并推a * (b + c) + d到堆栈上。
9. Pop e and a * (b + c) + d并推e * (a * (b + c) + d)到堆栈上。

同样，使用堆栈也可以轻松创建所需的输出。都是同样的步骤。您只需将不同的值推回堆栈以进行不同的操作。

看演示：http://jsfiddle.net/d2UYZ/2/ http://jsfiddle.net/d2UYZ/2/

Edit 1:我实在是太无聊了，所以我为你解决了这个问题：

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);

输出是（如您所料）字符串"multiply(e, add(multiply(a, add(b,c)), d))"。看演示：http://jsfiddle.net/d2UYZ/4/ http://jsfiddle.net/d2UYZ/4/

Edit 2:如果您需要评估表达式，您也可以轻松完成。您所需要的只是将符号映射到每个运算符的值和函数的上下文：

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();

因此表达式e*((a*(b+c))+d)变成5*((1*(2+3))+4)其评估结果为45。看演示：http://jsfiddle.net/d2UYZ/6/ http://jsfiddle.net/d2UYZ/6/