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

我学习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 + - * +

[请原谅我的格式，我在移动电话上]

最佳答案

你混淆了两个变量
在检查优先级的部分：

&& ((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只保存数字，所以这总是错误的。将assocs更改为prec，反之亦然。