Differences

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

--- lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/04 14:52]
Ivo Blöchliger [Tokenizing]
+++ lehrkraefte:blc:informatik:ffprg1-2020:stack-rechner [2021/06/09 09:12] (current)
Ivo Blöchliger
@@ 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>