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:

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

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:

	/**
	* The shunting yard algorythm transfers the term into
	* the polnish reverse notation
	*/
	string[] shuntingYard(string[] lxdTerm) {
	MATH_OPERATION[] opStack;
	MATH_OPERATION *pCurOp;
	string[] output;
	string str;
	for (int i = 0; i < lxdTerm.length; ++i) {
	str = lxdTerm[i];
	if (isNumber(str)) {
	output ~= str;
	}
	else if (str == ",") {
	bool pe = false;
	while (opStack.length > 0) {
	if (opStack[$-1].op == "(") {
	pe = true;
	break;
	} else {
	output ~= opStack.pushLast().op;
	}
	}
	if (!pe) {
	throw new Exception("Syntax Error!\n");
	}
	}
	else if (isOperation(*str)) {
	// At first we set the first Operator
	pCurOp = &operations[*str];
	if (pCurOp.op == "(") {
	opStack ~= *pCurOp;
	}
	else if (pCurOp.op == ")") {
	bool lParent=false;
	/* While '(' isn't found or the length of stack is
	higher than 0 */
	while (opStack.length>0) {
	MATH_OPERATION* tmpOp = &opStack[$-1];
	if (tmpOp.op == "(") {
	lParent = true;
	opStack.pushLast();
	break;
	} else {
	output ~= [tmpOp.op];
	opStack.pushLast();
	}
	}
	if (!lParent) {
	delete opStack;
	throw new Exception("Syntax Error");
	}
	}
	/* If the precedence of the current operation is lower or equal than the last
	element in the stack we can output the last element of the op-stack */
	else if (opStack.length > 0 && pCurOp.preced <=
	opStack[$-1].preced) {
	output ~= opStack[$-1].op; // the op goes to the output
	opStack[$-1] = *pCurOp;// We set the actual op to the stack
	} else {
	opStack ~= *pCurOp;
	}
	} // if isOperation
	else if (isFunction(str)) {
	MATH_OPERATION *f; // Our math function
	if ((f = str in functions) != null) {
	opStack ~= *f;
	} else {
	throw new Exception(format("Error: unknown function: %s\n",
	str));
	}
	}
	}
	// If there any items in the stack, we will put them to the output
	// (last in - first out)
	foreach_reverse (op; opStack) {
	output ~= [op.op];
	}
	return output;
	}

view raw calc.d hosted with ❤ by GitHub

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:

	double calcShunt(string[] term) {
	double[] rStack; // the result-Stack
	string str; // actual part of the term
	for (int i = 0; term.length > i; i++) {
	str = term[i];
	// Numbers always go in the result stack
	if (isNumber(str)) {
	rStack ~= to!double(str);
	} else if (isOperation(*str)) {
	MATH_OPERATION op = operations[*str];
	if (op.calc == null) {
	throw new Exception("Syntax Error!\n");
	}
	double[] param;
	for (int j = op.parameter; j>0; --j) {
	param ~= rStack.pushLast();
	}
	param = param.reverse();
	rStack ~= op.calc(param);
	} else if (isFunction(str)) {
	MATH_OPERATION* f = str in functions;
	// The parameter for the function
	double[] param;
	for (int j = f.parameter; j!=0; j--) {
	param ~= rStack.pushLast();
	}
	rStack ~= f.calc(param);
	} else { // Unknown Syntax
	throw new Exception("Syntax Error!\n");
	}
	}
	if (rStack.length != 1) {
	throw new Exception("Syntax Error!\n");
	}
	return rStack[0];
	}

view raw calc.d hosted with ❤ by GitHub

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