Hallo,
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.
Ich wünsche euch viel Spaß beim lesen... ;-)
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:
|
Quellcode
|
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:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/**
* Calculate the term-string
*/
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
if (!lexStr(term, lxdTerm))
{
throw new Exception("Syntax Error!\n");
}
// Transform the string with the Shunting Yard Algo
// in the reverse ploish notation
if (!shuntingYard(lxdTerm, output))
{
throw new Exception("Syntax Error!\n");
}
// Calculte the reversed polish notation string
double result = calcShunt(output);
return result;
}
|
(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 und Operatoren 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:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
|
enum MATH_ASSOCIATION { LEFT_ASSOC, RIGHT_ASSOC };
struct MATH_OPERATION
{
char[] op;
int parameter;
MATH_ASSOCIATION assoc;
int preced;
double function(double[]) calc;
};
|
Da ich beschlossen habe, die Funktionen Separat zu behandeln, habe ich für diese eine eigene Struktur definiert (Wäre aber nicht nötigt gewesen:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
|
struct MATH_FUNCTION
{
char[] functionName;
char[] description;
int parameter;
double function(double[]) func;
};
|
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:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
static const MATH_OPERATION[char] operations; // All internal operations
public MATH_FUNCTION[char[]] functions; // All functions for runtime
static this()
{
operations = [
'(' : MATH_OPERATION("(", 0, MATH_ASSOCIATION.LEFT_ASSOC, -1, null),
')' : MATH_OPERATION(")", 0, MATH_ASSOCIATION.LEFT_ASSOC, -1, null),
'+' : MATH_OPERATION("+", 2, MATH_ASSOCIATION.LEFT_ASSOC, 1, &add),
'-' : MATH_OPERATION("-", 2, MATH_ASSOCIATION.LEFT_ASSOC, 1, &sub),
'*' : MATH_OPERATION("*", 2, MATH_ASSOCIATION.LEFT_ASSOC, 2, &mul),
'/' : MATH_OPERATION("/", 2, MATH_ASSOCIATION.LEFT_ASSOC, 2, &div),
'!' : MATH_OPERATION("!", 1, MATH_ASSOCIATION.RIGHT_ASSOC, 3, &fak),
'^' : MATH_OPERATION("^", 2, MATH_ASSOCIATION.RIGHT_ASSOC, 3, &pow)
];
functions["sin"] = MATH_FUNCTION("sin", "Return the sinus-value of param.", 1, &sin);
functions["cos"] = MATH_FUNCTION("cos", "Return the sinus-value of param.", 1, &cos);
functions["tan"] = MATH_FUNCTION("tan", "Return the sinus-value of param.", 1, &cos);
functions["max"] = MATH_FUNCTION("max", "Return the higher value of param.", 2, &max);
functions["min"] = MATH_FUNCTION("min", "Return the lower value of param.", 2, &min);
}
/* 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)
{
return 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;
}
double pow(double[] p)
{
return std.math.pow(p[0], p[1]);
}
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];
}
|
Hier sind die kleinen Helfer-Methoden, welche für die Identifizierung der Teil-Terme zuständig sind:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
/**
* 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(char[] 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(char[] 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;
}
|
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:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
bool lexStr(string term, ref 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])) {}
if (!isNumber(term[i])) --i;
lxdTerm ~= term[firstNr..i+1];
}
else // it should be a function
{
int firstC = i;
while (i<term.length-1 && isFunction(term[++i])) {}
if (term[i] != '(') return false;
if (i-1<=0) return false;
lxdTerm ~= term[firstC..i];
--i;
}
}
i++;
}
return true;
}
|
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:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
/**
* The shunting yard algorithm transfer the term into
* the reversed polish notation
*/
bool shuntingYard(char[][] lxdTerm, ref string[] output)
{
MATH_OPERATION[] opStack;
MATH_OPERATION *pCurOp;
for (int i = 0; i < lxdTerm.length; ++i)
{
char[] item = lxdTerm[i];
if (isNumber(item))
{
output ~= item;
}
else if (item == ",")
{
bool pe = false;
for (int j = opStack.length-1; opStack.length > 0; j--)
{
if (opStack[j].op == "(")
{
pe = true;
break;
}
else
{
output ~= opStack.pushLast().op;
}
}
if (!pe)
{
writef("There was an error with the parameter (near pos %d)!\n", i);
return false;
}
}
else if (isOperation(*item))
{
pCurOp = &operations[*item];
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)
{
writef("There is missing the left parenthese (position %d)!\n", i);
return false;
}
}
/* If the precedence of the current operation is lower or equl 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(item))
{
// now we 'smuggle' our fake operation in the stack
MATH_FUNCTION *f; // Our math function
if ((f = (item in functions))!= null)
{
MATH_OPERATION op = {f.functionName, f.parameter, MATH_ASSOCIATION.RIGHT_ASSOC, 3, null};
opStack ~= op;
}
else
{
writef("Error: unknown function: %s\n", item);
delete opStack;
return false;
}
}
}
/* If there any stacks, we will put them to the output (last in - first out) */
foreach_reverse (item; opStack)
{
output ~= [item.op];
}
delete opStack;
return true;
}
|
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 wie einen Operator benötigen, fassen diese die obersten Elemente (Anzahl der Elemente von der Parameteranzahl der Funktion abhännig) in ein Stack-Element zusammen. Das ganze kann dann ungefähr so aussehen:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
double calcShunt(char[][] term)
{
double[] rStack;// the result-Stack
char[] 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 ~= toDouble(str);
}
else if (isOperation(*str))
{
MATH_OPERATION op = operations[*str];
double[] param;
for (int j = op.parameter; j!=0; j--)
{
param ~= rStack.pushLast();
}
if (op.assoc == MATH_ASSOCIATION.LEFT_ASSOC) param = param.reverse();
rStack ~= op.calc(param);
}
else if (isFunction(str))
{
MATH_FUNCTION* f = str in functions;
// The parameter for the function
double[] param;
for (int j = f.parameter; j!=0; j--)
{
param ~= rStack.pushLast();
}
rStack ~= f.func(param);
}
else // Unknown Syntax
{
throw new Exception("Unknown Syntax!");
}
}
return (rStack.length > 0) ? rStack[0] : 0.0;
}
|
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!