Come posso modificare il mio Algoritmo dello Shunting-Yard in modo che accetti operatori unari?

Question

Ho lavorato sull'implementazione dell'algoritmo Shunting-Yard in JavaScript per la lezione.

Ecco il mio lavoro finora:

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

} 

Funziona bene finora. Se mi danno:

((5 + 3) * 8)

Sarà uscita:

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

Tuttavia, sono alle prese con l'attuazione della operato unario rs così ho potuto fare qualcosa di simile:

((-5 +3) * 8)

Quale sarebbe il modo migliore per attuare operatori unari (negazione, ecc)? Inoltre, qualcuno ha qualche suggerimento per gestire anche i numeri in virgola mobile?

Un'ultima cosa, se qualcuno mi vede fare qualcosa di strano in JavaScript fammelo sapere. Questo è il mio primo programma JavaScript e non sono ancora abituato.

Answer 1

il mio suggerimento è questo. non gestire il '-' come operatore aritmetico. trattalo come un operatore di 'segno'. o trattalo come se fosse una parte dell'intero operando (cioè il suo segno). quello che voglio dire è che ogni volta che incontri '-', devi solo moltiplicare l'operando dopo di esso per -1, quindi procedi a leggere il prossimo token. :) Spero che aiuti. solo un semplice pensiero ...

Answer 2

Quando ho avuto bisogno di sostenere questo, l'ho fatto in una fase intermedia. Ho iniziato generando un elenco di tutti i lessemi di espressioni, poi ho usato le funzioni di supporto per estrarre operatori e operandi e la funzione "get operando" ha semplicemente consumato due lessemi ogni volta che vedeva un operatore unario.

È molto utile se si utilizza un altro carattere per indicare "meno unario", tuttavia.

Answer 3

La cosa più semplice sarebbe fare corrispondere isNumber , gestendo sia i punti mobili che i numeri negativi.

Se si ha realmente bisogno per gestire operatori unari (diciamo, la negazione unaria di espressioni tra parentesi), poi si deve:

• Renderli destra-associativo.
• Renderli più precisi rispetto a qualsiasi degli operatori di infisso.
• Gestirli separatamente in EvaluateExpression (creare una funzione separata PerformUnaryExpression che richiede solo un operando).
• Distinguere tra unario e binario negativo in InfixToPostfix tenendo traccia di un tipo di stato. Guarda come '-' viene convertito in '-u' in questo Python example.

Ho scritto una spiegazione più approfondita della gestione di unario meno su another SO question.

Answer 4

Nella mia implementazione Java ho fatto in modo successivo:

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

Answer 5

ho potuto risolvere il problema modificando operatori unari ('+' e '-') per distinguerli da quelli binari.

Ad esempio, ho chiamato unario meno 'm' e unario più '+', rendendoli giusti-associativi e la loro precedenza uguale all'operatore esponente ('^').

Per rilevare se l'operatore è unario, ho semplicemente dovuto verificare se il token prima che l'operatore fosse un operatore o una staffa di apertura.

Questa è la mia implementazione in 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); 
     } 

Qui gli operatori è uno stack e token è un iteratore alla stringa di espressione infissa

(questo solo la parte di movimentazione dell'operatore)