単項演算子を受け入れるようにShunting-Yardアルゴリズムを変更するにはどうすればよいですか？

Question

私はShunting-YardアルゴリズムをJavaScript用に実装しています。ここで

は私の仕事は、これまでのところです：

var userInput = prompt("Enter in a mathematical expression:"); 
var postFix = InfixToPostfix(userInput); 
var result = EvaluateExpression(postFix); 

document.write("Infix: " + userInput + "<br/>"); 
document.write("Postfix (RPN): " + postFix + "<br/>"); 
document.write("Result: " + result + "<br/>"); 


function EvaluateExpression(expression) 
{ 
    var tokens = expression.split(/([0-9]+|[*+-\/()])/); 
    var evalStack = []; 

    while (tokens.length != 0) 
    { 
     var currentToken = tokens.shift(); 

     if (isNumber(currentToken)) 
     { 
      evalStack.push(currentToken); 
     } 
     else if (isOperator(currentToken)) 
     { 
      var operand1 = evalStack.pop(); 
      var operand2 = evalStack.pop(); 

      var result = PerformOperation(parseInt(operand1), parseInt(operand2), currentToken); 
      evalStack.push(result); 
     } 
    } 
    return evalStack.pop(); 
} 

function PerformOperation(operand1, operand2, operator) 
{ 
    switch(operator) 
    { 
     case '+': 
      return operand1 + operand2; 
     case '-': 
      return operand1 - operand2; 
     case '*': 
      return operand1 * operand2; 
     case '/': 
      return operand1/operand2; 
     default: 
      return; 
    } 

} 

function InfixToPostfix(expression) 
{ 
    var tokens = expression.split(/([0-9]+|[*+-\/()])/); 
    var outputQueue = []; 
    var operatorStack = []; 

    while (tokens.length != 0) 
    { 
     var currentToken = tokens.shift(); 

     if (isNumber(currentToken)) 
     { 
      outputQueue.push(currentToken); 
     } 
     else if (isOperator(currentToken)) 
     { 
      while ((getAssociativity(currentToken) == 'left' && 
        getPrecedence(currentToken) <= getPrecedence(operatorStack[operatorStack.length-1])) || 
        (getAssociativity(currentToken) == 'right' && 
        getPrecedence(currentToken) < getPrecedence(operatorStack[operatorStack.length-1]))) 
      { 
       outputQueue.push(operatorStack.pop()) 
      } 

      operatorStack.push(currentToken); 

     } 
     else if (currentToken == '(') 
     { 
       operatorStack.push(currentToken); 
     } 
     else if (currentToken == ')') 
     { 
      while (operatorStack[operatorStack.length-1] != '(') 
      { 
       if (operatorStack.length == 0) 
        throw("Parenthesis balancing error! Shame on you!"); 

       outputQueue.push(operatorStack.pop()); 
      } 
      operatorStack.pop();   
     } 
    } 

    while (operatorStack.length != 0) 
    { 
     if (!operatorStack[operatorStack.length-1].match(/([()])/)) 
      outputQueue.push(operatorStack.pop()); 
     else 
      throw("Parenthesis balancing error! Shame on you!");   
    } 

    return outputQueue.join(" "); 
}  


function isOperator(token) 
{ 
    if (!token.match(/([*+-\/])/)) 
     return false; 
    else 
     return true; 
} 


function isNumber(token) 
{ 
    if (!token.match(/([0-9]+)/)) 
     return false; 
    else 
     return true; 
} 


function getPrecedence(token) 
{ 
    switch (token) 
    { 
     case '^': 
      return 9; 
     case '*':   
     case '/': 
     case '%': 
      return 8; 
     case '+': 
     case '-': 
      return 6; 
     default: 
      return -1; 
    } 
} 

function getAssociativity(token) 
{ 
    switch(token) 
    { 
     case '+': 
     case '-': 
     case '*': 
     case '/': 
      return 'left'; 
     case '^': 
      return 'right'; 
    } 

} 

それは、これまで正常に動作します。

（（5 + 3）* 8）

それの出力は以下となります：

中置：（（5 + 3）* 8）
Postfixの私はそれを与える場合（RPN）：5 3 + 8 *
結果：64

は、しかし、私は単項operatoを実装することに苦労しています単項演算子（否定、など）を実装するための最良の方法だろう何

（（-5 3）* 8）

：ので、私は次のようにRSができますか？また、誰も浮動小数点数を処理するための任意の提案を持っていますか？

誰かが私にJavaScriptで奇妙なことをしているのを見たら、私に知らせてください。これは私の最初のJavaScriptプログラムであり、まだ慣れていません。

Answer 1

私の提案はこれです。算術演算子として ' - 'を扱わないでください。それを '記号'演算子として扱う。それをオペランド全体の一部（あたかもその符号）のように扱います。つまり、 ' - 'が出現するたびにオペランドに-1を掛けてから、次のトークンを読みとるだけです。 :)私はそれが助けて欲しい。ちょっと考えました...

Answer 2

これをサポートする必要があるとき、私は中間段階でこれを行いました。私はすべての式のレクメムのリストを生成し、次に演算子とオペランドを抽出するためにヘルパー関数を使い始めました。そして、 "オペランドを得る"関数は単項演算子を見たときにただ2つのレクメムを消費しました。

「単項マイナス」を意味する別の文字を使用すると、本当に役に立ちます。

Answer 3

最も簡単なことは、isNumberが/-?[0-9]+(\.[0-9]+)?/に一致し、浮動小数点数と負数の両方を処理することです。

あなたが本当に単項演算子（たとえば、括弧で囲まれた式の単項否定）を処理する必要がある場合は、あなたが持っている：

• はそれら右結合してください。
• 中置演算子のいずれよりも優先順位を高くします。
• EvaluateExpressionで別々に処理してください（1つのオペランドしか持たない別のPerformUnaryExpression関数を作成してください）。
• 何らかの状態を把握して、InfixToPostfixの単項マイナスと二進マイナスを区別します。このPython exampleの'-'が'-u'に変わった方法をご覧ください。

私は、another SO questionに単項マイナスを扱うことのより完全な説明を書いています。私のJava実装で

Answer 4

私は次の方法でそれをやった：

expression = expression.replace(" ", "").replace("(-", "(0-") 
       .replace(",-", ",0-"); 
     if (expression.charAt(0) == '-') { 
      expression = "0" + expression; 
     } 

Answer 5

私は（「+」と「 - 」）単項演算子を変更することによってこの問題を解決することができ、バイナリのものと区別するために。

たとえば、単項マイナス 'm'と単項プラス '+'を使用して、それらを右結合し、それらの優先順位を指数演算子（ '^'）に等しくします。

オペレータが単項式かどうかを検出するには、オペレータの前にトークンがオペレータかオープニングブラケットかどうかを確認するだけでした。

これはC++での私の実装である：ここでは

 if (isOperator(*token)) 
     { 
      if (!isdigit(*(token - 1)) && *(token - 1) != ')') // Unary check 
      { 
       if (*token == '+') 
        *token = 'p';  // To distinguish from the binary ones 
       else if (*token == '-') 
        *token = 'm'; 
       else 
        throw; 
      } 

      short prec = precedence(*token); 
      bool rightAssociative = (*token == '^' || *token == 'm' || *token == 'p'); 

      if (!operators.empty()) 
      { 
       while (prec < precedence(operators.top()) || (prec == precedence(operators.top()) && !rightAssociative)) 
       { 
        rpn += operators.top(); 
        operators.pop(); 

        if (operators.empty()) 
         break; 
       } 
      } 
      operators.push(*token); 
     } 

事業者は、スタックされ、トークンは中置式文字列

（この部分を扱うだけのオペレータ）