javascript - polaca - polish calculator

¿Cómo puedo modificar mi algoritmo Shunting-Yard para que acepte operadores unarios?

Question

He estado trabajando en la implementación del algoritmo Shunting-Yard en JavaScript para la clase.

Aquí está mi trabajo hasta ahora:

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

Funciona bien hasta ahora. Si lo doy:

((5 + 3) * 8)

Saldrá:

Infijo: ((5 + 3) * 8)
Postfix (RPN): 5 3 + 8 *
Resultado: 64

Sin embargo, estoy luchando con la implementación de los operadores unarios para poder hacer algo como:

(( -5 +3) * 8)

¿Cuál sería la mejor manera de implementar operadores unarios (negación, etc.)? Además, ¿alguien tiene alguna sugerencia para manejar números de punto flotante también?

Una última cosa, si alguien me ve haciendo algo raro en JavaScript, hágamelo saber. Este es mi primer programa de JavaScript y todavía no estoy acostumbrado.

Answer 1

Cuando tuve que apoyar esto, lo hice en una etapa intermedia. Comencé generando una lista de todos los lexemas de expresión, luego usé funciones de ayuda para extraer operadores y operandos y la función "obtener operando" simplemente consumía dos lexemas cada vez que veía un operador único.

Sin embargo, realmente ayuda si usas otro personaje para significar "menos unario".

Answer 2

En mi implementación de Java lo hice de la siguiente manera:

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

Answer 3

Lo más fácil sería hacer que el isNumber sea ​​/-?[ isNumber /-?[0-9]+(/.[0-9]+)?/ isNumber /-?[0-9]+(/.[0-9]+)?/ , /-?[0-9]+(/.[0-9]+)?/ , manejando tanto los puntos flotantes como los números negativos.

Si realmente necesita manejar operadores unarios (por ejemplo, negación unaria de expresiones entre paréntesis), entonces tiene que:

• Hazlos asociativos por derecho.
• Haz que tengan mayor prioridad que cualquiera de los operadores de infijo.
• Manéjelos por separado en EvaluateExpression (haga una función separada PerformUnaryExpression que solo tome un operando).
• Distinguir entre unario y un binario menos en InfixToPostfix mediante el seguimiento de algún tipo de estado. Vea cómo ''-'' se convierte en ''-u'' en este ejemplo de Python .

Escribí una explicación más detallada del manejo de unario menos en otra pregunta de SO .

Answer 4

Mi sugerencia es esta. no maneje el ''-'' como un operador aritmético. Trátela como un operador de "signo". o trátela como si fuera parte de todo el operando (es decir, su signo). lo que quiero decir es que cada vez que se encuentre con ''-'', solo tiene que multiplicar el operando por -1 y luego proceder a leer el siguiente token. :) Espero que eso ayude. sólo un pensamiento simple ...

Answer 5

Podría resolver este problema modificando los operadores unarios (''+'' y ''-'') para distinguirlos de los binarios.

Por ejemplo, llamé al unary menos ''m'' y unary más ''+'', haciendo que sean correctos y su precedencia sea igual al operador exponente (''^'').

Para detectar si el operador es único, simplemente tuve que comprobar si el token antes del operador era un operador o un soporte de apertura.

Esta es mi implementación en 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);
}

Aquí los operadores son una pila y el token es un iterador para la cadena de expresión infija

(Esto es solo la parte de manejo del operador)