3. Matheparser

Matheparser

  • P

    Ich habe mir selbst schon einige Male die Aufgabe gestellt einen (fast) beliebigen mathematischen Ausdruck zu parsen und auch das Ergebnis zu berechnen. Ja - schon einige Versuche habe ich hinter mir. Aber bei jedem Versuch bin ich irgendwann gescheitert, weil immer einen Bug in meinem Programm hatte, den ich nie fand. Um dies dieses Mal zu verhindern habe ich mir vorgenommen bevor ich richtig anfange mir umfangreiche Gedanken zu machen. Hier nun meine theoretische Lösung:

    Aufgabe:
    Erstelle ein Programm, welches folgendes leiset:
    Es soll einen mathematischen Ausdruck berechnen können. Folgende Einschränkungen gelten für den Ausdruck:
    - keine Variablen - nur "Zahlen"
    - nur Ganzzahlen
    - nur folgende Operatoren: +, -, *, /
    - keine Klammern
    - das Ergebnis muss eine Ganzzahl sein

    Bsp:
    3+5*6-5 // richtig
    3(5+6) // falsch

    Und hier mein Gedankengang(grob):
    Grundlegendes: preferierte Operatoren sind * und /
    nicht preferierte Operatoren sind + und -

    Beispielausdruck: 3+2*6-3+6+4

    Die ersten 3 Werte und die ersten 2 Operatoren werden in jeweil eine List geladen.

    Nun werden die Operatoren überprüft:
    Folgende Fälle sind möglich:

    1. nicht preferierter Operator und nicht preferierter Operator
    2. nicht preferierter Operator und preferierter Operator
    3. preferierter Operator und preferierter Operator
    4. preferierter Operator und nicht preferierter Operator

    Für jeden Fall gibt es verschiedene Aktionen die durchgeführt werden müssen. Es existiert eine Variable names Temp in die ein Teil des Ergebnises gespeichert wird. Fast jeder Fall hat als Resultat einen Wert, den man mit sicherheit schonmal verwenden kann: 3+5*6 zum Beispiel. Hier wäre die 3 der Wert den man einfach zu Temp hinzuaddieren könnte. Desweiteren gibt es eine Variable Child. Manchmal ist es nötig ein Teil eines Drillings zu nehmen und zum Teil eines neuen Drillings zu machen siehe Fall 1.

    Ein Drilling besteht aus 3 Werten und 2 Operatoren.

    1. die ersten beiden Werte werden berechnet und das nächste Drilling beginnt mit dem aktuellen dritten Wert -> Bsp: 3+3+56+6
      Hier wird gerechnet: 3+3 = 6 - nächstes Drilling: 5      6+6
      Temp = 6
      Child = 5 // Child wird Teil des nächsten Drillings
    2. die letzten beiden Werte werden berechnet und der erste Wert wird Teil des neuen Drillings. Bsp: 2+6*6*2+2
      Hier wird gerechnet: 6*6 = 36 - nächstes Drilling: 36*2+2
      Temp = 2
      Child = 36
    3. es werden alle Werte berechnet. Das nächste Drilling beginnt mit dem Ergebnis der Berechnung. Beispiel: 1*2*3+4-2
      Es wird gerechnet: 1*2*3 = 7 -> nächstes Drilling 7+4-2
      Temp = 0
      Child = 7
    4. es werden die ersten beiden Werte berechnet. Das neue beginnt mit dem letzen Wert des aktuellen Ausdruckes. Bsp: 32-3+6-4
      Es wird berechnet: 3      2 = 6 - neues Drilling: -3+6-4
      Temp = 6
      Child = -3

    Und so kann man sich tot rechnen. Natürlich klappt das nur wenn die Anzahl der Operatoren stimmt. Aber das könnte man ja ganz einfach abfragen und habe ich hier nicht berücksichtigt.

    Naja wenn kein Operator mehr übrig ist muß man nurnoch die Temps der verschiedenen drillinge addieren und man hat das Ergebnis.

    Denke ich vielleicht zu kompliziert? Ja? Dann bitte einfachere Lösung aufzeigen.
    Habe ich irgendwo einen Denkfehler? Ja? Bitte aufzeigen!

    Danke schonmal!

    0
  • ?

    Hmm, wirklich ganzschön kompliziert dein Gedankengang.
    Wenn du sowieso keine Klammern erlaubst, würde ich es so machen:
    Du hast ja deinen Term als Zeichenkette vorliegen.
    z.B. "5+4*3-8/2"

    Als erstes gehst du von links nach rechts alle Operanden der höchsten Ordnung durch, hier also * und /. Triffst du auf eins dieser Zeichen, ersetzt du einfach den "Drilling" durch ein Zwischenergebnis. also hast jetzt im String zu stehen : "5+12-4" .
    Und im zweiten Durchlauf bildest du dann einfach die Summe.

    0
  • F

    Ich programmiere zur Zeit selsbt einen Funktionsplotter und mache das wie folgt.
    Ich machs einfach mit ner baumstruktur für den Term. Ich trenne den String an einem niederen Operator auf, trage ihn in das aktuelle baumelement ein,und rufe dir funktion selbst wieder auf, zuerst mit dem rechten teil des ausrucks, dann mit dem linken. So wird der Ausdruck nach und nach vollstänfig in den Baum eingetragen, dann reicht eine einfache rekursive Funktion aus, die das ganze dann ausrechnet.

    0
  • I

    Ich habe vor gut einem Jahr einen Parser für mathematische Ausdrücke in Java geschrieben, der so ziemlich alles verarbeiten kann (Klammern, * / - + und ^ sowie Funktionen wie sin,cos, sqrt usw). Ich habe dabei mit 2 Stacks und Infix->Postfix-Transformation gearbeitet. Falls dich interessiert, kann ich den Code ja mal zeigen.

    0
  • B

    Man kann sowas auch gut mit Rekursivem Abstieg lösen. Es lohnt sich, sich damit mal zu beschäftigen, dann muss man nicht an solchen ad-hoc-Lösungen wie oben verzweifeln ... und die Klammern sind a scho drin 😉

    0
  • E

    das grobe prinzip ist ganz einfach, ich glaub du machst alles nur
    unnoetig kopliziert:

    1. werte zahl aus (wandle string in zahl)
    2. werte alle * und / ausdruecke aus
    3. werte alle + und - ausdruecke aus

    das wars schon.
    du laeufst im string einfach von links nach rechts und gehst alle 3 punkte
    durch.
    auf meiner seite findest du auch einen parser: http://cchoernchen.de
    🙂

    0
  • K

    Bashar schrieb:

    Man kann sowas auch gut mit Rekursivem Abstieg lösen. Es lohnt sich, sich damit mal zu beschäftigen, dann muss man nicht an solchen ad-hoc-Lösungen wie oben verzweifeln ... und die Klammern sind a scho drin 😉

    das hab ich mal gemacht und muss sagen, es lässt sich schön programmieren und auch später berechnen. geschwindigkeit nicht die beste aber ok.

    0
  • I

    entelechie schrieb:

    das grobe prinzip ist ganz einfach, ich glaub du machst alles nur
    unnoetig kopliziert:

    1. werte zahl aus (wandle string in zahl)
    2. werte alle * und / ausdruecke aus
    3. werte alle + und - ausdruecke aus

    das wars schon.
    du laeufst im string einfach von links nach rechts und gehst alle 3 punkte
    durch.
    auf meiner seite findest du auch einen parser: http://cchoernchen.de
    🙂

    Tja, ganz so einfach ist es dann doch nicht. Dein Parser potenziert z.B. nicht richtig.

    0
  • E

    hm. warum potentiert er nicht richtig?
    kannst du mir da mal ein beispiel posten?

    0
  • I

    entelechie schrieb:

    hm. warum potentiert er nicht richtig?
    kannst du mir da mal ein beispiel posten?

    Du potenzierst linksassoziativ, das ist falsch. Die Exponentiation ist rechtsassoziativ. Bei dir wird z.B. der Ausdruck 432 so berrechnet (43)2, richtig wäre jedoch: 4(32)

    0
  • E

    hmm. ja, stimmt. da muss ich mal schaun. danke fuer den hinweis 🙂

    0
  • G

    interpreter, könntest du mir den Code von deinem Parser mal schicken? Danke! 🙂

    0
  • ?

    Auf meiner HP ist auch ein MatheParser zu finden.. Allerdings ist der noch relativ einfach gehalten.. Kennt also alle 4 Operationszeichen, und auch Potenzen via '^' (aber auch nur eine Potenz / Zahl, also nicht '222' oder so...), aber keine Klammern, etc... Man kann ihn aber auch mit einer Unbekannten 'x' verwenden... Bei Interesse einfach mal ausprobieren. Der Quelltext ist auch online, auch wenn er "dreckig" ist.. 😉
    MfG Aoeke

    0
  • I

    Griffin schrieb:

    interpreter, könntest du mir den Code von deinem Parser mal schicken? Danke! 🙂

    An welche Emailadresse?

    0
  • G

    Griffin007@gmx.net

    (ginge halt auhc über das Email senden übers Profil) 😉

    0
  • I

    Griffin schrieb:

    Griffin007@gmx.net

    (ginge halt auhc über das Email senden übers Profil) 😉

    Mail + Parser is raus 🙂

    0
  • R

    Wenn du es so machen willst, wie man es wirklich macht, besorg dir ein Buch über Compilerbau. Dann sind diese Dinge ganz einfach.

    0
Anmelden zum Antworten