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

Alright, so I don't know what's the problem with your code. It's not well formatted and it's too long. So I didn't read it. Nevertheless, here's how I would have written your program:

I'd split the program into a lexical analysis and a parsing phase. This makes your program more modular and easier to understand. I've already written a generic lexer and a shunting yard parser. So I'll use those to write the program.

First up, the lexical analyzer (I know that you didn't want to use regex and that you wrote your own expression parser, however this is the stuff regular expressions are good for, so):

const lexer = new Lexer();

lexer.addRule(/\s+/, () => {}); // skip whitespace

lexer.addRule(/[\+\-\*\/\(\)]/, lexeme => lexeme); // punctuators: + - * / ( )

lexer.addRule(/\-?(?:0|[1-9]\d*)(?:\.\d+)?/, lexeme => +lexeme); // numbers

Next we have the shunting yard parser:

const left1 = { associativity: "left", precedence: 1 };

const left2 = { associativity: "left", precedence: 2 };

const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });

Then we connect the lexer to the parser:

Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });

const step = value => ({ done: value === undefined, value });

const parse = input => {
    lexer.setInput(input);
    const next = () => step(lexer.lex());
    const tokens = Array.fromIterator({ next });
    return parser.parse(tokens);
};

Now all you need to do is call the parse function as follows:

const output = parse("9 - (5 * 2) + (7.66 / 3.21) * 3");

console.log(output); // [9, 5, 2, "*", "-", 7.66, 3.21, "/", 3, "*", "+"]

See the output for yourself.

const lexer = new Lexer();

lexer.addRule(/\s+/, () => {}); // skip whitespace

lexer.addRule(/[\+\-\*\/\(\)]/, lexeme => lexeme); // punctuators: + - * / ( )

lexer.addRule(/\-?(?:0|[1-9]\d*)(?:\.\d+)?/, lexeme => +lexeme); // numbers

const left1 = { associativity: "left", precedence: 1 };

const left2 = { associativity: "left", precedence: 2 };

const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });

Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });

const step = value => ({ done: value === undefined, value });

const parse = input => {
    lexer.setInput(input);
    const next = () => step(lexer.lex());
    const tokens = Array.fromIterator({ next });
    return parser.parse(tokens);
};

const output = parse("9 - (5 * 2) + (7.66 / 3.21) * 3");

console.log(output); // [9, 5, 2, "*", "-", 7.66, 3.21, "/", 3, "*", "+"]

<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>

It also correctly parses negative numbers:

const output = parse("9 - (3 * (-6))");

console.log(output); // [9, 3, -6, "*", "-"]

See the demo.

const lexer = new Lexer();

lexer.addRule(/\s+/, () => {}); // skip whitespace

lexer.addRule(/[\+\-\*\/\(\)]/, lexeme => lexeme); // punctuators: + - * / ( )

lexer.addRule(/\-?(?:0|[1-9]\d*)(?:\.\d+)?/, lexeme => +lexeme); // numbers

const left1 = { associativity: "left", precedence: 1 };

const left2 = { associativity: "left", precedence: 2 };

const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });

Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });

const step = value => ({ done: value === undefined, value });

const parse = input => {
    lexer.setInput(input);
    const next = () => step(lexer.lex());
    const tokens = Array.fromIterator({ next });
    return parser.parse(tokens);
};

const output = parse("9 - (3 * (-6))");

console.log(output); // [9, 3, -6, "*", "-"]

<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>

In addition it handles precedence and associativity rules to get rid of redundant parentheses:

const output = parse("9 - 3 * -6");

console.log(output); // [9, 3, -6, "*", "-"]

The demo.

const lexer = new Lexer();

lexer.addRule(/\s+/, () => {}); // skip whitespace

lexer.addRule(/[\+\-\*\/\(\)]/, lexeme => lexeme); // punctuators: + - * / ( )

lexer.addRule(/\-?(?:0|[1-9]\d*)(?:\.\d+)?/, lexeme => +lexeme); // numbers

const left1 = { associativity: "left", precedence: 1 };

const left2 = { associativity: "left", precedence: 2 };

const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });

Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });

const step = value => ({ done: value === undefined, value });

const parse = input => {
    lexer.setInput(input);
    const next = () => step(lexer.lex());
    const tokens = Array.fromIterator({ next });
    return parser.parse(tokens);
};

const output = parse("9 - 3 * -6");

console.log(output); // [9, 3, -6, "*", "-"]

<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>

Hope that helps.

Answer 2

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

Answer 3

A solution to your problem could be rewriting the entry 9-(3*(-6)) to 9-(3*(0-6)) to make the - operator binary. Just replace each (- in the string with (0-.