Newer
Older
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
{
"cells": [
{
"cell_type": "markdown",
"id": "6761a365",
"metadata": {},
"source": [
"# <font color='blue'>**Übung 1 - Anwendung von Datenstrukturen**</font>\n",
"## <font color='blue'>**Problemstellung: Auswertung von Klammerausdrücken (Stack)**</font>\n",
"### <font color='blue'>**Problembeschreibung**</font>\n",
"\n",
"Die Reihenfolge von Rechenoperationen wird mithilfe von Klammern bestimmt. Es soll ein Skript entwickelt werden, das in der Lage ist, eine Zeichenkette wie zum Beispiel ````\"(((35+7)*(5-3))/2)\"```` auszuwerten und das Ergebnis zu ermitteln. Um eine kompakte Programmierung zu ermöglichen, gelten dabei für die Zeichenkette die folgende Anforderungen:\n",
"* Jede Operation muss umklammert werden. Folglich sind Eingaben wie ````1+2+3```` oder ````1-3*5```` nicht möglich. Es muss ````((1+2)+3)```` oder ````(1-(3*5))```` eingegeben werden.\n",
"* Verfügbare Operatoren sollen ````+````,````-````,````*````, und ````/```` sein.\n",
"* Gleitkommazahlen mit ````.```` sollen unterstützt werden.\n",
"* Negative Zahlen werden nicht unterstützt.\n",
"\n",
"### <font color='blue'>**Modellbildung**</font>\n",
"\n",
"Die Operatoren werden entsprechend ihrer mathematischen Definition in der von den Klammern vorgegebenen Reihenfolge ausgewertet.\n",
"\n",
"### <font color='blue'>**Algorithmierung**</font>\n",
"\n",
"Stacks sind eine geeignete Datenstruktur, um solche Klammerausdrücke auszuwerten. Das grundsätzliche Vorgehen ist, dass die Zeichenkette von vorne nach hinten durchlaufen wird, und dabei zwei Stacks (Operanden und Operatoren) gefüllt werden (`push`). Bei jeder schließenden Klammer, wird die neueste Operation ausgewertet und dabei ein Operator und zwei Operanden von den Stacks entfernt (`pop`). Das Ergebnis wird dem Operandenstack hinzufügt (`push`).<br>\n",
"<br>\n",
"Dieses Verfahren lässt sich gut an einem Beispiel zeigen:<br>\n",
"<br>\n",
">Zeichenkette: ````(1-(3*5))````.<br>\n",
"><br>\n",
">Bis zur ersten schließenden Klammer werden die Zahlen und die Operatoren in die Stacks hinzugefügt. Die Stacks haben dann folgenden Inhalt:<br>\n",
">Operanden: `[ 1, 3, 5 ]`<br>\n",
">Operatoren: `[ -, * ]`<br>\n",
"><br>\n",
">Bei der ersten schließenden Klammer werden nun der Operator ````*```` und die Operanden ````5, 3```` aus den Stacks geholt. Die Operation ````3*5```` wird berechnet und das Ergebnis (````15````) dem Operandenstack hinzugefügt.<br>\n",
"><br>\n",
">Die beiden Stacks sind dann folgendermaßen gefüllt:<br>\n",
">Operanden: `[ 1, 15 ]`<br>\n",
">Operatoren: `[ - ]`<br>\n",
"<br>\n",
">Es folgt eine weitere schließende Klammer und die nächste Operation ````1-15```` wird aus den Stacks geholt und berechnet. Das Ergebnis ````-14```` wird in den Operandenstack geschrieben. Der Operatorstack ist leer und die Zeichenkette ist vollständig durchlaufen. Das Ergebnis ist der Eintrag im Operandenstack: ````-14````\n",
"\n",
"Dieses Vorgehen werden wir in der Methode ````auswerten(ausdruck)```` implementieren.\n",
"\n",
"Wir erstellen eine Klasse ````AusdruckAuswerter````, um die benötigten Daten und Methoden zu gruppieren. Da die Klasse zwei Stacks als Attribute hat, benötigen wir zusätzlich eine Klasse ````Stack````. Diese ist allgemein und wir leiten sie in zwei Varianten ab. Diese verändern die Push-Methode, sodass ````OperatorStack```` nur das Speichern von Operatoren erlaubt und ```` OperandenStack```` die Eingaben direkt von Zeichen zu Zahlen konvertiert. \n",
"\n",
"Die vollständige Klassenstruktur ist hier im UML Diagramm gezeigt: "
]
},
{
"cell_type": "markdown",
"id": "0b489c77",
"metadata": {
"tags": []
},
"source": [
""
]
},
{
"cell_type": "markdown",
"id": "42dd5113",
"metadata": {},
"source": [
"Die Klasse `AusdruckAuswerter` speichert neben den Stacks noch Listen für die verschiedenen Zeichentypen. Zudem wird das Attribut `zahl` verwendet, um Zahlen mit mehr als einer Ziffer auswerten zu können. Neben der zentralen `auswerten()`-Methode sind das Berechnen der aktuellen Operation und das Zwischenspeichern von Zahlen mit mehreren Ziffern ausgelagert.\n",
"\n",
"Um Zahlen mit mehr als einem Zeichen einlesen zu können, wird beim Durchgehen der Zeichenkette ein als Zahl erkanntes Zeichen nicht direkt dem Stack hinzugefügt, sondern zunächst der Zeichenkette ````zahl```` hinzugefügt. Sobald ein eingelesenes Zeichen keine Zahl (oder Dezimalpunkt) ist und etwas in ````zahl```` eingetragen ist, dann wird ````zahl```` dem Stack hinzugefügt und anschließend zurückgesetzt. Dieses Prüfen, Eintragen und Zurücksetzen wird von der Methode ````push_zahl()```` übernommen. Sie wird aufgerufen, wenn das aktuelle Zeichen keine Ziffer ist."
]
},
{
"cell_type": "markdown",
"id": "e7768d99",
"metadata": {},
"source": [
"In der Methode ````auswerten()```` wird über alle Zeichen in der Zeichenkette iteriert. Je nach Zeichen werden folgende Schritte ausgeführt: \n",
"* ````(````: keine Aktion\n",
"* Operator: `push_zahl()` und Operator dem Stack hinzufügen\n",
"* Zahl oder Dezimalpunkt: Zeichen `zahl` hinzufügen\n",
"* `)`: `push_zahl()` und Operation auswerten\n",
"* Anderes: Ausgabe \"unerwartetes Zeichen\"\n",
"\n",
"Nach dem letzten Zeichen gibt die Methode die neueste Zahl des Operandenstacks zurück. Wenn die ausgewerte Zeichenkette den oben genannten Bedingungen entspricht, ist dies der einzige Eintrag.\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "3c3e484e",
"metadata": {},
"source": [
"In der Methode ````berechne_operation()```` wird zunächst der Operator vom Operatorstack geholt. Anschließend werden die Zahlen (Operanden) vom Operandenstack geholt. Je nach Operator wird das Ergebnis der Operation dem Operandenstack hinzugefügt. Bei der Berechnung muss darauf geachtet werden, dass der zuerst ausgelesene Operand derjenige hinter dem Operator ist (relevant für \"-\" und \"/\")."
]
},
{
"cell_type": "markdown",
"id": "c9cfb189",
"metadata": {},
"source": [
"### <font color='blue'>**Umsetzung**</font>\n",
"\n",
"Stack-Klassen:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "462ef289",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"class Stack:\n",
" def __init__(self):\n",
" self.stack = list()\n",
" \n",
" def push(self, element):\n",
" self.stack.append(element)\n",
" \n",
" def pop(self):\n",
" element = self.stack[-1]\n",
" self.stack = self.stack[:-1]\n",
" return element\n",
" #return self.stack.pop()\n",
" \n",
" def peek(self):\n",
" return self.stack[-1]\n",
" \n",
" def __len__(self):\n",
" return len(self.stack)\n",
" \n",
"class OperatorStack(Stack):\n",
" def push(self, element):\n",
" if len(element) == 1 and element in \"+-*/\":\n",
" self.stack.append(element)\n",
" else:\n",
" print( f\"Operator '{element}' nicht verfügbar.\" )\n",
"\n",
"class OperandenStack(Stack):\n",
" def push(self, element):\n",
" self.stack.append( float(element) )"
]
},
{
"cell_type": "markdown",
"id": "381d6edc",
"metadata": {},
"source": [
"Klasse `AusdruckAuswerter`:"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "3878a0fd",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"class AusdruckAuswerter:\n",
" def __init__(self):\n",
" self.op_stack = OperatorStack()\n",
" self.zahl_stack = OperandenStack()\n",
" \n",
" self.operatoren = \"+-*/\"\n",
" self.ziffern = \"0123456789.\"\n",
" self.zahl = \"\"\n",
" \n",
" def auswerten(self, ausdruck):\n",
" for zeichen in ausdruck:\n",
" if zeichen ==\"(\":\n",
" continue\n",
" elif zeichen in self.operatoren:\n",
" self.push_zahl()\n",
" self.op_stack.push(zeichen)\n",
" elif zeichen in self.ziffern:\n",
" self.zahl += zeichen\n",
" elif zeichen == \")\":\n",
" self.push_zahl()\n",
" self.berechne_operation_eval()\n",
" else:\n",
" print(\"Ungültiges Zeichen \"+ zeichen)\n",
" \n",
" return self.zahl_stack.pop()\n",
" \n",
" def push_zahl(self):\n",
" if len(self.zahl)>0:\n",
" self.zahl_stack.push(float(self.zahl))\n",
" self.zahl = \"\"\n",
" \n",
" def berechne_operation(self):\n",
" operator_str = self.op_stack.pop()\n",
" if operator_str == '+':\n",
" self.zahl_stack.push(self.zahl_stack.pop()+self.zahl_stack.pop())\n",
" elif operator_str == '-':\n",
" self.zahl_stack.push(-self.zahl_stack.pop()+self.zahl_stack.pop())\n",
" elif operator_str == '*':\n",
" self.zahl_stack.push(self.zahl_stack.pop()*self.zahl_stack.pop())\n",
" else:\n",
" self.zahl_stack.push((1/self.zahl_stack.pop())*self.zahl_stack.pop())\n",
" \n",
" def berechne_operation_eval(self):\n",
" operation = self.op_stack.pop() + str(self.zahl_stack.pop())\n",
" operation = str(self.zahl_stack.pop()) + operation\n",
" self.zahl_stack.push( eval(operation) ) "
]
},
{
"cell_type": "markdown",
"id": "065630f0",
"metadata": {},
"source": [
"Test der Ausdruck-Auswertung (der Ausdruck darf gerne variiert werden):"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "6f505456",
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-14.0\n",
"2.0\n"
]
}
],
"source": [
"testauswerter = AusdruckAuswerter()\n",
"print( testauswerter.auswerten(\"(1-(3*5))\") )\n",
"print( testauswerter.auswerten(\"(20/(2*5))\") )"
]
},
{
"cell_type": "markdown",
"id": "2b49b5cf",
"metadata": {},
"source": [
"### <font color='blue'>**Anregungen zum selbst Programmieren**</font>\n",
"\n",
"* Erstelle eine Datenstruktur zur Verwaltung einer Warteschlange für eine CNC-Maschine. Verwende dazu 3 Klassen: \n",
" \n",
" * die allgemeine `Datenstruktur`, die `Maschine`, und den `Auftrag`. \n",
" \n",
" * Eine `Maschine` soll eine Datenstruktur für die Warteschlange beinhalten und Methoden, um Aufträge der Schlange hinzuzufügen und den nächsten Auftrag zu bearbeiten. \n",
" Zudem soll es eine Methode geben, die dafür sorgt, dass alle verbleibenden Aufträge abgearbeitet werden. \n",
" Bei der Bearbeitung soll die Maschine die Informationen über den bearbeiteten Auftrag ausgeben. \n",
" \n",
" * Ein `Auftrag` hat folgende Daten:\n",
" * `Name`\n",
" * `Stückzahl`\n",
" * `Materialart`\n",
" * `Materialmenge pro Stück`\n",
" * `Dauer pro Stück`<br>\n",
" * Die `__init()__`- Methode soll prüfen, dass bei den Zahlenwerten nur positive Werte eingegeben werden.\n",
" \n",
" <br><br>\n",
"\n",
"* **Anspruchsvoll:** Erweitere das in dieser Übung behandelte Programm so, dass nicht zwingend alle Operationen umklammert werden müssen, und dass Punkt- vor Strichrechnung umgesetzt wird. Um das bestehende Programm weiterverwenden zu können, ist ein möglicher Ansatz, eine Methode zu erstellen, die die Zeichenkette anhand der Regeln \"Punkt- vor Strichrechnung\" und \"von links nach rechts\" mit Klammern ergänzt. "
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.7"
}
},
"nbformat": 4,
"nbformat_minor": 5
}