3

我在 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);
4

3 回答 3

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

现在您需要做的就是调用该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>

希望有帮助。

于 2014-08-15T06:12:21.373 回答
3

在我看来，这不是“Aadit M Shah”提到的在标记化过程中处理负数的正确方法

我建议在调车场算法中处理一元 + 或 - 。只需将一元 + 或 - 替换为不同的符号（在我的情况下为“p”或“m”）并在评估后缀符号（或 RPN）期间处理它们。

你可以在 GitHub 上找到我的 C# 实现

于 2016-01-04T15:05:32.793 回答
2

您的问题的解决方案可能是重写条目9-(3*(-6))以9-(3*(0-6))使-运算符二进制。只需将(-字符串中的每个替换为(0-.

于 2014-08-15T05:23:39.583 回答