Differences

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

--- lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/04/28 14:01]
Ivo Blöchliger [Stack (Stapelspeicher)]
+++ lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/09 09:12] (current)
Ivo Blöchliger
@@ Line 68: / 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 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>
@@ Line 88: / Line 88: @@
 </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>