Okay, Scherz beiseite. Implementiert habe ich eine Teilform des Shunting-Yard-Algorithmus (ohne Unterstützung für Funktionen).
Unterstützt werden die vier Grundrechenarten zusammen mit Potenzierung (habe allerdings keine Konstanten eingebaut; sowas wie "e^123" ist also nicht möglich) und Klammerung.
"Punkt vor Strich" usw. wird befolgt und wenn ein Ausdruck mal nicht ausgewertet werden kann, dann wird einfach NAN (not a number) zurückgegeben; das printf gibt entsprechend dann "= nan" als Ergebnis aus.
Unäre Minuszeichen (Minus als Vorzeichen, statt als Operation; beispielsweise bei "-1") und die Konvention den Malpunkt vor einer Klammer weglassen zu können sind ebenfalls implementiert.
Der Sourcecode ist gleichzeitig sein eigenes Bash Compile-Script (wollte das mal wieder ausprobieren; ist nicht meine Idee -- habe ich vor ein paar Jahren mal irgendwo gelesen).
Das ganze sieht dann etwa so aus:
Für eine Beschreibung des Shunting-Yard-Algorithmus verweise ich an der Stelle einfach mal auf Wikipedia (dort finden sich auch ein paar schöne Diagramme, die die Funktionsweise anhand einiger Beispiele gut verdeutlichen).
Das Programm arbeitet in drei Schritten, die alle von "sy_eval_expression" initiiert werden.
Im ersten Schritt wird der übergebene Ausdruck in Tokens aufgeteilt. Bei den Operatoren/Klammern ist das geradezu langweilig und eigentlich nicht mal erwähnenswert. Schwieriger wird die Angelegenheit mit den Zahlen, die ja oft aus mehr als nur einer Ziffer bestehen. Da mit doubles gearbeitet wird kommt auch noch das Behandeln von Nachkommastellen hinzu.
Im Prinzip implementiert Schritt 1 also eine Art atof-Funktion, die einfach aufhört auszuwerten, wenn sie auf etwas trifft, das nicht mehr zum double gehört.
Hinzu kommen dann eben noch ein paar kleine Tricks, um auch ein Vorzeichen von einem Minus als Operator unterscheiden zu können und das Weglassen von Mal-Zeichen in Ausdrücken wie "2(3)" (statt "2*(3)") zu unterstützen.
In Zeile 70 wird dann eben überprüft, ob es sich beim aktuell eingelesenen Zeichen um eine aufgehende Klammer handelt und falls ja, ob unmittelbar davor eine Klammer geschlossen wurde (wie etwa in "(1+2)(3+4)"), oder ob davor eine Zahl stand (etwa "2(3)"). Wenn ja, so wird ein Mal-Zeichen eingefügt.
In Zeile 73 läuft das ganze für eine geschlossene Klammer ab. Dabei wird nur überprüft, ob dahinter eine Zahl steht (wie etwa "(2)3"; ob dahinter eine Klammer aufgeht wird nicht überprüft, da die aufgehende Klammer ja schon ein Mal-Zeichen einfügen würde [vgl. Zeile 70]).
In Zeile 68 entsteht der Support für das Minus als Vorzeichenindikator. Ist der Operator nämlich ein Minus und steht unmittelbar hinter einem der Zeichen "(*/^", so wird das Minus als Vorzeichen gedeutet und der Code in den Zeilen 70-75 wird nicht ausgeführt; insbesondere nicht das "break" in Zeile 75, also wird wie das eben bei switch so ist munter weiter Code ausgeführt... dieser Code ist dann aber zum Einlesen der Zahlen zuständig; dieser behandelt auch gleich den Fall, dass ein Minuszeichen davor steht.
Im zweiten Schritt wird der nun vorliegende Tokenstream, der den Ausdruck in infix-Notation repräsentiert mit dem Shunting-Yard-Algorithmus in die postfix-Notation überführt (also die Tokens entsprechend umsortiert; Rückgabewert ist wieder ein Stack mit Tokens).
Der dritte Schritt wertet nun den Ausdruck aus (Zeile 187ff.).
Wie auch immer... hier der Sourcecode:
http://pastie.org/2582205 (alt)
https://pastebin.com/hY0rgLJM (neu)
[C++] Taschenrechner (Anfängerprojekt? Orly?)
Zitieren
