Sonntag, 26. Juni 2011

Einen Taschenrechner in D programmieren

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).

Jetzt kommt eigentlich der schwierigste Teil des Tutorials. Hier wird der Term (der schon vom Lexer bearbeitet worden ist) so verändert, dass er später sehr leicht ab zu arbeiten ist. Hierzu habe ich mir den Shunting Yard-Algorithmus ausgesucht, der mir den Term in die Polnische Notation umwandelt. Da diese Themen relativ komplex sind und die Länge des Tutorials um Längen sprengen würde, bitte ich euch das Prinzip des Shunting-Yard Algo's und das der Polnischen Notation im Internet oder sonst wo zu recherchieren. Nur so viel sei zum Shunting-Yard-Algorithmus zu erwähnen: Man packt alle Operatoren in einen extra Stack und gibt sie je nach Priorität auch wieder aus, so dass am Ende die Operatoren hinter den Parametern stehen. (Auch eine Verschachtelung ist möglich) Kleines Beispiel: 4+5*3 wird zu 4 5 3 * +.
Genauer Infos findet ihr hier: http://en.wikipedia.org/wiki/Shunting-yard_algorithm
Das zur Theorie, hier der Code:



Wichtige Variablen:
  • lxdTerm: Dieses String-Array wird behandelt (Parameter der Funktion)
  • output: das in der RPN (Reversed Polnish Notation) formatierte String-Array (Result der Funktion)
  • opStack: Hier werden die Operationen zwischengespeichert
  • pCurOp: Zeiger auf aktuelle Operation (im lxdTerm-Array)
Beschreibung:
Wie wir am Code sehen können, wird jeder einzelne String im String-Array über eine for-Schleife behandelt. Dabei wird abgefragt, um welchen Typ es sich handelt. Ist es eine ganz normale Nummer, so wird diese dem output hinzugefügt, bei einer '('-Klammer dem Operatorenstack (hier ist keine Überprüfung nötig). Wird das Zeichen ',' gefunden (im Normalfall zur Trennung der Parameter gedacht) werden alle Operatoren bis zu ')' dem output hinzugefügt (so kann man schön alle Parameter abarbeiten). Wird das ')'-Zeichen gefunden, passiert im Grunde das selbe, wie beim ','(irgendwie logisch). Wird jedoch eine Operation anderer Art gefunden, so wird, falls die oberste Operation auf dem opStack eine höhere bzw. gleiche Priorität hat, wie die aktuelle Operation, diese (die Operation auf dem Stack) dem Output hinzugefügt.

So, das war der schwierigste Teil des Tutorials. Jetzt kommen wir zur finalen Arbeit: Wir arbeiten das Resultat des Shunting-Yard-Algorithmus von Zahl zu Zahl, von Operator zu Operator und von Funktion zu Funktion ab. Dabei speichern wir die Ergebnisse (Zahl liefert auch ein Ergebnis) in den Result-Stack, und sobald ein Operator oder eine Funktion kommt, welche mehr als einen Operator benötigen, fassen diese die obersten Elemente (Anzahl der Elemente von der Parameteranzahl der Funktion abhängig) in ein Stack-Element zusammen. Das ganze kann dann ungefähr so aussehen:



Das war schon alles. Natürlich können wir die Liste der Operatoren vergrößern, indem man zB. ein Plugin-System einbaut, welches die benötigten Strukturen lädt und in den function-hash hinzufügt. Außerdem wären Variablen nicht schlecht. Allerdings sollte man diese mit einem $ beginnen lassen (so wie zB. in PHP), damit man diese nicht mit einer Funktion verwechseln kann.

Ich hoffe, dass es sich (für euch) gelohnt hat dieses Tutorial zu lesen und ihr jetzt das Problem, falls ihr das jemals haben werden, angehen könnt!

Download eines Beispiel-Programms mit diesem Modul
Download 

Kommentare:

Architekt hat gesagt…

Du solltest dich wirklich mal mit regulären Ausdrücken beschäftigen.

Simon hat gesagt…

Hm. Ja, ich habe mal RegEx verwendet um einen Morse-Code zu decodieren und zu analysieren, allerdings war das mit Perl. Aber der Shunting Yard Algorithmus ist eigentlich ein gängiger Weg (neben der Baumstruktur...) um solche Terme aufzulösen.

Simon hat gesagt…

Außerdem kannte ich damals noch nicht das RegEx-Modul der Phobos Library ;-)

Architekt hat gesagt…

Kannst du denn Regex? (;

Simon hat gesagt…

Ich bin darin kein Experte, jedoch bin ich durchaus in der Lage Pattern zur Erkennung von Email-Adressen, Telefonnummern, etc ... zu erstellen.