Jak zmodyfikować algorytm Shunting-Yard, aby akceptował jednoargumentowe operatory?

Question

Pracuję nad implementacją algorytmu Shunting-Yard w JavaScript dla klasy.

Oto moja praca do tej pory:

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

} 

To działa dobrze do tej pory. Jeśli daję:

((5 + 3) * 8)

Będzie Wydajność:

Infix: ((5 + 3) * 8)
Postfix (RPN): 5 3 + 8 *
Wynik: 64

jednak jestem zmaga się z realizacji jednoargumentowy operato rs tak mógłby zrobić coś takiego:

((-5 +3) * 8)

Co byłoby najlepszym sposobem wdrożenia operatorów jednoargumentowy (negacja, itp)? Czy ktoś ma również jakieś sugestie dotyczące obsługi liczb zmiennoprzecinkowych?

Ostatnią rzeczą, jeśli ktoś widzi mnie robi nic dziwnego w JavaScript daj mi znać. To jest mój pierwszy program JavaScript i nie jestem do tego jeszcze przyzwyczajony.

Answer 1

Moja sugestia jest taka. nie traktuj "-" jako operatora arytmetycznego. traktuj to jako operator "znaku". lub traktować go tak, jakby był częścią całego operandu (tj. jego znaku). mam na myśli to, że za każdym razem, gdy napotykasz "-", musisz pomnożyć operand po nim przez -1, a następnie przystąpić do odczytu następnego tokena. :) Mam nadzieję że to pomogło. tylko prosta myśl ...

Answer 2

Kiedy potrzebne do wspierania tego, zrobiłem to na etapie pośrednim. Zacząłem od wygenerowania listy wszystkich wyrażeń leksykalnych, a następnie wykorzystałem funkcje pomocnicze do wyodrębnienia operatorów i operandów, a funkcja "pobierz operand" po prostu zużyła dwa leksemy za każdym razem, gdy zobaczył jednoargumentowy operator.

To naprawdę pomaga, jeśli używasz innego znak oznaczający „jednoargumentowy minus”, choć.

Answer 3

Najłatwiej byłoby ustawić isNumber w dopasowaniu /-?[0-9]+(\.[0-9]+)?/, obsługując zarówno liczby zmiennoprzecinkowe, jak i liczby ujemne.

Jeśli naprawdę potrzebujesz do obsługi operatorów Jednoargumentowy (powiedzmy, jednoargumentowy negację wyrażenia w nawiasach), potem trzeba:

• Dodać do nich prawym asocjacyjne.
• Uczyń je wyższym priorytetem niż którykolwiek z operatorów infiksów.
• Stosować je oddzielnie EvaluateExpression (wykonać oddzielny PerformUnaryExpression funkcję, która potrzebuje tylko jednego argumentu).
• Rozróżnianie jednoargumentowego i binarnego minus w InfixToPostfix przez śledzenie pewnego rodzaju stanu. Zobacz, jak '-' zmieni się w '-u' w tym Python example.

Napisałem dokładniejsze wyjaśnienie obsługi unarnego minusa na another SO question.

Answer 4

W moim implementacji Javy Zrobiłem to w następnym sposób:

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

Answer 5

mogę rozwiązać ten problem poprzez modyfikację operatorów Jednoargumentowy („+” i „-”), aby odróżnić je od tych binarnych.

Na przykład nazwałem jednoargumentowy minus "m" i jednoargumentowy plus "+", co sprawia, że ​​są one prawostronne i mają pierwszeństwo równe operatorowi wykładniczemu ("^").

Aby wykryć, czy operator jest unarny, musiałem po prostu sprawdzić, czy token przed operatorem był operatorem lub nawiasem otwierającym.

To moja implementacja w 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); 
     } 

Tutaj operatorów jest stosem i Token jest iterator do ciągu wypowiedzi infix

(To właśnie operator część obsługi)