Trouble with the Shunting Yard Algorithm

Question

EDIT: Complete code with interactivity: http://jsfiddle.net/LDEGe/2/

I am an introductory CS student in high school, and as a side project unrelated to the class, I'm trying to create a simple math equation parser using the Shunting-Yard Algorithm. I understand the pseudocode here, but I am having trouble converting it into Javascript code. I've created a stack and queue object here

function Queue(){
    this.stack=new Array();
    this.dequeue=function(){
        return this.stack.pop();
    };
    this.enqueue=function(addition){
        this.stack.unshift(addition);
    };
}
function Stack(){
    this.stack=new Array();
    this.pop=function(){
        return this.stack.pop();
    };
    this.push=function(item){
        this.stack.push(item);
    };
    this.peek=function(){
        return this.stack[this.stack.length-1];
    };
    this.empty=function(){
        return (this.stack.length<1);
    };
}

To start, I'm just using simple math operators, + - * / ^, and tokenizing the string by putting a space around each operator, then splitting it, and converting each token into an object, with the type, precedence, and associativity, like this

function tokenize(input){
    input=str_replace(["+","-","*","/","^","(",")"],[" + "," - "," * "," / "," ^ "," ( "," ) "],input).replace(/\s{2,}/g, ' ').trim().split(" ");
    for(var i in input){
        input[i]=new operator(input[i]);
    }
    return input;
}

to convert it to an object, I run it through this function, which just sees what the input is, and then assigns it precedence, associativity, a name, and a type

function operator(name){
    this.name=name;
    this.associativity="left";
    this.type="operator";
    this.precedence=1;
    if(isNumeric(name)){
        this.type="numeric";
    }
    else if(name=="("){
        this.type="open";
    }else if(name==")"){
        this.type="close";
    }else if(name=="^"){
        this.precedence=10;
        this.associativity="right";
    }else if(name=="*" || name=="/"){
        this.precedence=5;
        
    }else if(name=="+" || name=="-"){
        this.precedence=1;
    }
    var op={
        "name":this.name,
        "type":this.type,
        "associativity":this.associativity,
        "precedence":this.precedence
    };
    return op;
}

Finally, I have the shunting algorithm, which, I thought to have followed the pseudocode here

function shunt(input){
    var operators=new Stack();
    var output=new Queue();
    
    for(var i in input){
        var token=input[i];
        console.log(token.name);
        if(token.type=="operator"){
//          console.log(token);
            while(!operators.empty() && operators.peek().type=="operator"){
                if((token.associativity=="left" && token.precedence==operators.peek()) || (token.precedence<operators.peek().precedence)){
                    output.enqueue(operators.pop().name);
                }
            }
            operators.push(token);
            
        }else if(token.type=="open"){
            console.log(token);
            operators.push(token);
        }else if(token.type=="close"){
            while (!operators.empty() && !operators.peek().type=="open") {
                output.enqueue(operators.pop().name);
            }
            operators.pop();
        }else{
            output.enqueue(token.name);
        }
        
    }
    while(!operators.empty()){
        output.enqueue(operators.pop().name);
    }
    output.stack.reverse();
    return output.stack;
}

When I tokenize and shunt something simple, like 1+1, it returns the expected 1 1 +. However, when I give it 1+1+1, it gets stuck in an infinite loop. It also has trouble recognizing close parentheses, and it will not remove all parenthesis tokens. For example, when I type in (1+1), it gives out ["1", "1", "("]. Could anyone point me to where the errors are in the algorithm, and give me some tips on how to solve it? I've looked over it several times, but I can't see where the error in handling parentheses is.

Thanks

Answer 1

You can break a string into Tokens easily as follows: If your code for generating Tokens is correct then skip to next code for conversion to postfix form using Shunting yard algorithm.

function Break(expression){  /*Expression is string like "2.22+3-5"*/
  var Tokens=[];
  //Start at the end of the string//
  var i=expression.length-1;
  var Operators=['+','-','*','/','^','(',')'];
  while(i>=0){
    if(Operators.indexOf(expression[i])!=-1 && expression[i]!='-'){
      Tokens.push(expression[i]);
      i-=1;
    }
    else if(expression[i]=='-'){
      if(i===0){
        Tokens.push('neg');
        i-=1;
      }
      else if(expression[i-1]!=')' && Operators.indexOf(expression[i-1])!=-1  ){
        Tokens.push('neg');
        i-=1;
      }
      else{
        Tokens.push('-');
        i-=1;
      }
    }
    else{
      var x=0,wt=0;
      while(i>=0 && Operators.indexOf(expression[i])==-1){
        if(expression[i]=='.'){
          x=x/Math.pow(10,wt);
          i-=1;
          wt=0;
        }
        else{
          x+=Math.floor(expression[i])*Math.pow(10,wt);
          wt+=1;
          i-=1;
        }
      }
      Tokens.push(x);
    }
  }
  return Tokens.reverse();
}

Once the string is converted into a list of Tokens returned by Break function, Shunting yard algorithm can be used for conversion to postfix form:

Following subroutine returns priorities of operator:

function Priority(x){
  switch(x){
    case 'neg': /*Highest priority of unary negation operator*/
      return 4;
    case '^':
      return 3;
    case '/':
      return 2;
    case '*':
      return 2;
    case '+':
      return 1;
    case '-':
      return 1;
    case '(':
      return 0;
  }
}

Finally we are ready for conversion to postfix:

function Postfix(Tokens){
  var Stack=[],List=[];
  var Operators=['^','/','*','+','-'];
  var i;
  for(i=0;i<Tokens.length;i++){
    if(Operators.indexOf(Tokens[i])!=-1){
      while(Stack.length!=-1 && Priority(Stack[Stack.length-1])>=Priority(Tokens[i]))
        List.push(Stack.pop());
      Stack.push(Tokens[i]);
    }
    else if(Tokens[i]=='(')
      Stack.push(Tokens[i]);
    else if(Tokens[i]==')'){
      while(Stack[Stack.length-1]!='(')
        List.push(Stack.pop());
      Stack.pop();
    }
    else
      List.push(Tokens[i]);
  }
  while(Stack.length!==0)
    List.push(Stack.pop());
  return List;
}

Now, say, if we want postfix form of "1+1+1" , we call Postfix(Break("1+1+1")). You can have a look at the running code at: http://jsbin.com/AbIleWu/1/edit?js,output

PS: You can add other unary operators like sin,cos,tan,log,ln etc. easily.