In diesem Tutorial möchte ich euch zeigen, wie man einen Taschenrechner in der Sprache D erstellt. Das soll kein einfacher Taschenrechner werden, der über irgendwelchen switch-Statements überprüft, welcher mathematischer Operator ausgewählt werden soll und dann die entsprechenden Parameter einliest, nein er soll komplexere Terme wie "
max(sin(43),cos(31))*4^2" ausrechnen können.
Als ersten Schritt möchte ich mit der Frage beginnen, wie man überhaupt so einen Term auflöst. Sicher ist es ratsam zuerst den Term zu lexen, d.h in in seine Einzelteile zu zerlegen. Ein weiterer wichtiger Schritt ist die richtige Anordnung des Terms (hier kommt der Shunting-Yard-Algorithmus zum Einsatz), da es sonst sehr schwer wird, diesen abzuarbeiten.
Beginnen wir also mit der
Planung des Programms:
- Es soll eine Hauptfunktion namens 'calculate' geben, welche alle Arbeitsschritte des Moduls zusammenfasst
- Funktion für die korrekte Trennung der Rechentypen (Zahl, Operator und Funktion)
- Funkion für die richtige Anordnung für die spätere Umwandlung in ein Double-Wert (Der Shunting-Yard-Algorithmus, welcher den String in Reversed Polnish Notation umwandelt)
- Funktion für die Abarbeitung und des Strings (Hier wird gerechnet)
- kleinere Helfer-Methoden, die gut zu gebrauchen sind
- Datentypen, die die Operatoren und Funktionen beschreiben. Diese werden später benötigt, da sie in einem Stack abgelegt werden und dort entsprechend abgearbeitet werden (zB. für die Änderung der Anordnung der Operatoren/Funktionen)
Des weiteren beinhaltet dieses Modul Funktionen, die nicht in der Standard-Lib vorhanden sind (die habe ich geschrieben), aber einer genaueren Erläuterung nicht Wert sind. Achtung: D bietet die Möglichkeit an, diese Methoden als Extension zu verwenden, weshalb man glauben könnte, dass es sich bei dem betreffenden Datentyp um ein Objekt handelt, was aber nicht der Fall ist. Ein Beispiel:
|
|
1
2
3
4
| ...
char[] hallo = "Hallo Welt";
int i = hallo.findFirst('l');
...
|
Diese Methoden sind im Anhang (dort ist auch ein Beispielprogramm des Moduls untergebracht) unter extd/array.d zu finden (Nachdem ihr die Datei entpackt habt). Hier die Liste der hier nicht aufgeführten Methoden:
- int findFirst(T)(T[] array, T item);
- int findFirst(T)(T[] array, T[] item);
- bool contains(T)(T[] array, T item);
- bool contains(T)(T[] array, T[] item);
- T[] reverse(T)(T[] array);
- T pushLast(T[] array);
Jetzt kommen wir zur Implementierung. Ich möchte hier mit der Hauptfunktion beginnen, damit ihr eine Übersicht habt, welche Funktionen wie heißen, und wie sie mit dem gesamten Modul in Verbindung stehen:
(Wenn ihr das selber macht, solltet ihr das natürlich anders angehen (Im Kopf und(oder auf einem Blatt Papier... ;-) )
Als nächstes machen wir mit den Operatoren und Funktionen weiter. Diese müssen folgende Kriterien erfüllen:
- Bekannte Parameterzahl (Damit später bekannt ist, wie viele Werte vom Stack, in dem die Ergebnisse temporär gespeichert werden, zu holen sind)
- Bekannte Assoziation (Links oder rechts)
- Bekannte Priorität (Wichtig für die "Punkt vor Strich-Regel")
- Zeiger auf Funktion (für die Rechnung)
Nichts liegt näher, als diese ein einem Typ (in diesem Fall eine Struktur) zusammenzufassen:
Damit man diese Operatoren und Funktionen auch leichter ansprechen kann, habe ich jeweils ein assoziatives Array (Das Array der Operatoren ist selbstverständlich konstant) erstellt, was die Operatoren und Funktionen mit dem Passenden Schlüssel speichert. Die Initialisierung findet im Konstruktor des Moduls statt:
Hier sind die kleinen Helfer-Methoden, welche für die Identifizierung der Teil-Terme zuständig sind:
Das wäre geschafft. Jetzt können wir mit der ersten eigentlichen Funktion "lexString" beginnen. Diese Funktion dient dazu, den String in seine Einzel-Teile zu zerlegen. Das sollte auch kein sonderlich großes Problem sein:
So jetzt haben wir einen funktionstüchtigen Lexer, der uns alle verschiedene Typen in ein extra Array speichert ( '(' und ')' sind auch Operatoren).