Differences

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

--- lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/03/20 13:27]
Ivo Blöchliger [Tokenizing]
+++ lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/09 09:12] (current)
Ivo Blöchliger
@@ Line 50: / Line 50: @@
 print(a)         #  [7]
 print(a.pop())   #  7
-pritn(a)         #  []
+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.
@@ Line 61: / Line 61: @@
 ==== 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)
@@ Line 67: / Line 68: @@
   * 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>