javascript - 在 JavaScript 中实现调车场算法

Question

我已经学习 JavaScript 大约一个月了，我正在尝试实现 Shunting Yard Algorithm

但是，我似乎在某处(可能在 while 循环中)有逻辑错误，但我终究无法弄清楚。

var parser = function(inp){
    var outQueue=[];
    var opStack=[];

    Array.prototype.peek = function() {
        return this.slice(-1)[0];
};

    //tokenize
    var inArr=tokenize(inp);
 var top;
    var prec = {
        "^" : "right",
       "*" : "left",
        "/" : "left",
        "+" : "left",
    "-" : "left"
};

   var assoc = {
       "^" : 4,
       "*" : 3,
    "/" : 3,
    "+" : 2,
    "-" : 2
    };

    inArr.forEach(function(v) {
    //If the token is a number, then push it to the output queue
    if(v.match(/\d+/)) {
        outQueue.push(v);
    } 
    //If the token is an operator, o1, then:
    else if(v.match(/[+*-/^]/)) {
        if (opStack.peek()) {
        top = opStack.peek();
        //while there is an operator token o2, at the top of the operator stack and
        while(top.match(/[+*-/^]/) 
            //either o1 is left-associative and its precedence is less than or equal to that of o2,
            && ((assoc[v]==="left" && prec[v] <= prec[top])
                //or o1 is right associative, and has precedence less than that of o2,
                || (assoc[v]==="right" && prec[v] < prec[top]))) {
                    outQueue.push(opStack.pop());
                top = opStack.peek();
        }
    }
        //at the end of iteration push o1 onto the operator stack
        opStack.push(v);
    } 
    //If the token is a function token, then push it onto the stack.
    else if(v.match(/(sin|cos|tan)/)) {
        opStack.push(v);

    } 
    //If the token is a function argument separator 
    else if(v===",") {
        //Until the token at the top of the stack is a left parenthesis
        //pop operators off the stack onto the output queue.
        while(opStack.peek() != "(") {
            outQueue.push(opStack.pop());
        }
        /*if(opStack.length == 0){
            console.log("Mismatched parentheses");
            return;
        }*/
    } 
    //If the token is a left parenthesis (i.e. "("), then push it onto the stack.
    else if(v==="(") {
        opStack.push(v);
    }
    //If the token is a right parenthesis (i.e. ")"):
    else if(v===")") {
        //Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        while(opStack.peek() != "(") {
            outQueue.push(opStack.pop());
        }
        /*if(opStack.length == 0){
            console.log("Unmatched parentheses");
            return;
        }*/
        //Pop the left parenthesis from the stack, but not onto the output queue.
        opStack.pop();

        //If the token at the top of the stack is a function token, pop it onto the output queue.
        if(opStack.peek().match(/(sin|cos|tan)/)) {
            outQueue.push(opStack.pop());
        }
    }
});

return outQueue.concat(opStack.reverse()).join(" ");
 };

function tokenize(arg) {
    return arg.split(" ");
}

console.log(parser("5 + 3 * 6 - ( 5 / 3 ) + 7"));

正确的输出:

5 3 6 * + 5 3 / - 7 +

实际输出:

5 3 6 5 3 / 7 + - * +

[请原谅格式化；我在移动]

Answer 1

你混淆了 2 个变量

在检查优先级的部分:

&& ((assoc[v]==="left" && prec[v] <= prec[top])
            //or o1 is right associative, and has precedence less than that of o2,
            || (assoc[v]==="right" && prec[v]

你检查 assoc[v] 是否被留下。 Assoc 只保存数字，所以这永远是错误的。将 assoc 更改为 prec，反之亦然。