Implementing Shunting Yard Algorithm in JavaScript

Question

I've been learning JavaScript for just about a month, and I'm trying to implement the Shunting Yard Algorithm

However, I seem to have a logic error somewhere (probably in the while loop) but I can't for the life of me figure it out.

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"));

Correct output:

5 3 6 * + 5 3 / - 7 +

Actual output:

5 3 6 5 3 / 7 + - * +

[Please excuse the formatting; I'm on mobile]

Answer 1

You mixed up 2 variables

In the part where you check the precedence:

&& ((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]

you check if assoc[v] is left or not. Assoc only holds numbers, so this'll be always false. Change the assocs to prec and vice-versa.

Answer 2

The mistake you did is to inverse precedence with associativy. The correct code should look like that:

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

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