lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/03/12 08:57] – [Stack] Ivo Blöchligerlehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/09 07:12] (current) – Ivo Blöchliger
Line 1: Line 1:
 +====== Postfix Notation ======
 +Siehe auch https://de.wikipedia.org/wiki/Umgekehrte_polnische_Notation
 +
 +==== 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? Ein Möglichkeit bestünde darin, ICS-Dateien (Kalender-Format) zu analysieren. Das in C++ auf einem Mikroprozessor zu programmieren erschien mir aber zu aufwendig und das Speichermanagment heikel.
 +
 +Die Lösung war die "Erfindung" einer Programmiersprache, für die es sehr einfach ist, einen Interpreter zu schreiben. Diese Programmiersprache ist eine "Stacksprache" und stark von Postscript inspiriert.
 +
 +Ziel war eine Programmiersprache, die zum Auswerten keine Manipulation zusätzlicher Zeichenketten erfordert. Damit soll verhindert werden, dass mit der Zeit der Speicher voll wird.
 +
 +Die Sprache sieht zur Zeit wie folgt aus:
 +<code txt>
 +0 setmode "" setstatus 0 setalarm 0 setbeep
 +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 = {"   Montag|   Wald" setstatus}
 +@tue now = {"  Dienstag|   Tagi" setstatus}
 +@wed now = {"  Mittwoch|  Schwimmen" setstatus}
 +@thu now = {"  Donnerstag|   Klavier" setstatus}
 +@fri now = {"   Freitag|Turnen" setstatus}
 +@sat now = @sun now = or {"Wochenende" setstatus}
 +@6:30 now > mode 1 = and {1 setalarm}
 +@6:20 now = alarm and {1 setbeep}
 +</code>
 +
 +===== Arithmetische Ausdrücke mit Zahlen =====
 +Ausdrücke wie ''2+3*(5-4)'' sind für uns einfach auszurechnen. Ein Computerprogramm zu schreiben, das solche Ausdrücke korrekt ausrechnet, ist aber nicht trivial. Python (und auch fast alle anderen Programmiersprachen) können solche Ausdrücke selbstverständlich korrekt interpretieren und berechnen. Diese Notation wird **Infix-Notation** genannt, weil der **Operator zwischen** den Operanden liegt.
 +
 +Besonders interessant (und einfach zu programmieren) ist der Umgang mit Ausdrücken in **Postfix-Notation**, d.h. der Operator folgt auf die Operanden:
 +  * infix: ''2+3*(5-4)''
 +  * postifx: ''2 3 5 4 - * +'', d.h. Minus wirkt auf 5 und 4 und ''5 4 -'' wird durch ''1'' ersetzt. Dann steht noch ''2 3 1 * +''. Es wird ''3 1 *'' ausgerechnet und durch das Resultat 3 ersetzt. Es bleibt am Schluss noch ''2 3 +'', also 5.
 +  * (Der Vollständigkeit halber) prefix: ''add(mul(sub(5,4),3),2)'' (die Operatoren sind wie Funktionen).
 +
 +[[lehrkraefte:blc:informatik:ffprg1-2020:postfix-quiz|Postfix-Quiz]]
 +
 +===== Stack (Stapelspeicher) =====
 +Ein Stack ist eine Speicherstruktur, die genau zwei Operationen erlaubt:
 +  * Ein Element hinzufügen (push)
 +  * Das zuletz hinuzgefügte Element entfernen (pop)
 +In Python kann das z.B. mit einem Array (Liste) realisiert werden, wobei die Methoden ''append'' und ''pop'' verwendet werden können:
 +<code python>
 +a=[]
 +a.append(7)
 +a.append(4);
 +print(a)         #  [7,4]
 +print(a.pop())   #  4
 +print(a)         #  [7]
 +print(a.pop())   #  7
 +print(a)         #  []
 +</code>
 +Der Stack ist eine grundlegende Stpeicherstrukur, die auch direkt in Prozessoren schon umgesetzt ist. Damit werden z.B. lokale Variablen in Funktionen abgelegt (und je nach Architektur auch auf dem Stack übergeben). Insbesondere die Rücksprungadresse (wo im Code es nachher weiter geht) wird bei Funktionen auf den Stack abgelegt.
 +
 +===== Auswerten eines Ausdrucks in postfix-Notation =====
 +Das Auswerten ist extrem einfach und geht den Ausdruck von links nach rechts durch:
 +  * Wird eine Zahl gelesen, wird diese auf den Stack geschrieben
 +  * Wird eine Operation gelesen, werden der Operation entsprechend viele Zahlen vom Stack entfernt, entsprechend verrechnet und das Resultat wieder auf den Stack geschrieben.
 +Am Ende liegt das Resultat auf dem Stack.
 +
 +==== Tokenizing ====
 +<WRAP todo>
 +Kriegt man einen Ausdruck als Zeichenkette, muss diese erst in "Tokens", d.h. einzelne Elemente wie Zahlen und Operatoren zerlegt werden.
 +  * Input: eine String (Zeichenkette mit dem Ausdruck)
 +  * Output: eine Liste mit Strings, die den einzelnen Tokens entsprechen.
 +Beispiel:
 +  * Input ''<nowiki>"</nowiki>3 4 5+2 - *<nowiki>"</nowiki>''
 +  * Ausgabe ''[<nowiki>"</nowiki>3<nowiki>"</nowiki>, <nowiki>"</nowiki>4<nowiki>"</nowiki>, <nowiki>"</nowiki>5<nowiki>"</nowiki>, <nowiki>"</nowiki>+<nowiki>"</nowiki>, <nowiki>"</nowiki>-<nowiki>"</nowiki>, <nowiki>"</nowiki>*<nowiki>"</nowiki>]''
 +Die Idee ist, den Eingabe-String Zeichen um Zeichen durchzugehen und zu entscheiden, ob ein neuer Token beginnt, einer weiter geht oder aufhört. Die Information, ob die aktuelle Position gerade innberhalb oder ausserhalb eines Tokens ist wird in einer Variablen ''intoken'' gespeichert (''True'' oder ''False'').
 +</WRAP>
 +
 +<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 ['123', '24', '5', '+', '2', '-', '*'] liefern
 +</code>
 +</hidden>
 +
 +====== 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, debug=False):
 +        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+"\n"+" "*self.position+"^")
 +            print("  "+msg+" from "+caller+"   token="+self.token+"    error="+self.error)
 +        
 +        
 +    def nextToken(self):
 +        self.token = ""
 +        # Leerschläge ignorieren
 +        while self.position<len(self.code) and self.code[self.position]==" ":
 +            self.position+=1
 +        # Am Ende angekommen?
 +        if self.position>=len(self.code):
 +            self.error = "done"
 +            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<len(self.code) and self.code[self.position] in ".0123456789":
 +            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 = "Fehlende schliessende Klammer:\n"+self.code+"\n"+" "*self.position+"^"
 +                self.show(self.error)
 +                return None
 +            self.nextToken()
 +            self.show("a=%d" % a)
 +            return a
 +        if self.token=="-":
 +            self.nextToken()
 +            a = -self.atom()
 +            self.show("a=%d" % a)
 +            return a
 +        a = float(self.token)
 +        self.nextToken()
 +        self.show("a=%d" % a)
 +        return a
 +        
 +        
 +    def produkt(self):
 +        self.show()
 +        a = self.atom()
 +        while self.error=="" and self.token in "*/":            
 +            op = self.token
 +            self.nextToken()
 +            b = self.atom()
 +            if op=="*":
 +                a*=b
 +            else:
 +                a/=b
 +        self.show("a=%d" % a)
 +        return a
 +        
 +    def summe(self):
 +        self.show()
 +        a = self.produkt()
 +        self.show()
 +        while self.error=="" and self.token in "+-":
 +            op = self.token
 +            self.nextToken()
 +            b = self.produkt()
 +            if op=="+":
 +                a+=b
 +            else:
 +                a-=b
 +        self.show("a=%d" % a)
 +        return a
 +        
 +    def ausdruck(self):
 +        return self.summe()
 +
 +    def evaluate(self, code):
 +        self.code = code
 +        self.position = 0
 +        self.error = ""
 +        self.nextToken()
 +        return self.ausdruck()
 +        
 +        
 +    
 +p = Parser(False)  # True für detaillierte Ausgabe
 +for test in ["1+2", "6*7", "-8", "4*2.5+1", "1+-3.5*2", "(1+3)*2", "-(1+3)*-2", "--2", "((2+6/2)+1)*(3+16/4)"]:
 +    r = p.evaluate(test)
 +    rr = eval(test)   # Python soll den Ausdruck auswerten
 +    if (r==rr):
 +        print(test+" -> %f" % r)
 +    else:
 +        print("FAIL on "+test)
 +    
 +
 +</code>
 +