Wie kann ich ändern, meine Rangier-Yard-Algorithmus, so dass es akzeptiert unären Operatoren?
Ich arbeite schon an der Umsetzung der Rangier-Yard-Algorithmus in JavaScript für die Klasse.
Hier ist meine Arbeit so weit:
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';
}
}
Es funktioniert gut so weit. Wenn ich es geben:
((5+3) * 8)
Wird es ausgegeben wird:
Infix: ((5+3) * 8)
Postfix (RPN): 5 3 + 8 *
Ergebnis: 64
Jedoch bin ich zu kämpfen mit der Umsetzung der unäre Operatoren, so dass ich tun könnte etwas wie:
((-5+3) * 8)
Was wäre die beste Art der Umsetzung unäre Operatoren (negation, etc)? Auch, hat jemand irgendwelche Vorschläge für die Handhabung von floating-point-zahlen als gut?
Eine Letzte Sache, wenn jemand sieht mich dabei etwas komisch in JavaScript lassen Sie es mich wissen. Dies ist mein erstes JavaScript-Programm, und ich bin nicht daran gewöhnt noch.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist die einfachste Sache wäre zu machen
isNumber
match/-?[0-9]+(\.[0-9]+)?/
-, handling-sowohl schwimmend als auch Punkte und negative zahlen.Wenn Sie wirklich brauchen, um zu behandeln unäre Operatoren (z.B. unäre negation des eingeklammerten Ausdrücke), dann müssen Sie zu:
EvaluateExpression
(eine separatePerformUnaryExpression
Funktion, die mit nur einem Operanden).InfixToPostfix
durch verfolgen der irgendeine Art von Zustand. Sehen Sie, wie'-'
sich in'-u'
in diesem Python-Beispiel.Schrieb ich eine ausführliche Erklärung der Handhabung unäre minus auf eine andere Frage.
mein Vorschlag ist dieser. don ' T behandeln Sie das '-' als ein arithmetischer operator. behandeln Sie es als ein 'Zeichen' - operator. oder es behandeln, als wenn es ein Teil des ganzen operand (d.h. das Vorzeichen). was ich meine ist, dass jedes mal, wenn Sie Begegnung '-', man muss Sie nur multiplizieren Sie den Operanden, nachdem er durch -1, dann gehen Sie mit dem Lesen des nächsten Tokens. 🙂 ich hoffe, das hilft. nur ein einfacher Gedanke...
sin(3 + 4)
geht3 4 + sin
,7 sin
, und dann auch immer die Hölle, Sünde(7) ist. Nicht schwierig, wenn Sie Folgen, Rangierbahnhof-Algorithmus.Konnte ich lösen dieses problem, indem Sie unäre Operatoren('+' und '-') zur Unterscheidung von den binären Einsen.
Zum Beispiel, ich rief die unären minus 'm' und unären plus '+', so dass Sie rechts-assocative und deren Rang gleich dem Exponenten-operator('^').
Zu erkennen, ob der operator unär ich musste einfach überprüfen, ob das token vor dem operator ein operator oder eine öffnende Klammer.
Dies ist meine Implementierung in C++:
Hier Betreiber ist ein Stapel-und token ist ein iterator, um die infix-Ausdruck string
(Diese nur die Handhabung durch den Bediener Teil)
Wenn ich brauchte, um dies zu unterstützen, habe ich diese in einem Zwischenstadium. Ich begann durch die Erstellung einer Liste aller Ausdruck Lexeme, dann verwendet helper-Funktionen zum extrahieren von Operatoren und Operanden und der "get operand" - Funktion einfach verbraucht zwei Lexeme, Wann immer es sah ein unärer operator.
Hilft es wirklich, wenn Sie verwenden ein anderes Zeichen, um zu signalisieren "unäre minus", obwohl.
In meiner Java-Implementierung habe ich es in der folgenden Weise:
2*-2
?