입환 마당 알고리즘 불필요한 괄호

Question

입력 (자바 스크립트) "3-2 + (8-3)"입니다

내가 역 폴란드 표기법이 표현을 번역 할. 그러나 알고리즘에 따르면 "결과를 평가하지 않는"3 2 8 3 - + - "을 얻을 수 있습니다. 나는 오, 음 ... 내가 아래에있는 내 기능을 가지고, 괄호 여기 불필요 알고 있지만 :

함수의 논리에 오류가

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에서 오래 전은 멀리 멀리 나는 자바 스크립트 익스트라의 전철 야드 알고리즘의 구현을 썼다 :

여기

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>

가 당신이 그것을 가지고 : 자바 스크립트에서 다 익스트라의 전철 야드 알고리즘의 일반화 된 구현을. 표현 파서 엔진이 있습니다

Answer 2

: 이전 연산자는 출력 큐에 스택에서 팝해야 2 케이스의 경우 :
1. 우선 순위가 높습니다 (코드가이 경우를 처리 함).
2. 우선 순위가 같고 새 연산자가 왼쪽 연관입니다 (더하기 및 빼기의 경우).
두 번째 사례는 코드에서 다루지 않으므로 제대로 작동하지 않습니다.

Answer 3

엔진은 매우 유연하고 구성 할 수 있습니다, github Xpresion에 (PS. 내가 해요 저자) (자바 스크립트/PHP/Python과 ActionScript에 구현), 하나 파서를 만들 수 있습니다 또한 다형 연산자 일반 n 차 연산자를 포함하는 표현식을 파싱 (예. 삼원 IF-그때 다른)

알고리즘은 (하나, Shunting Yard algorithm의 일반화 변화를 말할 수있다)