在 JavaScript 中实现调车场算法

Question

我已经学习JavaScript大约一个月了，我正在尝试实现调车场算法

但是，我似乎在某处（可能在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 s 更改为 prec，反之亦然。

Answer 2

您犯的错误是将优先级与关联反转。正确的代码应如下所示：

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