Как я могу изменить алгоритм 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 RS, так что я мог бы сделать что-то вроде:

((-5 +3) * 8)

Что бы быть лучшим способом реализовать унарные операторы (отрицание, и т.д.)? Кроме того, есть ли у кого-нибудь предложения по обработке чисел с плавающей запятой?

Последнее, если кто-нибудь увидит, что я делаю что-нибудь странное в JavaScript, дайте мне знать. Это моя первая программа для JavaScript, и я пока не привык к ней.

Answer 1

мое предложение. не обрабатывайте «-» как арифметический оператор. рассматривать его как оператора «знака». или рассматривать его так, как будто он является частью всего операнда (т. е. его знака). я имею в виду, что каждый раз, когда вы сталкиваетесь с «-», вам просто нужно умножить операнд после него на -1, затем перейдите к следующему токену. :) Надеюсь, это поможет. просто простая мысль ...

Answer 2

Когда мне нужно было поддержать это, я сделал это на промежуточной стадии. Я начал с создания списка всех выражений lexemes, затем использовал вспомогательные функции для извлечения операторов и операндов, а функция «получить операнд» просто потребляла два лексема всякий раз, когда он видел унарный оператор.

Это действительно помогает, если вы используете другого персонажа, чтобы обозначить «унарный минус».

Answer 3

Проще всего было бы сделать isNumber совпадение /-?[0-9]+(\.[0-9]+)?/, обрабатывая как плавающие точки, так и отрицательные числа.

Если вам действительно нужно обрабатывать унарные операторы (например, унарное отрицание выражения в скобках), то вы должны:

• Сделать их правоассоциативными.
• Сделать их более высокоприоритетными, чем любые операторы infix.
• Обращайтесь с ними отдельно в EvaluateExpression (сделайте отдельную функцию PerformUnaryExpression, которая принимает только один операнд).
• Различают унарный и двоичный минус в InfixToPostfix, отслеживая состояние какого-либо состояния. Посмотрите, как '-' превращается в '-u' в этом Python example.

Я написал более подробное объяснение обработки унарного минуса на another SO question.

Answer 4

В моей реализации Java я сделал это следующим способом:

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

Здесь операторы является стек и маркер итератор к выражению инфикс строки

(Это только оператор обработки часть)