Hinzufügen von Bedingungen und Funktionen zu einem mathematischen Parser
https://stackoverflow.com/questions/3262889
-
16-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen Binärbaum-basierten Parser für mathematische Ausdrücke erstellt, der sich hervorragend für „normale“ Mathematik eignet, wie zum Beispiel: (3.5 * 2) ^ 1 / (1 << 6).Ich möchte es jedoch ein wenig erweitern, um einen ternären Auswahloperator hinzuzufügen, der den von C widerspiegelt: {expr} ? {true-expr} : {false-expr}.Ich würde auch gerne Funktionen hinzufügen, z sin(x) oder ave(...).
Ich habe jedoch keine Ahnung, wie ich damit umgehen soll (aufgrund der Art und Weise, wie die Auswertung funktioniert), und ich kann auch nichts im Internet finden, das dies abdeckt, zumindest nicht auf einer nicht auf Grammatik basierenden Weise (ich möchte Grammatik-Parser-Generatoren vermeiden). (falls möglich).
Mein aktueller Parser wertet einen Infix-Ausdruck aus und konvertiert ihn sofort in einen Baum. Von dort aus kann der Baum dann ausgewertet werden, d. h.:Es ist Ihr langweiliger Standardausdrucksbaum.
Aktuell sieht mein Bewerter so aus:
struct Node
{
int nType;
union
{
unsigned long dwOperator;
BOOL bValue;
int nValue; //for indices, args & functions
number_t fValue;
char* szValue; //for string literals to pass to functions
};
Node* pLeft;
Node* pRight;
};
number_t EvaluateTree(Node* pNode)
{
if(pNode == NULL)
return 0.0f;
int nType = pNode->nType;
if(nType == TOKEN_OPERATOR)
{
number_t fLeft = EvaluateTree(pNode->pLeft);
number_t fRight = EvaluateTree(pNode->pRight);
switch(pNode->dwOperator)
{
case '+': return fLeft + fRight;
case '-': return fLeft - fRight;
case '*': return fLeft * fRight;
case '/': return fLeft / fRight;
case '^': return pow(fLeft,fRight);
case '_': return pow(fLeft,1.0f/fRight);
case '%': return fmod(fLeft,fRight);
//case '?': return bSelect = ?;
//case ':': return (bSelect) ? fLeft : fRight;
//case '>': return fLeft > fRight;
//case '<': return fLeft < fRight;
//case '>=': return fLeft >= fRight;
//case '<=': return fLeft <= fRight;
//case '==': return fLeft == fRight;
//case '!=': return fLeft != fRight;
//case '||': return fLeft || fRight;
//case '&&': return fLeft && fRight;
case '&': return static_cast<number_t>(static_cast<unsigned long>(fLeft) & static_cast<unsigned long>(fRight));
case '|': return static_cast<number_t>(static_cast<unsigned long>(fLeft) | static_cast<unsigned long>(fRight));
case '~': return static_cast<number_t>(~static_cast<unsigned long>(fRight));
case '>>': return static_cast<number_t>(static_cast<unsigned long>(fLeft) >> static_cast<unsigned long>(fRight));
case '<<': return static_cast<number_t>(static_cast<unsigned long>(fLeft) << static_cast<unsigned long>(fRight));
default:
{
printf("ERROR: Invalid Operator Found\n");
return 0.0f;
}
}
}
else if(nType == TOKEN_NUMBER)
return pNode->fValue;
else if(nType == TOKEN_CALL)
return CreateCall(pNode); //not implemented
else if(nType == TOKEN_GLOBAL)
return GetGlobal(pNode);
else if(nType == TOKEN_ARGUMENT)
return GetArgument(pNode);
else if(nType == TOKEN_STRING)
return 0.0f;
return 0.0f;
}
Irgendwelche Tipps/Hinweise/Ratschläge oder nützliche Links, wie ich das erreichen kann?
Eine kleine Auswahl an Beispielen (wie gewünscht):
Was bei mir bereits funktioniert
Eingang: 2 * (3 ^ 1.5) - 4 / (1 << 3)
Ausgabe: In-Order: 2.0 * 3.0 ^ 1.5 - 4.0 / 1.0 << 3.0
Pre-Order: - * 2.0 ^ 3.0 1.5 / 4.0 << 1.0 3.0
Post-Order: 2.0 3.0 1.5 ^ * 4.0 1.0 3.0 << / -
Result: 9.892304
Was ich hinzufügen möchte
Eingang: (GetDay() == 31) ? -15.5 : 8.4
Ausgabe: 8.4
Ausgabe am 31.: -15.5
Eingang: max([0],20) (wobei [0] Argument 0 bezeichnet und [0] = 35)
Ausgabe: 20
Eingang: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (wobei [0] das Argument 0 ist und [0] auf einen gültigen Index gesetzt ist)
Ausgabe (wenn years_of_service für den Mitarbeiter weniger als 10 beträgt: 0.15
sonst Ausgabe: 0.07
Es handelt sich im Wesentlichen um Mathematik mit einigen C-inspirierten Ergänzungen, außer dass Argumente nicht nach Namen, sondern nach Index übergeben werden und Zeichenfolgen durch einfache Anführungszeichen statt doppelte Anführungszeichen maskiert werden.
Wenn ich das letzte Stück fertig habe, hoffe ich, dass ich es entweder per Bytecode kompilieren oder per JIT kompilieren kann, da ich vorhabe, dies für Dinge wie Spiele oder mathematikabhängige Programme zu verwenden, bei denen die Eingabesatzdaten konstant sind, der Eingabesatz jedoch kann sich ändern, wird aber häufig verwendet, daher muss es „schnell“ sein und von Nicht-Programmierern verwendet werden können.
Lösung
Das Richtige?Und :hängt vom vom Parser erzeugten Baum ab.Ich werde so tun, als würde der Parser einen Baum generieren
?
b :
t f
Zuerst müssen Sie die Bäume vor dem Wechsel nicht bewerten, und an den meisten Stellen ändern Sie so etwas
fLeft + fRight;
hinein
EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);
Dabei wird + durch alle verschiedenen Operatoren ersetzt.
Für ?:du tust ....
case ':': return 0.0f; /* this is an error in the parse tree */
case '?': if (!(pNode && pNode->pLeft && pNode->pRight &&
pNode->pRight->pLeft && pNode->pRight->pRight))
/* another error in the parse tree */
return 0.0f;
return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pRight->pLeft) :
EvaluateTree(pNode->pRight->pRight) ;
Für eine Definition von EvaluateBool haben Sie mehrere Möglichkeiten.Der C-Weg ist mehr oder weniger
BOOL EvaluateBool(Node* pNode)
{
return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}
Dann benötigen Sie Definitionen für „<“ und Freunde, die 0,0 für „falsch“ und alles andere für „wahr“ zurückgeben.Der Wert -1 ist ein sehr beliebter wahrer Wert, allerdings im Allgemeinen zum Speichern von Bools in Ints.
Der strukturiertere Weg besteht darin, alle Operatoren wie „<“, die boolesche Werte zurückgeben, in den Hauptteil von EvaluateBool zu verschieben und dafür zu sorgen, dass es mehr oder weniger wie EvaluateTree funktioniert.
Anstatt schließlich den ternären Operator ? zu erstellen:Wenn Sie zwei Knoten verwenden, können Sie auch die Definition des Knotens (und des Parsers) ändern, um bis zu drei Unterbäume zu haben. Dann hätten die meisten Operatoren zwei Bäume, aber ?:hätte drei.Vielleicht so etwas wie
case '?': return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pMiddle) :
EvaluateTree(pNode->pRight) ;
Aber dann müssen Sie Ihre Vorbestellungs-, In-Order- und Post-Order-Baumdurchquerungen neu schreiben.
Zweiter Teil, Funktionen.Eine Möglichkeit besteht darin, den Namen der Funktion in szValue zu speichern.Eine andere Möglichkeit besteht darin, dass es je nach Funktion eine Reihe unterschiedlicher Werte für nType gibt.Sie müssen im Parser eine Regel auswählen und diese hier im Interpreter verwenden.Du könntest so etwas tun wie...
else if(nType == TOKEN_CALL)
return EvaluateFunc(pNode);
Dann könnte EvaluateFunc in etwa so aussehen
number_t EvaluateFunc(Node* pNode)
{
if ((pNode == NULL) || (pNode->szValue == NULL))
return 0.0f;
if (0 == strcmp('cos', pNode->szValue))
return my_cos(EvaluateTree(pNode->pLeft));
else if (0 == strcmp('gcd', pNode->szValue))
return my_gcd(EvaluateTree(pNode->pLeft),
EvaluateTree(pNode->pRight));
/* etc */
else /* unknown function */ return 0.0f;
}
Sieht nach einem lustigen Projekt aus, viel Spaß!
Andere Tipps
Ich denke, Sie sollten Ihre „Node“-Struktur so ändern, dass sie ein Array von untergeordneten Elementen anstelle von „pLeft“ und „pRight“ hat.Eine Funktion wie sin() hat ein Argument/ein Kind.Der bedingte (ternäre) Operator hat drei Argumente/untergeordnete Elemente.
