Как я могу изменить алгоритм Shunting-Yard Algorithm, чтобы он принимал унарные операторы?
Я работал над внедрением алгоритма 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
Однако я борюсь с реализацией унарных операторов, поэтому я мог бы сделать что-то вроде:
(( -5 +3) * 8)
Каким будет лучший способ реализовать унарные операторы (отрицание и т.д.)? Кроме того, есть ли у кого-нибудь предложения по обработке чисел с плавающей запятой?
Последнее, если кто-нибудь увидит, что я делаю что-нибудь странное в JavaScript, дайте мне знать. Это моя первая программа для JavaScript, и я еще не привык к ней.
Ответы
Ответ 1
Проще всего было бы сделать isNumber
match /-?[0-9]+(\.[0-9]+)?/
, обрабатывая как плавающие точки, так и отрицательные числа.
Если вам действительно нужно обрабатывать унарные операторы (например, унарное отрицание выражений в скобках), вы должны:
- Сделайте их право-ассоциативными.
- Сделайте их более приоритетными, чем любой из инфиксных операторов.
- Обработайте их отдельно в
EvaluateExpression
(создайте отдельную функцию PerformUnaryExpression
, которая принимает только один операнд).
- Различать унарный и двоичный минус в
InfixToPostfix
, отслеживая какое-то состояние. Посмотрите, как '-'
превращается в '-u'
в этом примере Python.
Я написал более подробное объяснение обработки унарного минуса на другом вопросе SO.
Ответ 2
Мое предложение - это. не обрабатывайте "-" как арифметический оператор. рассматривать его как оператора "знака". или рассматривать его так, как если бы он был частью всего операнда (т.е. его знака). я имею в виду, что каждый раз, когда вы сталкиваетесь с "-", вам просто нужно умножить операнд после него на -1, затем перейдите к следующему токену.:) Надеюсь, это поможет. просто простая мысль...
Ответ 3
Когда мне нужно было поддержать это, я сделал это на промежуточной стадии. Я начал с создания списка всех выражений lexemes, затем использовал вспомогательные функции для извлечения операторов и операндов, а функция "получить операнд" просто потребляла два лексема всякий раз, когда он видел унарный оператор.
Это действительно помогает, если вы используете другого персонажа, чтобы обозначить "унарный минус".
Ответ 4
В моей реализации Java я сделал это следующим образом:
expression = expression.replace(" ", "").replace("(-", "(0-")
.replace(",-", ",0-");
if (expression.charAt(0) == '-') {
expression = "0" + expression;
}
Ответ 5
Я мог бы решить эту проблему, изменив унарные операторы ('+' и '-'), чтобы отличить их от двоичных.
Например, я назвал унарный минус "m" и унарный плюс "+", делая их право-ассоциативными, а их приоритет равен показателю экспоненты ('^').
Чтобы определить, является ли оператор унарным, я просто должен был проверить, был ли токен перед оператором оператором или открывающей скобкой.
Это моя реализация в С++:
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);
}
Здесь операторы - это стек, а токен - это итератор строки строки infix
(Это только часть обработки оператора)