Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/03/12 16:14] Ivo Blöchliger [Stack (Stapelspeicher)] |
lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/09 09:12] (current) Ivo Blöchliger |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Postfix Notation ====== | ====== Postfix Notation ====== | ||
Siehe auch https:// | Siehe auch https:// | ||
+ | |||
+ | ==== Hintergrund ==== | ||
+ | Für meine Kinder habe ich einen Wecker programmiert. Der läuft auf einem ESP32 und hat ein kleines Display, kann piepsen und soll dann einmal die Temperatur, Luftfeuchtigkeit etc. aufzeichnen. | ||
+ | |||
+ | Je nach Wochentag oder Ferien soll der Wecker um verschiedene Zeiten losgehen bzw. Informationen anzeigen. Die Frage ist, wie kommt die Information auf den Mikroprozessor? | ||
+ | |||
+ | Die Lösung war die " | ||
+ | |||
+ | Ziel war eine Programmiersprache, | ||
+ | |||
+ | Die Sprache sieht zur Zeit wie folgt aus: | ||
+ | <code txt> | ||
+ | 0 setmode "" | ||
+ | 0 {@wed setwday @6:20 settime} | ||
+ | @6:20 @19:50 >=< { 1 setmode } | ||
+ | @sat now = @sun now = or @10.4. @24.4. >=< or @7:00 now > and { 0 setmode } | ||
+ | @mon now = {" | ||
+ | @tue now = {" | ||
+ | @wed now = {" | ||
+ | @thu now = {" | ||
+ | @fri now = {" | ||
+ | @sat now = @sun now = or {" | ||
+ | @6:30 now > mode 1 = and {1 setalarm} | ||
+ | @6:20 now = alarm and {1 setbeep} | ||
+ | </ | ||
===== Arithmetische Ausdrücke mit Zahlen ===== | ===== Arithmetische Ausdrücke mit Zahlen ===== | ||
- | Ausdrücke wie '' | + | Ausdrücke wie '' |
Besonders interessant (und einfach zu programmieren) ist der Umgang mit Ausdrücken in **Postfix-Notation**, | Besonders interessant (und einfach zu programmieren) ist der Umgang mit Ausdrücken in **Postfix-Notation**, | ||
* infix: '' | * infix: '' | ||
* postifx: '' | * postifx: '' | ||
- | * prefix: '' | + | * (Der Vollständigkeit halber) |
[[lehrkraefte: | [[lehrkraefte: | ||
Line 25: | Line 50: | ||
print(a) | print(a) | ||
print(a.pop()) | print(a.pop()) | ||
- | pritn(a) # | + | print(a) # |
</ | </ | ||
- | Der Stack ist einen grundlegende Stpeicherstrukur, | + | Der Stack ist eine grundlegende Stpeicherstrukur, |
===== Auswerten eines Ausdrucks in postfix-Notation ===== | ===== Auswerten eines Ausdrucks in postfix-Notation ===== | ||
Line 36: | Line 61: | ||
==== Tokenizing ==== | ==== Tokenizing ==== | ||
+ | <WRAP todo> | ||
Kriegt man einen Ausdruck als Zeichenkette, | Kriegt man einen Ausdruck als Zeichenkette, | ||
* Input: eine String (Zeichenkette mit dem Ausdruck) | * Input: eine String (Zeichenkette mit dem Ausdruck) | ||
* Output: eine Liste mit Strings, die den einzelnen Tokens entsprechen. | * Output: eine Liste mit Strings, die den einzelnen Tokens entsprechen. | ||
Beispiel: | Beispiel: | ||
- | * Input ''" | + | * Input '' |
- | * Ausgabe '' | + | * Ausgabe '' |
+ | Die Idee ist, den Eingabe-String Zeichen um Zeichen durchzugehen und zu entscheiden, | ||
+ | </ | ||
+ | |||
+ | <hidden Lösungsvorschlag> | ||
+ | <code python tokenize.py> | ||
+ | def tokenize(s): | ||
+ | intoken = False | ||
+ | token = "" | ||
+ | tokens = [] | ||
+ | # Da fehlt noch was ;-) | ||
+ | |||
+ | |||
+ | return tokens | ||
+ | |||
+ | |||
+ | a = "123 24 5+2-*" | ||
+ | tks = tokenize(a) | ||
+ | print(tks) # Sollte hier [' | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | ====== Auswerten eines Infix-Ausdrucks ====== | ||
+ | Die Idee ist, das Auswerten eines Ausdrucks rekursiv zu Programmieren: | ||
+ | * Ein Ausdruck ist eine Summe | ||
+ | * Eine Summe ist ein Produkt, eventuell gefolgt von +/- und einem weiteren Produkt (etc.) | ||
+ | * Ein Produkt ist ein Atom, eventuell gefolgt von */ und einem weiteren Atom (etc.) | ||
+ | * Ein Atom ist eines von folgenden Dingen: | ||
+ | * Ein negatives Vorzeichen, gefolgt von einem Atom | ||
+ | * Eine öffnende Klammer, gefolgt von einem Ausdruck, gefolgt von einer schliessenden Klammer | ||
+ | * Eine Zahl | ||
+ | |||
+ | In Python kann das z.B. wie folgt umgesetzt werden: | ||
+ | <code python infix-parser.py> | ||
+ | import inspect | ||
+ | |||
+ | class Parser: | ||
+ | def __init__(self, | ||
+ | self.code = "" | ||
+ | self.debug = debug | ||
+ | self.position = "" | ||
+ | self.token = "" | ||
+ | self.error = "" | ||
+ | |||
+ | def show(self, msg="" | ||
+ | if self.debug: | ||
+ | caller = inspect.stack()[1][3] | ||
+ | print(self.code+" | ||
+ | print(" | ||
+ | |||
+ | |||
+ | def nextToken(self): | ||
+ | self.token = "" | ||
+ | # Leerschläge ignorieren | ||
+ | while self.position< | ||
+ | self.position+=1 | ||
+ | # Am Ende angekommen? | ||
+ | if self.position> | ||
+ | self.error = " | ||
+ | return | ||
+ | # Tokens mit einem Zeichen | ||
+ | if self.code[self.position] in " | ||
+ | self.token = self.code[self.position] | ||
+ | self.position+=1 | ||
+ | return | ||
+ | # Zahlen | ||
+ | while self.position< | ||
+ | self.token += self.code[self.position] | ||
+ | self.position+=1 | ||
+ | |||
+ | |||
+ | |||
+ | def atom(self): | ||
+ | self.show() | ||
+ | if self.token==" | ||
+ | self.nextToken() | ||
+ | a = self.ausdruck() | ||
+ | if self.token!=" | ||
+ | self.error = " | ||
+ | self.show(self.error) | ||
+ | return None | ||
+ | self.nextToken() | ||
+ | self.show(" | ||
+ | return a | ||
+ | if self.token==" | ||
+ | self.nextToken() | ||
+ | a = -self.atom() | ||
+ | self.show(" | ||
+ | return a | ||
+ | a = float(self.token) | ||
+ | self.nextToken() | ||
+ | self.show(" | ||
+ | return a | ||
+ | |||
+ | |||
+ | def produkt(self): | ||
+ | self.show() | ||
+ | a = self.atom() | ||
+ | while self.error=="" | ||
+ | op = self.token | ||
+ | self.nextToken() | ||
+ | b = self.atom() | ||
+ | if op==" | ||
+ | a*=b | ||
+ | else: | ||
+ | a/=b | ||
+ | self.show(" | ||
+ | return a | ||
+ | |||
+ | def summe(self): | ||
+ | self.show() | ||
+ | a = self.produkt() | ||
+ | self.show() | ||
+ | while self.error=="" | ||
+ | op = self.token | ||
+ | self.nextToken() | ||
+ | b = self.produkt() | ||
+ | if op==" | ||
+ | a+=b | ||
+ | else: | ||
+ | a-=b | ||
+ | self.show(" | ||
+ | return a | ||
+ | |||
+ | def ausdruck(self): | ||
+ | return self.summe() | ||
+ | |||
+ | def evaluate(self, | ||
+ | self.code = code | ||
+ | self.position = 0 | ||
+ | self.error = "" | ||
+ | self.nextToken() | ||
+ | return self.ausdruck() | ||
+ | |||
+ | |||
+ | |||
+ | p = Parser(False) | ||
+ | for test in [" | ||
+ | r = p.evaluate(test) | ||
+ | rr = eval(test) | ||
+ | if (r==rr): | ||
+ | print(test+" | ||
+ | else: | ||
+ | print(" | ||
+ | |||
+ | |||
+ | </ | ||