Ich habe einen Gleichungsparser entwickelt, der einen einfachen Stapelalgorithmus verwendet, der binäre (+, -, |, &, *, / usw.) Operatoren, unäre (!) Operatoren und Klammern verarbeitet.
Wenn ich diese Methode verwende, habe ich jedoch alles mit der gleichen Priorität - sie wird unabhängig vom Operator von links nach rechts ausgewertet, obwohl die Priorität in Klammern erzwungen werden kann.
Im Moment gibt "1 + 11 * 5" also 60 zurück, nicht 56, wie man erwarten könnte.
Während dies für das aktuelle Projekt geeignet ist, möchte ich eine Allzweckroutine haben, die ich für spätere Projekte verwenden kann.
Aus Gründen der Übersichtlichkeit bearbeitet:
Was ist ein guter Algorithmus zum Parsen von Gleichungen mit Vorrang?
Ich interessiere mich für etwas Einfaches zu implementieren und zu verstehen, dass ich mich selbst codieren kann, um Lizenzprobleme mit verfügbarem Code zu vermeiden.
Grammatik:
Ich verstehe die Grammatikfrage nicht - ich habe sie von Hand geschrieben. Es ist einfach genug, dass ich keine Notwendigkeit für YACC oder Bison sehe. Ich muss lediglich Zeichenfolgen mit Gleichungen wie "2 + 3 * (42/13)" berechnen.
Sprache:
Ich mache das in C, aber ich interessiere mich für einen Algorithmus, nicht für eine sprachspezifische Lösung. C ist so niedrig, dass es bei Bedarf leicht in eine andere Sprache konvertiert werden kann.
Codebeispiel
Ich habe den Testcode für den Parser für einfache Ausdrücke gepostet, über den ich oben gesprochen habe. Die Projektanforderungen haben sich geändert, sodass ich den Code nie für Leistung oder Speicherplatz optimieren musste, da er nicht in das Projekt integriert war. Es ist in der ursprünglichen ausführlichen Form und sollte leicht verständlich sein. Wenn ich in Bezug auf die Operatorrangfolge etwas weiter damit mache, werde ich wahrscheinlich den Makro-Hack wählen, da er der Einfachheit halber mit dem Rest des Programms übereinstimmt. Wenn ich dies jedoch jemals in einem realen Projekt verwende, werde ich mich für einen kompakteren / schnelleren Parser entscheiden.
Verwandte Frage
-Adam
Antworten:
Der harte Weg
Sie möchten einen Parser für rekursiven Abstieg .
Um Vorrang zu haben, müssen Sie rekursiv denken, z. B. mithilfe Ihrer Beispielzeichenfolge.
Um dies manuell zu tun, müssten Sie das lesen
1
, dann das Plus sehen und eine ganz neue rekursive Analyse "Sitzung" starten, beginnend mit11
... und sicherstellen, dass Sie das11 * 5
in seinen eigenen Faktor analysieren, um einen Analysebaum mit zu erhalten1 + (11 * 5)
.Dies alles fühlt sich so schmerzhaft an, selbst zu versuchen, es zu erklären, insbesondere mit der zusätzlichen Ohnmacht von C. Sehen Sie, nach dem Parsen der 11, wenn das * tatsächlich ein + wäre, müssten Sie den Versuch, einen Begriff zu bilden, abbrechen und stattdessen das analysieren
11
selbst als Faktor. Mein Kopf explodiert bereits. Es ist mit der rekursiven anständigen Strategie möglich, aber es gibt einen besseren Weg ...Der einfache (richtige) Weg
Wenn Sie ein GPL-Tool wie Bison verwenden, müssen Sie sich wahrscheinlich keine Gedanken über Lizenzprobleme machen, da der von Bison generierte C-Code nicht von der GPL abgedeckt wird (IANAL, aber ich bin mir ziemlich sicher, dass GPL-Tools die GPL nicht erzwingen generierter Code / Binärdateien (zum Beispiel Apple kompiliert Code wie beispielsweise Aperture mit GCC und sie verkaufen ihn, ohne den Code GPL zu müssen).
Laden Sie Bison herunter (oder etwas Ähnliches, ANTLR usw.).
Normalerweise gibt es einen Beispielcode, mit dem Sie Bison einfach ausführen und den gewünschten C-Code erhalten können, der diesen Rechner mit vier Funktionen demonstriert:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Schauen Sie sich den generierten Code an und stellen Sie fest, dass dies nicht so einfach ist, wie es sich anhört. Die Vorteile eines Tools wie Bison sind außerdem: 1) Sie lernen etwas (insbesondere, wenn Sie das Drachenbuch lesen und etwas über Grammatiken lernen). 2) Sie vermeiden, dass NIH versucht, das Rad neu zu erfinden. Mit einem echten Parser-Generator-Tool können Sie später skalieren und anderen Personen zeigen, dass Parser die Domäne von Parsing-Tools sind.
Aktualisieren:
Die Leute hier haben viele gute Ratschläge gegeben. Meine einzige Warnung vor dem Überspringen der Parsing-Tools oder der Verwendung des Shunting Yard-Algorithmus oder eines handgerollten rekursiven anständigen Parsers ist, dass kleine Spielzeugsprachen 1 eines Tages zu großen tatsächlichen Sprachen mit Funktionen (sin, cos, log) und Variablen, Bedingungen und für werden können Schleifen.
Flex / Bison kann für einen kleinen, einfachen Interpreter durchaus übertrieben sein, aber ein einmaliger Parser + Evaluator kann später zu Problemen führen, wenn Änderungen vorgenommen oder Funktionen hinzugefügt werden müssen. Ihre Situation wird unterschiedlich sein und Sie müssen Ihr Urteilsvermögen einsetzen. Bestrafe einfach keine anderen Menschen für deine Sünden [2] und baue ein weniger als angemessenes Werkzeug.
Mein Lieblingswerkzeug zum Parsen
Das beste Werkzeug der Welt für diesen Job ist die Parsec- Bibliothek (für rekursive anständige Parser), die mit der Programmiersprache Haskell geliefert wird. Es ähnelt stark BNF oder einem speziellen Tool oder einer domänenspezifischen Sprache zum Parsen (Beispielcode [3]), ist jedoch nur eine reguläre Bibliothek in Haskell, was bedeutet, dass es im selben Erstellungsschritt wie die anderen kompiliert wird Sie können beliebigen Haskell-Code schreiben und diesen in Ihrem Parser aufrufen, und Sie können andere Bibliotheken im selben Code mischen und abgleichen . (Das Einbetten einer Parsing-Sprache wie dieser in eine andere Sprache als Haskell führt übrigens zu einer Menge syntaktischer Cruft. Ich habe dies in C # gemacht und es funktioniert ganz gut, aber es ist nicht so hübsch und prägnant.)
Anmerkungen:
1 Richard Stallman sagt in Warum Sie Tcl nicht verwenden sollten
[2] Ja, ich habe für immer Angst davor, diese "Sprache" zu benutzen.
Beachten Sie auch , dass , wenn ich diesen Eintrag vorgelegt, die Vorschau war richtig, aber SO ist weniger als ausreichend Parser meiner Nähe Anker - Tag auf dem ersten Absatz aß , was beweist , dass Parser sind nicht etwas zu spaßen , denn wenn Sie reguläre Ausdrücke verwenden und eine off - Hacks Sie wird wahrscheinlich etwas subtiles und kleines falsch machen .
[3] Ausschnitt eines Haskell-Parsers mit Parsec: Ein Vierfunktionsrechner, der um Exponenten, Klammern, Leerzeichen für die Multiplikation und Konstanten (wie pi und e) erweitert wurde.
quelle
Der Rangierbahnhof-Algorithmus ist dafür das richtige Werkzeug. Wikipedia ist diesbezüglich wirklich verwirrend, aber im Grunde funktioniert der Algorithmus folgendermaßen:
Angenommen, Sie möchten 1 + 2 * 3 + 4 bewerten. Intuitiv "wissen" Sie, dass Sie zuerst 2 * 3 ausführen müssen, aber wie erhalten Sie dieses Ergebnis? Der Schlüssel besteht darin, zu erkennen, dass Sie beim Scannen der Zeichenfolge von links nach rechts einen Operator auswerten, wenn der darauf folgende Operator eine niedrigere (oder gleichwertige) Priorität hat. Im Kontext des Beispiels möchten Sie Folgendes tun:
Wie setzen Sie das um?
Sie möchten zwei Stapel haben, einen für Zahlen und einen für Operatoren. Sie schieben die ganze Zeit Zahlen auf den Stapel. Sie vergleichen jeden neuen Operator mit dem am oberen Rand des Stapels. Wenn der am oberen Rand des Stapels eine höhere Priorität hat, entfernen Sie ihn vom Operatorstapel, entfernen die Operanden vom Zahlenstapel, wenden den Operator an und übertragen das Ergebnis auf den Zahlenstapel. Jetzt wiederholen Sie den Vergleich mit dem Top-of-Stack-Operator.
Zurück zum Beispiel: Es funktioniert folgendermaßen:
N = [] Ops = []
*
. N = [1 2], Ops = [+ *]*
3 aus und drücke das Ergebnis auf N. N = [1 6], Ops = [+]+
bleibt assoziativ, daher möchten Sie auch 1, 6 ausschalten und das + ausführen. N = [7], Ops = [].Dort ist das nicht so schwierig, oder? Und es werden keine Grammatiken oder Parser-Generatoren aufgerufen.
quelle
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Sehr gute Erklärung verschiedener Ansätze:
Geschrieben in einfacher Sprache und Pseudocode.
Ich mag 'Priority Climbing'.
quelle
Es gibt einen schönen Artikel hier über einen einfachen rekursiven Abstieg Parser mit Operator-Vorrang - Analyse kombiniert. Wenn Sie kürzlich Parser geschrieben haben, sollte das Lesen sehr interessant und lehrreich sein.
quelle
Vor langer Zeit habe ich meinen eigenen Parsing-Algorithmus entwickelt, den ich in keinem Parsing-Buch (wie dem Dragon Book) finden konnte. Wenn ich mir die Zeiger auf den Shunting Yard-Algorithmus ansehe, sehe ich die Ähnlichkeit.
Vor ungefähr 2 Jahren habe ich auf http://www.perlmonks.org/?node_id=554516 einen Beitrag darüber mit Perl-Quellcode verfasst . Es ist einfach, in andere Sprachen zu portieren: Die erste Implementierung, die ich durchgeführt habe, war in Z80 Assembler.
Es ist ideal für die direkte Berechnung mit Zahlen, aber Sie können es verwenden, um einen Analysebaum zu erstellen, wenn Sie müssen.
Update Da mehr Benutzer Javascript lesen (oder ausführen) können, habe ich meinen Parser in Javascript neu implementiert, nachdem der Code neu organisiert wurde. Der gesamte Parser enthält weniger als 5.000 KB Javascript-Code (ca. 100 Zeilen für den Parser, 15 Zeilen für eine Wrapper-Funktion), einschließlich Fehlerberichterstattung und Kommentaren.
Eine Live-Demo finden Sie unter http://users.telenet.be/bartl/expressionParser/expressionParser.html .
quelle
Es wäre hilfreich, wenn Sie die Grammatik beschreiben könnten, die Sie derzeit zum Parsen verwenden. Klingt so, als ob das Problem dort liegen könnte!
Bearbeiten:
Die Tatsache, dass Sie die Grammatikfrage nicht verstehen und dass Sie dies von Hand geschrieben haben, erklärt sehr wahrscheinlich, warum Sie Probleme mit Ausdrücken der Form '1 + 11 * 5' haben (dh mit Operator-Vorrang). . Wenn Sie beispielsweise nach "Grammatik für arithmetische Ausdrücke" googeln, sollten Sie einige gute Hinweise erhalten. Eine solche Grammatik muss nicht kompliziert sein:
würde zum Beispiel den Trick machen und kann trivial erweitert werden, um sich um einige kompliziertere Ausdrücke zu kümmern (einschließlich Funktionen zum Beispiel oder Potenzen, ...).
Ich schlage vor, Sie sehen sich zum Beispiel diesen Thread an.
Fast alle Einführungen in Grammatiken / Parsing behandeln arithmetische Ausdrücke als Beispiel.
Beachten Sie, dass die Verwendung einer Grammatik keinesfalls die Verwendung eines bestimmten Werkzeugs ( a la Yacc, Bison, ...) bedeutet. In der Tat verwenden Sie mit Sicherheit bereits die folgende Grammatik:
(oder so etwas) ohne es zu wissen!
quelle
Haben Sie darüber nachgedacht, Boost Spirit zu verwenden ? Es ermöglicht Ihnen, EBNF-ähnliche Grammatiken in C ++ wie folgt zu schreiben:
quelle
Wenn Sie Ihre Frage stellen, besteht keinerlei Rekursionsbedarf. Die Antwort lautet drei Dinge: Postfix-Notation plus Shunting Yard-Algorithmus plus Bewertung des Postfix-Ausdrucks:
1). Postfix-Notation = erfunden, um die Notwendigkeit einer expliziten Prioritätsspezifikation zu beseitigen. Lesen Sie mehr im Internet, aber hier ist das Wesentliche: Infix-Ausdruck (1 + 2) * 3, während es für Menschen leicht zu lesen und zu verarbeiten ist, was für die maschinelle Berechnung nicht sehr effizient ist. Was ist? Einfache Regel, die besagt, dass "Ausdruck durch Caching vorrangig neu geschrieben und dann immer von links nach rechts verarbeitet wird". Das Infix (1 + 2) * 3 wird also zu einem Postfix 12 + 3 *. POST, da der Operator immer NACH den Operanden steht.
2). Postfix-Ausdruck auswerten. Einfach. Lesen Sie die Zahlen aus der Postfix-Zeichenfolge. Schieben Sie sie auf einen Stapel, bis ein Bediener gesehen wird. Bedienertyp prüfen - unär? binär? Tertiär? Pop so viele Operanden vom Stapel wie nötig, um diesen Operator auszuwerten. Bewerten. Ergebnis wieder auf Stapel schieben! Und du bist fast fertig. Machen Sie so weiter, bis der Stapel nur noch einen Eintrag = Wert hat, den Sie suchen.
Machen wir (1 + 2) * 3, was im Postfix steht, ist "12 + 3 *". Lesen Sie die erste Zahl = 1. Schieben Sie sie auf den Stapel. Lesen Sie weiter. Nummer = 2. Schieben Sie es auf den Stapel. Lesen Sie weiter. Operator. Welcher? +. Welche Art? Binär = benötigt zwei Operanden. Pop-Stack zweimal = Argright ist 2 und Argleft ist 1. 1 + 2 ist 3. Schieben Sie 3 zurück auf den Stack. Lesen Sie als nächstes aus der Postfix-Zeichenfolge. Es ist eine Nummer. 3.Push. Lesen Sie weiter. Operator. Welcher? *. Welche Art? Binär = benötigt zwei Zahlen -> Pop-Stack zweimal. Erst in Argright, zweitens in Argleft. Betrieb auswerten - 3 mal 3 ist 9.Drücken Sie 9 auf den Stapel. Lesen Sie das nächste Postfix-Zeichen. Es ist null. Ende der Eingabe. Pop Stack onec = das ist deine Antwort.
3). Shunting Yard wird verwendet, um menschliche (leicht) lesbare Infix-Ausdrücke in Postfix-Ausdrücke umzuwandeln (auch menschliche, nach einiger Übung leicht lesbare). Einfach manuell zu codieren. Siehe Kommentare oben und net.
quelle
Gibt es eine Sprache, die Sie verwenden möchten? Mit ANTLR können Sie dies aus Java-Sicht tun. Adrian Kuhn hat eine ausgezeichnete Beschreibung, wie man eine ausführbare Grammatik in Ruby schreibt. Tatsächlich ist sein Beispiel fast genau Ihr Beispiel für einen arithmetischen Ausdruck.
quelle
Es hängt davon ab, wie "allgemein" es sein soll.
Wenn Sie möchten, dass es wirklich sehr allgemein ist, z. B. mathematische Funktionen wie sin (4 + 5) * cos (7 ^ 3) analysieren können, benötigen Sie wahrscheinlich einen Analysebaum.
In dem ich nicht denke, dass eine vollständige Implementierung angemessen ist, um hier eingefügt zu werden. Ich würde vorschlagen, dass Sie sich eines der berüchtigten " Drachenbücher " ansehen .
Wenn Sie jedoch nur Vorrangunterstützung wünschen , können Sie dies tun, indem Sie zuerst den Ausdruck in ein Postfix-Formular konvertieren, in dem ein Algorithmus zum Kopieren und Einfügen von Google verfügbar sein sollte, oder ich denke, Sie können ihn selbst mit einer Binärdatei codieren Baum.
Wenn Sie es in Postfix-Form haben, ist es von da an ein Kinderspiel, da Sie bereits verstehen, wie der Stapel hilft.
quelle
Ich würde vorschlagen, zu schummeln und den Shunting Yard-Algorithmus zu verwenden . Es ist ein einfaches Mittel zum Schreiben eines einfachen Parsers vom Typ eines Taschenrechners und berücksichtigt Vorrang.
Wenn Sie Dinge richtig tokenisieren und Variablen usw. einbeziehen möchten, würde ich einen rekursiven Abstiegsparser schreiben, wie von anderen hier vorgeschlagen. Wenn Sie jedoch einfach einen Parser im Taschenrechnerstil benötigen, sollte dieser Algorithmus ausreichen :-)
quelle
Ich habe dies auf der PIC-Liste über den Shunting Yard-Algorithmus gefunden :
-Adam
quelle
Eine weitere Ressource für das Parsen von Vorrang ist der Eintrag für den Operator-Vorrang-Parser in Wikipedia. Behandelt den Shunt-Yard-Algorithmus von Dijkstra und einen alternativen Baumalgorithmus, behandelt jedoch insbesondere einen wirklich einfachen Makro-Ersetzungsalgorithmus, der trivial vor jedem ignoranten Parser mit Vorrang implementiert werden kann:
Rufen Sie es auf als:
Das ist großartig in seiner Einfachheit und sehr verständlich.
quelle
Ich habe auf meiner Website eine Quelle für einen ultrakompakten Java Math Evaluator (1 Klasse, <10 KiB) veröffentlicht . Dies ist ein rekursiver Abstiegsparser des Typs, der die Schädelexplosion für das Poster der akzeptierten Antwort verursacht hat.
Es unterstützt volle Priorität, Klammern, benannte Variablen und Funktionen mit nur einem Argument.
quelle
Ich habe einen Ausdrucksparser veröffentlicht, der auf dem Shunting Yard- Algorithmus von Dijkstra unter den Bedingungen der Apache-Lizenz 2.0 basiert :
http://projects.congrace.de/exp4j/index.html
quelle
Ich habe im MathEclipse Parser- Projekt einen rekursiven Abstiegsparser in Java implementiert . Es kann auch als Google Web Toolkit- Modul verwendet werden
quelle
Ich arbeite derzeit an einer Reihe von Artikeln, die einen Parser für reguläre Ausdrücke als Lernwerkzeug für Entwurfsmuster und lesbare Programmierung erstellen. Sie können sich den lesbaren Code ansehen . Der Artikel beschreibt eine klare Verwendung des Rangierbahnhof-Algorithmus.
quelle
Ich habe einen Ausdrucksparser in F # geschrieben und hier darüber gebloggt . Es verwendet den Shunt-Yard-Algorithmus, aber anstatt von Infix zu RPN zu konvertieren, habe ich einen zweiten Stapel hinzugefügt, um die Ergebnisse der Berechnungen zu sammeln. Es behandelt die Priorität von Operatoren korrekt, unterstützt jedoch keine unären Operatoren. Ich habe dies geschrieben, um F # zu lernen, aber nicht um das Parsen von Ausdrücken zu lernen.
quelle
Eine Python-Lösung mit Pyparsing finden Sie hier . Das Parsen der Infixnotation mit verschiedenen Operatoren mit Vorrang ist ziemlich häufig, und daher umfasst das Pyparsing auch den
infixNotation
(früherenoperatorPrecedence
) Ausdrucksgenerator. Mit ihm können Sie einfach boolesche Ausdrücke definieren, indem Sie beispielsweise "UND", "ODER", "NICHT" verwenden. Oder Sie können Ihre Arithmetik mit vier Funktionen erweitern, um andere Operatoren zu verwenden, z. für Fakultät oder '%' für Modul oder fügen Sie P- und C-Operatoren hinzu, um Permutationen und Kombinationen zu berechnen. Sie können einen Infix-Parser für die Matrixnotation schreiben, der die Behandlung von '-1'- oder' T'-Operatoren (für Inversion und Transponierung) umfasst. Das operatorPrecedence-Beispiel eines Parsers mit 4 Funktionen (mit '!'quelle
Ich weiß, dass dies eine späte Antwort ist, aber ich habe gerade einen winzigen Parser geschrieben, mit dem alle Operatoren (Präfix, Postfix und Infix-links, Infix-rechts und nicht assoziativ) einen beliebigen Vorrang haben können.
Ich werde dies für eine Sprache mit willkürlicher DSL-Unterstützung erweitern, aber ich wollte nur darauf hinweisen, dass man keine benutzerdefinierten Parser für die Operatorpriorität benötigt, man kann einen generalisierten Parser verwenden, der überhaupt keine Tabellen benötigt, und sucht einfach nach der Priorität jedes Operators, wie er angezeigt wird. Die Leute haben benutzerdefinierte Pratt-Parser oder Rangier-Parser erwähnt, die illegale Eingaben akzeptieren können - diese müssen nicht angepasst werden und akzeptieren (sofern kein Fehler vorliegt) keine schlechten Eingaben. Es ist in gewissem Sinne nicht vollständig, es wurde geschrieben, um den Algorithmus zu testen, und seine Eingabe erfolgt in einer Form, die eine Vorverarbeitung erfordert, aber es gibt Kommentare, die dies klar machen.
Beachten Sie, dass einige gängige Arten von Operatoren fehlen, z. B. die Art des Operators, der zum Indizieren verwendet wird, z. B. Tabelle [Index] oder Aufrufen einer Funktionsfunktion (Parameterausdruck, ...). Ich werde diese hinzufügen, aber beide als Postfix betrachten Operatoren, bei denen das, was zwischen den Trennzeichen '[' und ']' oder '(' und ')' steht, mit einer anderen Instanz des Ausdrucksparsers analysiert wird. Es tut mir leid, dass ich das ausgelassen habe, aber der Postfix-Teil ist in - das Hinzufügen des Restes wird wahrscheinlich fast die doppelte Größe des Codes haben.
Da der Parser nur aus 100 Zeilen Schlägercode besteht, sollte ich ihn vielleicht hier einfügen. Ich hoffe, dass dies nicht länger ist, als es der Stackoverflow zulässt.
Einige Details zu willkürlichen Entscheidungen:
Wenn ein Postfix-Operator mit niedriger Priorität um dieselben Infixblöcke wie ein Präfix-Operator mit niedriger Priorität konkurriert, gewinnt der Präfix-Operator. Dies tritt in den meisten Sprachen nicht auf, da die meisten keine Postfix-Operatoren mit niedriger Priorität haben. - zum Beispiel: ((Daten a) (links 1 +) (vor 2 nicht) (Daten b) (nach 3!) (Links 1 +) (Daten c)) ist a + nicht b! + C, wo nicht a ist Präfixoperator und! ist ein Postfix-Operator und beide haben eine niedrigere Priorität als +, daher möchten sie auf inkompatible Weise entweder als (a + nicht b!) + c oder als + (nicht b! + c) gruppieren. In diesen Fällen gewinnt der Präfix-Operator immer Zweitens ist die Art und Weise, wie es analysiert
Nichtassoziative Infix-Operatoren sind wirklich vorhanden, sodass Sie nicht so tun müssen, als ob Operatoren, die andere Typen zurückgeben, als sie zusammen sinnvoll sind, aber ohne unterschiedliche Ausdruckstypen für jeden einen Kludge zu haben. Daher weigern sich nicht assoziative Operatoren in diesem Algorithmus, nicht nur sich selbst, sondern jedem Operator mit derselben Priorität zuzuordnen. Dies ist ein häufiger Fall, da << = ==> = usw. in den meisten Sprachen nicht miteinander assoziiert werden.
Die Frage, wie verschiedene Arten von Operatoren (links, Präfix usw.) die Rangfolge aufheben, sollte nicht auftauchen, da es nicht wirklich sinnvoll ist, Operatoren unterschiedlicher Typen dieselbe Priorität einzuräumen. Dieser Algorithmus macht in diesen Fällen etwas, aber ich mache mir nicht einmal die Mühe, genau herauszufinden, was, weil eine solche Grammatik überhaupt eine schlechte Idee ist.
quelle
Hier ist eine einfache rekursive Falllösung, die in Java geschrieben wurde. Beachten Sie, dass keine negativen Zahlen verarbeitet werden. Sie können dies jedoch hinzufügen, wenn Sie möchten:
}}
quelle
Der Algorithmus könnte leicht in C als rekursiver Abstiegsparser codiert werden.
Die nächsten Bibliotheken könnten nützlich sein: yupana - streng arithmetische Operationen; tinyexpr - arithmetische Operationen + C mathematische Funktionen + eine vom Benutzer bereitgestellte; mpc - Parser-Kombinatoren
Erläuterung
Lassen Sie uns eine Folge von Symbolen erfassen, die den algebraischen Ausdruck darstellen. Die erste ist eine Zahl, dh eine Dezimalstelle, die ein- oder mehrmals wiederholt wird. Wir werden diese Notation als Produktionsregel bezeichnen.
Der Additionsoperator mit seinen Operanden ist eine weitere Regel. Es sind eines
number
oder mehrere Symbole, die diesum "*" sum
Sequenz darstellen.Versuchen Ersatz
number
insum "+" sum
dem sein wird ,number "+" number
was wiederum in ausgeweitet werden könnte ,[0..9]+ "+" [0..9]+
dass schließlich reduziert werden könnte ,1+8
die die Expression korrekte Zugabe ist.Andere Substitutionen erzeugen ebenfalls den richtigen Ausdruck:
sum "+" sum
->number "+" sum
->number "+" sum "+" sum
->number "+" sum "+" number
->number "+" number "+" number
->12+3+5
Stück für Stück könnten wir einer Reihe von Produktionsregeln, auch Grammatik genannt , ähneln , die alle möglichen algebraischen Ausdrücke ausdrücken.
Um die Priorität des Bedieners zu kontrollieren, ändern Sie die Position seiner Produktionsregel gegenüber anderen. Schauen Sie sich die Grammatik oben an und beachten Sie, dass die Produktionsregel für
*
darunter platziert+
wird, um dieproduct
Auswertung vorher zu erzwingensum
. Die Implementierung kombiniert lediglich die Mustererkennung mit der Bewertung und spiegelt somit die Produktionsregeln genau wider.Hier bewerten wir
term
zuerst und geben es zurück, wenn es kein*
Zeichen gibt, nachdem es in unserer Produktionsregel ausgewählt wurde. Andernfalls bewerten Sie die Symbole danach und gebenterm.value * product.value
dies in unserer Produktionsregel zurück, d. H.term "*" product
quelle