javascript - 调车场算法(Javascript)，处理负数

Question

我在 JS 中编写了调车场算法，它适用于几乎所有场景，但是如果我有一个负数场景，那么它就会失败，例如，如果我给出这个表达式 9-(3*(-6))那么它不会给出结果...任何提示将不胜感激...我不想使用正则表达式。我已经编写了自己的表达式解析器。

我的代码:-

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

好的，所以我不知道您的代码有什么问题。它的格式不好，而且太长了。所以我没有读它。不过，这就是我编写您的程序的方式:

我将程序分为词法分析和语法分析阶段。这使您的程序更加模块化并且更易于理解。我已经写了一个通用的 lexer和一个 shunting yard parser .所以我将使用这些来编写程序。

首先是词法分析器(我知道您不想使用正则表达式并且您编写了自己的表达式解析器，但这是正则表达式的用武之地，所以):

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

现在您需要做的就是调用 parse 函数，如下所示:

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

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

自己查看输出。

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>

它也能正确解析负数:

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

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

查看演示。

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>

此外，它还处理优先级和关联性规则以摆脱多余的括号:

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

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

演示。

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>

希望对您有所帮助。