myDevCenter: Juni 2011

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:

	/**
	* Calculate the string term
	*/
	public double calculate(string term)
	{
	string[] lxdTerm; // Our lexed term string
	string[] output; // The shunting yard string

	// At first we have to lex the term
	lxdTerm = lexStr(term);

	// Transform the string with the Shunting Yard Algo
	// in the reverse ploish notation
	output = shuntingYard(lxdTerm);

	// Calculte the polish notation string
	double result = calcShunt(output);

	return result;
	}

view raw calc.d hosted with ❤ by GitHub

(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:

	struct MATH_OPERATION
	{
	string op; // the Token
	int parameter;
	MATH_ASSOCIATION assoc;
	int preced; // precedence
	double function(double[]) calc;
	};

view raw calc.d hosted with ❤ by GitHub

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:

	static this() {
	operations = [
	'(' : MATH_OPERATION("(",
	0,
	MATH_ASSOCIATION.LEFT_ASSOC,
	-1,
	null )
	/* the other ops... */
	];
	}
	/* operation functions */
	double add(double[] p) {
	return p[0]+ p[1];
	}

	double sub(double[] p) {
	return p[0] - p[1];
	}

	double mul(double[] p) {
	return p[0] * p[1];
	}

	double div(double[] p) {
	if (p[1] == 0) {
	throw new Exception("Math Error: Cannot divide through Zero!\n");
	}
	return *p / p[1];
	}

	double per(double[] p) {
	return p[0] / 100;
	}

	double pow(double[] p) {
	return std.math.pow(p[0], p[1]);
	}

	double fak(double[] p) {
	int result = cast(int)p[0];
	for (int i = result-1; 0 < i; --i) result *= i;
	return result;
	}

	/* mathematic functions */
	double sin(double[] p) {
	return std.math.sin(*p);
	}

	double cos(double[] p) {
	return std.math.cos(*p);
	}

	double tan(double[] p) {
	return std.math.tan(*p);
	}

	double max(double[] p) {
	return (p[0] < p[1]) ? p[1] : p[0];
	}

	double min(double[] p) {
	return (p[0] < p[1]) ? p[0] : p[1];
	}

view raw calc.d hosted with ❤ by GitHub

Hier sind die kleinen Helfer-Methoden, welche für die Identifizierung der Teil-Terme zuständig sind:

	/**
	* helper methods, which check the input
	*/

	bool isOperation(char c) {
	if (c == '*' \|\| c == '/' \|\| c == '-' \|\| c == '+' \|\| c == '%'
	\|\| c == '(' \|\| c == ')' \|\| c == '^' \|\| c == '!') {
	return true;
	} else {
	return false;
	}
	}

	bool isNumber(char c) {
	switch (c) {
	case '0':
	case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	case '.':
	return true;
	default:
	return false;
	}
	}

	bool isNumber(string str) {
	bool isDotIn = false;
	foreach (i, c; str) {
	if (c=='.') {
	if (isDotIn) return false;
	else isDotIn = true;
	}
	if (!isNumber(c)) return false;
	}
	return true;
	}

	bool isFunction(string str) {
	foreach (c; str) {
	if (!isFunction(c)) return false;
	}
	return true;
	}

	bool isFunction(char c) {
	if (isNumber(c) \|\| isOperation(c) \|\| c=='(' \|\| c==')') return false;
	return true;
	}

view raw calc.d hosted with ❤ by GitHub

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:

	/**
	* The lexer split the term into numbers, functions,
	* math operatoin and variables
	*/
	string[] lexStr(string term) {
	string[] lxdTerm;

	char[] tmpNr;
	char c;
	int i = 0;
	while (i<term.length) {
	c = term[i];
	if (c != ' ') {

	if (isOperation(c) \|\| c == ',') {
	lxdTerm ~= [c];
	}

	else if (isNumber(c)) {
	int firstNr = i;

	while (i<term.length-1 && isNumber(term[++i])) {
	// empty
	}

	if (!isNumber(term[i])) {
	--i; // Set the cursor back
	}

	lxdTerm ~= term[firstNr..i+1];
	}

	else if (isFunction(c)) { // it should be a function
	int sc = i;

	while (i<term.length-1 && isFunction(term[++i])) {
	// empty
	}

	if (term[i] != '(' \|\| i-1<=0) {
	throw new Exception("Syntax Error!\n");
	}

	lxdTerm ~= term[sc..i];
	--i; // We have to go back to '('
	} else {
	throw new Exception("Syntax Error!\n");
	}
	}
	i++;
	}
	return lxdTerm;
	}

view raw calc.d hosted with ❤ by GitHub

So jetzt haben wir einen funktionstüchtigen Lexer, der uns alle verschiedene Typen in ein extra Array speichert ( '(' und ')' sind auch Operatoren).

myDevCenter

Sonntag, 26. Juni 2011

Einen Taschenrechner in D programmieren

Samstag, 25. Juni 2011

GKasse - eine Gastrokasse

Hello World