實施調度場算法在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，反之亦然。

Answer 2

您所犯的錯誤是與associativy相反的優先順序。正確的代碼應該看起來像這樣：

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

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