使用javascript解析算术表达式

Question

是否有一种简单的方法,使用javascript,转换以下表达式

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

变成类似的东西

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

表达式将存储在字符串中.我愿意接受任何可以避免编写自己的解析器的解决方案(库,buitl-in功能,......)

编辑:我应该已经预先确定我实际上并不想使用乘法和添加函数,这样做的目的是定义我自己的函数来替换乘法并添加并对变量执行自定义操作

Answer 1

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

为了简化解析,我们将分离词法分析阶段.因此,我们首先需要创建一个词法分析器.幸运的是,有很多方便的词法分析库可用.我们将使用这个:

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

所以这是解析器:

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 + *"

postfix表单的优点是你可以使用堆栈轻松地操作它:

1. 推e到堆栈上.
2. 推a到堆栈上.
3. 推b到堆栈上.
4. 推c到堆栈上.
5. 弹出b并c推入b + c堆栈.
6. 弹出a并b + c推入a * (b + c)堆栈.
7. 推d到堆栈上.
8. 弹出a * (b + c)并d推入a * (b + c) + d堆栈.
9. 弹出e并a * (b + c) + d推入e * (a * (b + c) + d)堆栈.

同样,使用堆栈也可以轻松创建所需的输出.它的步骤相同.您只需将不同的值推回堆栈以进行不同的操作.

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

编辑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/

编辑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/