Шунтирование Yard Алгоритм ненужными скобки

Question

ввода (в JavaScript) является "3-2 + (8-3)"

Я хочу, чтобы перевести это выражение Reverse Polish Notation. Однако, согласно алгоритму, я могу получить «3 2 8 3 - + -», который не оценивает результат 12 ..... Любая работа вокруг метода для этого? Я знаю, что круглые скобки не нужны здесь, но, да ладно ... У меня есть функция ниже:

function ShuntingYard(str){ 
    str=str.replace(/\)\(/g, ")*("); 
    var arr=str.split(""); 
    var sYqueue=[]; 
    var sYstack=[]; 
    while (arr.length>0){ 
     var token=arr.shift(); 
     if (/\d+/.test(token)){ 
      // if it's a number, push to the queue 
      sYqueue.push(token); 
     } // end if 
     else if (/[+]|[-]|[*]|[\/]/.test(token)){ 
      // if it's an operator 
      if (sYstack.length==0){ 
       // if an empty operator stack 
       sYstack.push(token); 

      } 
      else{ 
       while ((/[*]|[\/]/.test(sYstack[sYstack.length-1])) && 
        (/[+]|[-]/.test(token))){ 
         // if the TOS has operator with higher precedence 
         // then need to pop off the stack 
         // and add to queue 
         console.log(sYstack); 
         sYqueue.push(sYstack.pop()); 
        } 
        sYstack.push(token); 

      } 
     } 
     else if (/[(]/.test(token)){ 
      // if it's left parenthesis 
      sYstack.push(token); 
     } 

     else if (/[)]/.test(token)){ 
      // if it's right parenthesis 
      while (!(/[(]/.test(sYstack[sYstack.length-1]))){ 
       // while there's no left parenthesis on top of the stack 
       // then need to pop the operators onto the queue 
       sYqueue.push(sYstack.pop()); 
      } // end while 
      if (sYstack.length==0) 
      { // unbalanced parenthesis!! 
       console.log("error, unbalanced parenthesis"); 
      } 
      else 
      { 
       sYstack.pop(); // pop off the left parenthesis 
      } 

     } 
     else{ 
      // other cases 
     } 

    } // end while 


    // now while the stack is not empty, pop every operators to queue 
    while (sYstack.length>0){ 
     sYqueue.push(sYstack.pop()); 
    } 
    return sYqueue; 

} // end function ShuntingYard 

Answer 1

Уже давно в gist далеко далеко я написал реализацию маневровой алгоритма двор Дейкстры в JavaScript:

function Parser(table) { 
    this.table = table; 
} 

Parser.prototype.parse = function (input) { 
    var length = input.length, 
     table = this.table, 
     output = [], 
     stack = [], 
     index = 0; 

    while (index < length) { 
     var token = input[index++]; 

     switch (token) { 
     case "(": 
     stack.unshift(token); 
      break; 
     case ")": 
      while (stack.length) { 
       var token = stack.shift(); 
       if (token === "(") break; 
       else output.push(token); 
      } 

      if (token !== "(") 
       throw new Error("Mismatched parentheses."); 
      break; 
     default: 
      if (table.hasOwnProperty(token)) { 
       while (stack.length) { 
        var punctuator = stack[0]; 

        if (punctuator === "(") break; 

        var operator = table[token], 
         precedence = operator.precedence, 
         antecedence = table[punctuator].precedence; 

        if (precedence > antecedence || 
         precedence === antecedence && 
         operator.associativity === "right") break; 
        else output.push(stack.shift()); 
       } 

       stack.unshift(token); 
      } else output.push(token); 
     } 
    } 

    while (stack.length) { 
     var token = stack.shift(); 
     if (token !== "(") output.push(token); 
     else throw new Error("Mismatched parentheses."); 
    } 

    return output; 
}; 

Вот как вы бы использовать:

var parser = new Parser({ 
 
    "*": { precedence: 2, associativity: "left" }, 
 
    "/": { precedence: 2, associativity: "left" }, 
 
    "+": { precedence: 1, associativity: "left" }, 
 
    "-": { precedence: 1, associativity: "left" } 
 
}); 
 

 
var output = parser.parse("3 - 2 + (8 - 3)".split(" ")).join(" "); 
 

 
alert(JSON.stringify(output)); // "3 2 - 8 3 - +"

<script>function Parser(a){this.table=a}Parser.prototype.parse=function(a){var b=a.length,table=this.table,output=[],stack=[],index=0;while(index<b){var c=a[index++];switch(c){case"(":stack.unshift(c);break;case")":while(stack.length){var c=stack.shift();if(c==="(")break;else output.push(c)}if(c!=="(")throw new Error("Mismatched parentheses.");break;default:if(table.hasOwnProperty(c)){while(stack.length){var d=stack[0];if(d==="(")break;var e=table[c],precedence=e.precedence,antecedence=table[d].precedence;if(precedence>antecedence||precedence===antecedence&&e.associativity==="right")break;else output.push(stack.shift())}stack.unshift(c)}else output.push(c)}}while(stack.length){var c=stack.shift();if(c!=="(")output.push(c);else throw new Error("Mismatched parentheses.");}return output};</script>

Это, кстати, не (и никогда не будет) оцениваться до 12, но это d OES:

var parser = new Parser({ 
 
    "*": { precedence: 2, associativity: "left" }, 
 
    "/": { precedence: 2, associativity: "left" }, 
 
    "+": { precedence: 1, associativity: "left" }, 
 
    "-": { precedence: 1, associativity: "left" } 
 
}); 
 

 
var output = parser.parse("3 * 3 - 2 + 8 - 3".split(" ")).join(" "); 
 

 
alert(JSON.stringify(output)); // "3 3 * 2 - 8 + 3 -"

<script>function Parser(a){this.table=a}Parser.prototype.parse=function(a){var b=a.length,table=this.table,output=[],stack=[],index=0;while(index<b){var c=a[index++];switch(c){case"(":stack.unshift(c);break;case")":while(stack.length){var c=stack.shift();if(c==="(")break;else output.push(c)}if(c!=="(")throw new Error("Mismatched parentheses.");break;default:if(table.hasOwnProperty(c)){while(stack.length){var d=stack[0];if(d==="(")break;var e=table[c],precedence=e.precedence,antecedence=table[d].precedence;if(precedence>antecedence||precedence===antecedence&&e.associativity==="right")break;else output.push(stack.shift())}stack.unshift(c)}else output.push(c)}}while(stack.length){var c=stack.shift();if(c!=="(")output.push(c);else throw new Error("Mismatched parentheses.");}return output};</script>

Там у вас есть: обобщенная реализация алгоритма маневрового ярда Дейкстров в JavaScript.

Answer 2

Существует ошибка в вашей функции логики: предыдущий оператор должен быть из стека в выходную очередь в 2 случаях:
1. Это приоритет выше (ваш код обрабатывает этот случай).
2. Он имеет тот же приоритет, и новый оператор лево-ассоциативный (что имеет место для плюса и минуса).
Второй код не распространяется на ваш код, поэтому он не работает должным образом.

Answer 3

Существует синтаксический анализатор двигатель выражения (реализации JavaScript/PHP/Python и ActionScript), на github Xpresion (пс. Я являюсь автор)

Двигатель достаточно гибкий и настраиваемый, можно создать парсер, что разобрать любое выражение, которое также включает в себя полиморфные операторы и общие п-арной операторов (например. тройная, если-то-иначе)

алгоритм имеет весьма общий характер (можно сказать, обобщенный вариант Shunting Yard algorithm)