shunting yard algorithm(in Javascript),handling negative numbers

Question

I have written shunting yard algorithm in JS which works fine for almost all the scenarios, however if I have a negative number scenario then it fails, say for example if I give this expression 9-(3*(-6)) then it won't give a result...Any hint would be much appreciated ...I don't want to use regex. I have written my own expression parser instead.

my code:-

http://jsfiddle.net/min2bro/8ZvGh/20/

     // ========================== Converting string into Array of opeartors & operands including brackets also======
    // for example: if you enter the expression: 9-(5*2)+(7.66/3.21)*3 
    // this would return ['9','-','5','*','2','+','7.66','/','3.21','*','3']


    output = prompt("Enter the expression");


var result = [];
var str = "";
var temp = [];
var expression = [];



  for (i = 0; i < output.length; ++i)

  { 

      if(output[i] != "*" && output[i] != "+" && output[i] != "/" && output[i] != "-" )

       temp.push(output[i]);

      if(output[i] == "*" || output[i] == "+" || output[i] == "-" || output[i] == "/")

      { 
         for(var j = 0; j<= temp.length-1 ; j++ )
         {

             if (temp[j] == '(' || temp[j] == ')')
             { 
                 expression.push(temp[j])
             }
             else
             {
                 str += temp[j];
                 if (temp[j+1] == ")")
                 { expression.push(str);
                    str = "";
                 }
             }
         }

         var temp = [];  
         if (str!="")
         {
             expression.push(str);
         }
         expression.push(output[i]);

      }       

      str = "";

  } 

for(var n = 0 ; n<= temp.length-1 ; n++ )
{

                 if (temp[n] == '(' || temp[n] == ')')
             { 
                 expression.push(temp[n])
             }
             else
             {
                 str += temp[n];
                 if (temp[n+1] == ")")
                 { expression.push(str);
                    str = "";
                 }
             }


}
if (str!="")
         {
             expression.push(str);
         }











// ========================== Converting expression array into output array as defined in shunting algorithm
// for example: if you enter the expression: 9-(5*2)+(7.66/3.21)*3 
// this would return [9,5,2,*,-,7.66,3.21,/,3,*,+]
//==============================================================================

var output = [];   
var stack = [];
var precedence = {'+': 1,'-': 1,'*': 2,'/': 2,'(': 0};

for(var i = 0; i <= (expression.length-1) ; i++)
{
    if(!isNaN(expression[i]))
    {
      output.push((expression[i]));   
    }
    else if(expression[i] == "*" || expression[i] == "/" || expression[i] == "+" || expression[i] == "-" || expression[i] == "(" || expression[i] == ")")
    {
        if(stack == "" && expression[i] != ")")
       {
           stack.push(expression[i]);
       }
        else if(precedence[expression[i]] > precedence[stack[(stack.length -1)]])
       {
        stack.push(expression[i]);
       }
        else if((precedence[expression[i]] <= precedence[stack[stack.length -1]]))
        {   
            if(expression[i] == "(")
            {
                stack.push(expression[i]);
            }
            if(stack[stack.length-1]!="(")
            { 
            for(var k = (stack.length-1); k >= 0 ; k--)  
              { 
                  output.push(stack[k]);
                stack.pop(stack[k]);
              }
                stack.push(expression[i]);
            }
         }

if(expression[i] == ")")
{
    for(var j = (stack.length-1); j > 0 ; j--)
    {  
        if(stack[j]!="(")
          output.push(stack[j]);
          stack.pop(stack[j]);
    }

}
}

    //alert(stack)
    if(i == expression.length-1 && expression[i] != ")")
{
    //alert(stack);
    for(var j = (stack.length-1); j >= 0 ; j--)
    {  
        if(stack[j]!="(")
       output.push(stack[j]);
        stack.pop();
    }

}

}

    //alert(stack);
    for(var j = (stack.length-1); j >= 0 ; j--)
    {  
        if(stack[j]!="(")
       output.push(stack[j]);
    }




//============ Calculate the result===================

var result = [];

  for (i = 0; i < output.length; ++i)
  { 
    t = output[i];
      //alert(t);
    if (!isNaN(t))
      result.push(t);
    else if (t == "(" || result.length < 2)
      return false;
    else 
    {
       //alert(result);
      var rhs = result.pop();
       //alert(rhs);
      var lhs = result.pop();
      // alert(rhs);
      if (t == "+") result.push(parseFloat(lhs) + parseFloat(rhs));
      if (t == "-") result.push(parseFloat(lhs) - parseFloat(rhs));
      if (t == "*") result.push(parseFloat(lhs) * parseFloat(rhs));
      if (t == "/") result.push(parseFloat(lhs) / parseFloat(rhs));
    }
  }
alert(result);

Answer 1

In my opinion its not the right way to handle negative numbers during the tokenization process as mentionded by 'Aadit M Shah'

I would recomend to handle the unary + or - within the shunting-yard algorythm. Just replace the unary + or - with a different sign (in my case 'p' or 'm') and handle them during the evaluation of the postfix notation (or RPN).

You can find my C# implementation here on GitHub