Entwickler-Ecke :: Thema anzeigen - Mathematischen Parser schreiben

Benutzername - Fr 05.08.05 22:24
Titel: Mathematischen Parser schreiben

Hi Leute^^

Mich überkam mal wieder die Lust, was neues zu programmieren, das auch nicht zu einfach ist.
Und so bin ich drauf gekommen, mir nen Mathe-Parser zu basteln.

Ich hab auch schon gegoogelt und bin auf verschiedene Anstöße gekommen:
Iterative Parser, rekursive Parser, UPN-Parser, Parser mit Stack usw.
Hab mir auch schon diverse PDFs und andere Seite angeschaut, abe rda war irgendwie nix weiter interessantes dabei, das nicht irgendwie Parser-Generatoren o.Ä. verwendet hätte :?

Aber jetzt meine Frage: Wie würdet ihr das angehen?
Ich hab sowas noch nie gemacht, von daher bin ich praktisch auf eure Hilfe angewiesen ;)

Mir kommts erstmal überhaupt nicht auf Geschwindigkeit an, sondern darauf, dass er erstmal das wesentliche beherrscht: +-*/ (inklusive Punkt-vor-Strich-Regeln) und Klammersetzung, nach dem Motto "FIRST make it work, THEN make it fast" ;)

Ich hoff mal, ihr könnt mir bei dem Thema helfen :)

AXMD - Fr 05.08.05 22:26

Erste Anlaufstelle: die Suche in: Delphi-Forum, Delphi-Library

FORENSUCHE. Einfach mal nach Suche in: Delphi-Forum, Delphi-Library

PARSER suchen - gibt es einige hier im Forum.

AXMD

Benutzername - Fr 05.08.05 22:28

Die Forensuche hab ich schon oft verwendet, hat auch oftmals geholfen bei diversen anderen Problemen.
Allerdings fand ich eigentlich nur fertige Units für Parser. :?
Ich wollte aber mal wissen, wie man/wie ihr sowas angeht/angehen würdet ;)

LigH - Fr 05.08.05 22:52

Wohl eher gar nicht; schon die String-Zerlegung zu programmieren, wäre mir persönlich viel zu aufwändig! 8)

Das wichtigste ist, die Struktur zu erkennen - wo sind Operatoren, wo Variablen/Zahlen. Dann die Struktur nach Operatoren-Wertigkeit sortiert in einem Baum einbauen. Und dann (wenn sich der Baum fehlerfrei aufbauen lies) den Baum lösen.

Das alles selber zu machen, wäre "Eulen nach Athen tragen", oder "das Rad neu erfinden", oder ... - na, du verstehst: Wozu sich wochenlang den Kopf zerbrechen, das andere über Monate hinweg schon perfektioniert haben?

In den JEDI-Bibliotheken müsste bereits was enthalten sein:

http://sourceforge.net/projects/jcl + http://sourceforge.net/projects/jvcl

Benutzername - Fr 05.08.05 23:03

Öhm, Danke LigH :)
Aber das war eine der Antworten, die ich eher nicht hören wollte :mrgreen: ;)

Ich weiß, dass es vermutlich viel Arbeit sein wird ;)
Ich brauch den Parser ja auch nicht für ein Projekt, ich will das einfach nur ma gemacht haben ;)
Stichwort Lerneffekt ;)

Trotzdem danke, wenn ich mal nen Schnellen brauch, dann schau ich in die JCL :)

delfiphan - Sa 06.08.05 02:48

Das hab ich mir eines Tages auch gesagt und dabei ist die Unit tyParser.pas [http://www.tyberis.com/download/tyParser.pas] rausgekommen. :)

Eine Erklärung zur verwendeten Methode findest du hier [http://www.delphi-forum.de/viewtopic.php?p=219936#219936].

Jedoch basiert die neuste Version von tyParser auf anderen (aber ähnlichen) Prinzipien.
Die Unit tyParser enthält übrigens auch einen Compiler, welcher einen Stringausdruck in eine direkt ausführbare Funktion umwandelt.

Das ganze wurde gänzlich von Hand geschrieben.

PS: Im DF hat es übrigens auch noch eine Handvoll andere Parsers. Die kannst du dir ja auch mal anschauen :)

alcaeus - Sa 06.08.05 03:20

So, mein Tipp: regular Expressions. Ein parsen mit Hilfe von Pos(), Copy, Delete() waere hier wohl glatter Selbstmord. Allerdings habe ich im Moment keine RegExp-Unit fuer Delphi (Infos gibts hier [http://www.regular-expressions.info/delphi.html]) installiert, also gibt es nur Pseudo- oder php-Code. Da ich dir keinen fertigen Code geben will (:P) gibts Pseudo-Code. Erstens die Grundlagen:

Der Parser akzeptiert Variablen, die auch mehr als ein Zeichen lang sein koennen. Die Variablen duerfen aber ausschliesslich aus Kleinbuchstaben (a-z) bestehen.
Als Operationszeichen kennt der Parser die Grundrechenarten (+, -, *, /) sowie die Potenz (^)
Geklammerte Ausdruecke sind erlaubt, solange die Klammern geschlossen werden ;)
Ausser diesen Zeichen duerfen natuerlich noch Zahlen sowie Spaces zur Formatierung verwendet werden.
Sollte was anderes auftreten, bricht der Parser einfach ab.

Hier noch die Referenz zu den einzelnen php-Funktionen die ich verwendet habe, ich denke dass es diese auch in den RegExp-Libs fuer Delphi gibt: preg_match_all() [http://de.php.net/preg_match_all], preg_match() [http://de.php.net/preg_match()], preg_replace() [http://de.php.net/preg_replace] und preg_split() [http://de.php.net/preg_split].

Bevor es losgeht, noch eine Kleinigkeit: ich erklaere hier nicht lange die Feinheiten der Regular Expressions. Diese duerft ihr selbst rausfinden :P ;)

So, der Parser besteht aus drei Funktionen. Die beiden ersten sind relativ einfach:

parse_expression() erwartet als Parameter den String mit der Expression, sowie ein Array mit den Variablen-Deklarationen. In php geht dies ja z.B. so: $ar['foo'] = 3. Da dies in Delphi nicht geht, musst du dir anders helfen, z.B. mit der Komponente fuer String-Indizierte Arrays [http://www.delphipraxis.net/topic57060.html]. Was macht die Funktion? Einfach: mit einer Regular Expression werden alle Zeichen-Kombinationen rausgesucht, und durch den entsprechenden Array-Wert ersetzt. Die Regexp sieht dann so aus: #\b([a-z]+)\b#is. Diese Regexp findet eine mind. 1 Zeichen lange Folge der Buchstaben a-z, die von Wortgrenzen umgeben sind. Das wird in preg_match_all reingefuettert, zusammen mit der Expression. Dort gibts als Rueckgabewert ja die Anzahl Matches, also ersetzen wir alle gefundenen Elemente mit deren Wert. Ist kein Wert vorhanden, so nehmen wir einfach 0. In anderen Worten (php):

Quelltext

1:
2:
3:
4:
5:
6:

$varcount = preg_match_all('#\b([a-z]+)\b#is', $expr, $matches, PREG_SET_ORDER);
for ($i = 0; $i < $varcount; $i++)
{
  $varname = $matches[$i][1];
  $expr = preg_replace('#\b'. $varname .'\b#is', (isset($vars[$varname]) ? $vars[$varname] : 0), $expr);
}

Die Funktion gibt einen Integer zurueck, naemlich den Rueckgabewert von do_parsing(), welche spaeter noch deklariert wird.

eval_expression(): Diese Funktion erwartet ein array mit 3 Elementen, wobei das erste und letzte Element eine Zahl, das zweite Element ein beliebiges Operationszeichen sein koennen. Zuerst werden diese Bedingungen geprueft. Der erste Teil kann in Delphi wahrs. entfallen, dieser ist nur da, weil php nicht typesafe ist. Nach der Pruefung ob es sich ueberhaupt um ein Array der Laenge 3 handelt, testen wir die einzelnen Teile, dies geschieht mit preg_match. Element 1 und 3 muessen Zahlen sein (Regexp: #\d+(\.\d+)?#), Element 2 eines der vorher festgelegten Op-Zeichen (RegExp: #(\+|\-|\*|\/|\^)#). Sobald das erledigt ist, fuehren wir einfach die gewuenschte Operation aus, welche anhand von Element 2 bestimmt werden kann. Das Ergebnis geben wir zurueck. Und da dies ein einfacher Code ist (case-of), gibts hier keinen Codeschnipsel :P

do_parsing() schlussendlich ist das, worauf es ankommt. Diese Funktion erwartet nur einen String mit dem Rechenausdruck, in dem die Variablen bereits durch Zahlen ersetzt wurden. Jetzt gehts richtig los: zuerst werden Klammern aufgeloest. Also wiedermal preg_match_all, diesmal mit dieser regexp: #$(.*)$#is. Anschliessend fuettern wir unseren ersten Match (also das was in der Klammer steht) wieder in do_parsing, und ersetzen den Ausdruck inkl. Klammern mit dem Rueckgabewert von do_parsing. Hier der Code:

Quelltext

1:
2:
3:
4:
5:

$matchcount = preg_match_all('#\((.*)\)#is', $expr, $matches, PREG_SET_ORDER);
for ($i = 0; $i < $matchcount; $i++)
{
  $expr = str_replace($matches[$i][0], do_parsing($matches[$i][1]), $expr);
}

Aus diesem Rechenausdruck: 2+4*(52-4) wird also 2+4*48. Wie es dazu kommt, sehen wir gleich.

Jetzt versehen wir jedes Einzelelement des Rechenausdrucks (also Op-Zeichen sowie Zahlen [nicht Ziffern]) mit einem Leerzeichen, vorne und hinten. Warum sehn wir gleich. Die Regexp sieht hier ein bisschen verwirrend aus, ist sie aber nicht: #(\+|\-|\*|\/|\^|\d+(\.\d+)?)#is. Hier der entsprechende php-Code:

Quelltext

1:	$expr = preg_replace('#(\+\|\-\|\*\|\/\|\^\|\d+(\.\d+)?)#is', ' \\1 ', $expr);

Anschliessend ersetzen wir alle mehrfach hintereinander vorkommenden Leerzeichen mit einem einzigen:

Quelltext

1:	$expr = preg_replace('# {2,}#', ' ', trim($expr));

Das {2,} bedeutet in diesem Fall "mind. 2 mal". Das trim() schneidet dabei alle "aussenstehenden" Leerzeichen ab.
Nun sieht unser Rechenausdruck von vorhin schon so aus (der Klammmernausdruck wird der Einfachheit halber direkt ausgewertet, aber nur in der Erklaerung ;)): 2 + 4 * 48

Jetzt kommt der richtig lustige Teil:
Wir spalten unseren Rechenausdruck in einzelne Teile, und zwar immer am Leerzeichen. Dieses teilt ja jeden einzelnen Ausdruck. Dazu wird preg_split() mit folgender regexp verwendet: # #. Die einzelnen Teile landen alle in einem Array, welches also folgende Zeichen enthaelt:

Quelltext

1:
2:
3:
4:
5:

Anschliessend prueffen wir folgende Bedingungen:

Das erste und letzte Zeichen muessen Integers sein. Das Pruefen auf Integer mittels preg hatten wir ja schon ;)
Die Anzahl der Elemente ist ungerade. Der Grund ist einfach: jedes Rechenzeichen muss von 2 Zahlen umgeben sein, sonst haben wir einen ungueltigen Ausdruck.

Trifft eine der beiden Bedingungen nicht zu, gehts raus. Anschliessend kommt ein kleiner "Speedhack" (und Bugfix *g*): wenn nur ein Element im Array ist, geben wir diesen Wert gleich zurueck. Sonst wuerde diese Rechnung einen Fehler ergeben, da im naechsten Schritt mind. 3 Elemente da sein muessen: 2+(4)

Anschliessend initialisieren wir unsere Rueckgabevariable (ich nenne sie Value) mit dem ersten Array-Element, warum wird gleich rauskommen. Im naechsten Schritt laufen wir mit einer Schleife, welche bei 1 beginnt, natuerlich innerhalb der Array-Grenzen bleiben muss, und in jedem Schritt um 2 erhoeht wird, ueber das Array mit den einzelnen Elementen. So sprechen wir Elemente mit ungeradem Index an, was in unserem Fall die Op-Zeichen sind. Nun pruefen wir auf die folgenden Bediungungen:

Das aktuelle Rechenzeichen ist *, / oder ^
Das aktuelle Rechenzeichen ist + oder -, aber es gibt kein weiteres Rechenzeichen mehr
Das aktuelle Rechenzeichen ist + oder -, ebenso wie das folgende

In diesem Fall weisen wir value den Rueckgabewert von eval_expression zu, welche mit folgenden Parametern aufgerufen wird: value, dem aktuellen Rechenzeichen, und der naechsten Zahl, also dem naechsten Array-Element.

Die Faelle die ich oben geprueft habe, sind nur gueltig, wenn die Punkt-vor-Strich-Regel nicht gilt. Falls wir aber ein + oder / haben, und das naechste Rechenzeichen ein *, / oder ^ ist, so wird es etwas komplizierter. In diesem Fall werten wir erstmal den naechsten Ausdruck aus. Eine temp-Variable bekommt also den Wert von eval_expression() mit den folgenden Parametern zugewiesen: Die naechste Zahl, das naechste Op-Zeichen, die uebernaechste Zahl. Anschliessend weisen wir value das Ergebnis von eval_expression mit folgenden Parametern zu: value, das aktuelle Op-Zeichen, und dem Wert unserer Temp-Variable. Anschliessend inkrementieren wir die Laufvariable um 2 (zusaetzlich zu den 2, die in jedem Durchlauf addiert werden, damit die naechste Operation, welche ja soeben bereits durchgefuehrt wurde, uebersprungen wird. Tja...und sobald die Schleife zu Ende ist, gibt die Funktion den Wert von value zurueck, und gut is.

So, und nachdem das jetzt viel Theorie war, gibts erstmal Praxis. Gegeben sei folgender Ausdruck: 2+ a*(b^4 -2)- 6/3
a ist in dem Fall 5, b ist 2.
Man beachte die mehrfachen Leerzeichen, die ich reingebaut habe.

Aufruf von parse_expression('2+ a*(b^4 -2)- 6/3', vararray);
Jetzt werden alle Variablen ersetzt, der Ausdruck sieht also so aus: 2+ 5*(2^4 -2)- 6/3
Jetzt sind wir in do_parsing('2+ 5*(2^4 -2)- 6/3'). Wir pruefen auf Klammern und finden (2^4 -2)
- Rekursiver Aufruf von do_parsing('2^4 -2') (Klammern werden nicht mituebergeben).
- Wir finden keine Klammern, weiter im Programm.
- Wir fuegen vor und hinter jedem Element ein Leerzeichen ein, der Ausdruck sieht nun so aus: 2 ^ 4 - 2
- Mehrfache Leerzeichen werden rausgeworfen: 2 ^ 4 - 2
- Der String wird gespalten, wir haben ein Array mit folgenden Elementen:
  Quelltext
  1:
  2:
  3:
  4:
  5:
  
  2
  ^
  4
  -
  2
- Unsere Pruefungen passen, das Array ist laenger als 1 Element, also parsen wir das Ding durch. Unsere Laufvariable ist i, in matches stehn die einzelnen Teile drin.
- Value wird auf 2 gesetzt.
  - i ist 1, das Zeichen an der Stelle ist ^, also werten wir den Ausdruck aus: eval_expression(2, ^, 4). In Value steht jetzt 16.
  - Das naechste Zeichen ist -. Nachdem es nachher kein Op-Zeichen mehr gibt, koennen wir wiederum gleich auswerten: eval_expression(16, -, 2). Value ist nun 14, die Schleife ist zuende.
- Wir geben den Wert von Value zurueck: 14.
Der Rueckgabewert vom Klammernausdruck wird statt dem Ausdruck selbst eingesetzt, also sieht der gesamte Ausdruck jezt so aus: 2+ 5*14- 6/3
Das Spiel geht weiter, diesmal ein kleines bisschen Schneller: nach der Leerzeichenspielerei sieht der Ausdruck so aus: 2 + 5 * 14 - 6 / 3

Wieder splitten wir, und erhalten folgendes array:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

2
+
5
*
14
-
6
/
3

Also, pruefen...ok. Array ist laenger als 1 Element, also Laufvariable auf 1, value auf das erste Element (2).
- Wir finden ein +, stellen aber fest, dass das folgende Zeichen ein * ist. Also werten wir erstmal den Ausdruck aus: eval_expression(5, *, 14). Den Rueckgabewert (70) schreiben wir in tempvalue.
- Anschliessend koennen wir den folgenden Ausdruck ausfuehren: eval_expression(2, +, 70). Das Ergebnis (72) kommt in Value, und wir inkrementieren i um 2.
- Value ist nun 72, i ist 5 (Standard-Inkrementierung plus die 2 von vorhin). Was finden wir? Ein -, aber wieder gilt Punkt vor Strich. Also wie vorhin erstmal eval_expression(6, /, 3) ausfuehren, und das Ergebnis (2) dann weiterverwenden: eval_expression(72, -, 2). Das Ergebnis (70) kommt in value, und wieder inkrementieren wir i um 2.
- i ist nun groesser als die Anzahl Elemente im Array, also brechen wir ab.
Wir geben den Wert von Value (70) zurueck.
parse_expression() bekommt den Wert, gibt ihn zurueck, und fertig ist die Rechnung: 2+ a*(b^4 -2)-6/3 = 70

So, ich hab dir (Benutzername) doch gesagt, vor 3 gibts kein Ergebnis. Allerdings ist eine gute Stunde fuers Tippen des Beitrags draufgegangen. Deshalb: danke fuers Lesen. Ich hoffe ihr versteht meine Ausfuehrungen wenigstens ein bisschen, und bei Fragen: nur her damit. Und wer einen Blick auf den Code (php) werfen will, kann sich per PN an mich wenden, und vielleicht habe ich morgen (oder eher heute) Lust, das ganze noch in Delphi zu schreiben ;)

Greetz
alcaeus

Edit: Regexps fuer Reelle Zahlen angepasst

alcaeus - Sa 06.08.05 12:02

So, und nachdem dieses lange Posting so schoen war, gibts heute Abend noch eins. Ich hab soeben das Delphi-Beispiel fertiggestellt, hab aber im Moment keine Lust, es zu erklaeren. Das kommt heute um 2 Uhr nachts :lol:

Greetz
alcaeus

Benutzername - Sa 06.08.05 12:05

:lol:
Auf jeden Fall schonmal Danke ;)
Aber heut nacht um 2 is schon seit etwa 10 Stunden vorbei :P

jakobwenzel - Sa 06.08.05 12:12

In einem alten Turbo-Pascal Buch (so alt ist es auch noch nicht) haben sie einen Parser so programmiert, das die Funktion im Hauptprogramm eingegeben wird, die dann in einen Quelltext integriert wird, der kompiliert wird. Dieser überschreibt eine Dummy-Methode im Hauptprogramm. Nun kannn das Hauptprogramm die eingegebene Funktion nutzen, als hätte sie schon beim kompilieren im Quelltext gestanden.

P.S.:Wozu einen Mathe-Parser programmieren, wenn man schon einen im Kompiler eingebauten hat?

P.P.S.: eventuell geht das mit dem ersetzen der Dummy-Funktion nicht mehr unter Delphi. Dann müsste man die Ausgabe des Ergebnisses im dynamisch generierten Programm vornehemen.

AXMD - Sa 06.08.05 12:34

jakobwenzel hat folgendes geschrieben:

Mich würde interessieren, wie der Quelltext dazu aussieht. Könntest du den uU mal posten?

AXMD

jakobwenzel - Sa 06.08.05 13:32

Die .bgi und .chr Dateien sind für den Grafikmodus. Funktion.exe/.pas ist das Hauptprogramm, hilfprg.exe/.pas das Hilfsprogramm. Das Programm braucht den Borland Pascal-Compiler TPC.exe im gleichen Verzeichnis. Da ich nicht weiß ob das Programm inzwischen Freeware ist, habe ich es weggelassen. Das Programm hat den Runtime-Error 200 Bug auf PC mit >150 MHZ Prozesor. (Hat ja inzwischen fast jeder so einen) Deshalb braucht man das Programm "PC-Bremse" (http://www.lrz-muenchen.de/~leoklein/downloads.html, 3. Programm von oben) benutzen. Ich musste bei meinem Rechner auf 75% gehen (1.5 GHZ).

jakobwenzel - Sa 06.08.05 13:34

Mist, Datei vergessen... Hier ist sie... :oops:

Moderiert von raziel: 32 mal :oops: entfernt.

retnyg - Sa 06.08.05 13:40

jakobwenzel hat folgendes geschrieben:

Das Programm hat den Runtime-Error 200 Bug auf PC mit >150 MHZ Prozesor. (Hat ja inzwischen fast jeder so einen) Deshalb braucht man das Programm "PC-Bremse" (http://www.lrz-muenchen.de/~leoklein/downloads.html, 3. Programm von oben) benutzen. Ich musste bei meinem Rechner auf 75% gehen (1.5 GHZ).

gibt auch einen patch für kompilierte programme: Suche bei Google

CTBPPAT, ausserdem ein update für die crt.tpu, damit neue progs den fehler nicht mehr haben

jakobwenzel - Sa 06.08.05 13:59

Ich glaube, so einen Patch habe ich schon drauf, das Programm habe ich dann wohl auf meinem alten PC (150 MHZ) kompiliert. :lol:

retnyg - Sa 06.08.05 14:02

jakobwenzel hat folgendes geschrieben:

Ich glaube, so einen Patch habe ich schon drauf, das Programm habe ich dann wohl auf meinem alten PC (150 MHZ) kompiliert. :lol:

der patch ctbppat patcht fertigt kompilierte programme. dadurch funktionieren diese auf jedem system einwandfrei.
der fix patcht gleich die verantwortlichen dateien in der TP installation, so dass der fehler in neu kompilierten .exe'n gar nicht drin ist.

jakobwenzel - Sa 06.08.05 14:20

Ich meinte das Update für die crt.tpu

Benutzername - Sa 06.08.05 15:10

Ich habs mal jetzt nicht runtergeladen, aber ich hab auch schonmal Überlegungen angestellt, dass man kompilietren Code "einfach" austauscht.
Aber das scheint mir nicht sehr sauber zu sein :?

jakobwenzel - Sa 06.08.05 15:25

Das Hilfsprogramm kopiert den Maschinencode der Funktion in einen der "unteren" Speicherbereiche, die, zumindest unter DOS (bzw. "Das 16-Bit Teilsystem" unter XP) jedes Programm auslesen kann. Das Hauptprogramm überschreibt seine Dummy-Funktion nur im Speicher mit dem neuen Code, der dann anstatt der Dummy-Funktion aufgerufen wird. Die Dummy-Funktion muss halt länger als die richtige Funktion sein, sonst werden andere Funktionen überschrieben.

Wahrscheinlich funktioniert ein Teil dessen, was unter DOS so wunderbar geht, unter Windows mit Delphi nicht mehr.

delfiphan - So 07.08.05 13:00

Der Vorschlag mit Regular Expressions ist nett, würde ich persönlich aber nicht empfehlen.

Normalerweise besteht ein Parser aus einer Komponente, die den Text in "Atome" (oder Tokens) zerlegt (Lexer) und einer Komponente, die die Tokens dann auswertet. (In meinem Parser ist das ganze zwar nicht so klar getrennt aber egal)

Der "Suchen und Ersetzen"-Ansatz ist meiner Meinung nach langsam, kompliziert (deswegen fehleranfällig) und nicht universell einsetzbar (man denke an Fälle wie: "1 - (-1) + 2e-1" (wobei 2e-1 = 0.2)).
Ausserdem sollte man meiner Meinung nach nicht am Ausdruck selbst arbeiten. Der Parser sollte sich den String anschauen und den genau so interpretieren, wie er da steht. Im Idealfall sollte sich der Parser einen Baum generieren, welcher er dann noch optimieren kann. Aus diesem Baum ist es dann relativ einfach möglich, einen Bytecode oder direkt Maschinencode zu generieren. Das beschleunigt die Auswertung ganz entscheidend.

Last but not least: Man sollte sich bei Parsern zuerst eine Grammatik definieren (z.B. in EBNF). Spätestens wenn du kompliziertere Sachen drin hast sind alle anderen Ansätze unmöglich zu implementieren. Mit EBNF kannst du ganze Programmiersprachen (Delphi, Java, etc.) definieren. Mit Regular Expressions kommst du da nicht sehr weit... Ausserdem würde ich bezweifeln, dass du es mit RegExp schaffst, eine halbwegs sinnvolle Fehlermeldung zu generieren, wenn was schief läuft.

Benutzername - So 07.08.05 16:07

Ja, so ganz begeistert war ich von den Regular Expressions auch nicht, aber wenns funktioniert... ;)
Du sagst, man sollte das mit nem Baum lösen: Gibts da schon ne fertige Klasse in Delphi, mit der man daslösen könnte?

Und noch ne andere Frage: Angenommen ich hab jetzt einfach nen Term wie 3+6*5*7. Wie mach ich dem Parser klar, dass er doch bitte Punkt-vorStrich beachten soll? Such ich da "einfach" nach dem ersten vorkommenden * oder / -Zeichen und schau dann, welche Zahlen drumrum stehen?

Vermute ich richtig, dass ich zuerst alle Klammern von innen nach außen ausrechnen muss?
Weil dann mach ich mich zuerst mal an ne Funktion, die mir den Term in der innersten Klammer raussucht :)

LigH - So 07.08.05 21:44

Es wird sicher darauf ankommen, welche Operanden du überhaupt zuläßt (unäre, binäre, Funktionen, Klammern, evtl. noch logische?) - "Punkt vor Strich" ist ja nur eine Ebene, ich kenne Parser mit mehr als einem halben Dutzend Operanden-Hierarchie-Ebenen.

Und da - wenn du einen Zweig des Baumes als Operand ansiehst, und ein Blatt als Operator - jeder Operanden-Zweig sowohl unterschiedlich viele Verzweigungen haben kann, als auch unterschiedliche Inhalte (entweder ein Operanden-Blatt, oder einen kompletten neuen Operatoren-Zweig), wäre mit Sicherheit eine eigene Klassenheirarchie sinnvoll, so etwas dürfte man kaum fertig vorfinden.

Benutzername - So 07.08.05 23:28

Hm, klingt recht kompliziert :? *g*
Ich werds mir bei Gelegenheit nochmal durch den Kopf gehen lassen^^

Aber ich hab nun einfach mal so drauflos geschrieben, und hab meinen Parser nun soweit, dass er * und / -Rechnungen richtig ausrechnet :)
Jetz fehlen "nurnoch" + und - Rechnungen und vielleicht Potenzen.
Und das unäre Minus muss ich noch einbauen, dass passt die Sache *g*

delfiphan - Mo 08.08.05 04:28

Benutzername hat folgendes geschrieben:

Vermute ich richtig, dass ich zuerst alle Klammern von innen nach außen ausrechnen muss?

Es gibt Parsers, die arbeiten von aussen nach innen; es gibt welche, die arbeiten von innen nach aussen. Du kannst einen Parser (iirc) sogar mit einer Finite State Maschine programmieren (à la Windows-Calculator). Es gibt bestimmt mind. 5 komplett verschiedene Ansätze, wie man das programmieren kann.
Ich bevorzuge meine rekursive Variante (keine Finite State Maschine), die den String mehr oder weniger einmal von links nach rechts passiert. Die Rekursion ist dabei so gemacht, dass man direkt die richtige Reihenfolge der Operationen für die Umwandlung zu Maschinencode erhält.

Beispiel:
1+(2+3)*(4+5)

Der Parser bringt das ganze in folgende Reihenfolge:
1 2 3 + 4 5 + * +

Zum Auswerten geht man diese Liste von links nach rechts durch. Man muss dabei lediglich zwei Regeln beachten:
- Eine Zahl wird auf den Stack gepusht.
- Eine binäre Operationen "poppt" zwei Zahlen aus dem Stack, führt die Operation durch und pusht anschliessend wieder das Ergebnis.

Beispiel:
Zeitschritt  Token   Stack        Rechnung
0                    []
1            1       [1]
2            2       [1,2]
3            3       [1,2,3]
4            +       [1]          2+3
5                    [1,5]
6            4       [1,5,4]
7            5       [1,5,4,5]
8            +       [1,5]        4+5
9                    [1,5,9]
10           *       [1]          5*9
11                   [1,45]
12           +       []           1+45
13                   [46]

(46 ist das Ergebnis)

Mein Parser beschäftigt sich also vereinfacht gesprochen mit der Aufgabenstellung
1+(2+3)*(4+5)
in
1 2 3 + 4 5 + * +
umzuwandeln.

Benutzername - Mo 08.08.05 16:15

Ah, Danke für die Erklärung, Hintergrundwissen ist immer gut :)

Aber ich hab das jetz ohne die Postfix-Notation gemacht (so heißt die doch (bzw. UPN) ? *gg*) und auch ohne Stack.
Alles was jetzt noch fehlt, ist die Rechnung mit Potenzen und das mit den negativen Zahlen.
Wobei Potenzen schnell einzubauen sind *g*

Ich parse jetzt einfach die Klammern von innen nach außen, bis ich beim "Grundterm" angekommen bin, und löse das dann so auf, klappt auch wunderbar. Nicht-Ganzzahlen kann er auch schon, war auch kein Problem :)

Ich meld mich wieder, wenns Neuigkeiten und/oder Fragen gibt :stupid:

delfiphan - Mo 08.08.05 17:12

Benutzername hat folgendes geschrieben:

Aber ich hab das jetz ohne die Postfix-Notation gemacht (so heißt die doch (bzw. UPN) ? *gg*) und auch ohne Stack.

Yep, Infix heisst die "normale" Schreibweise und Postfix die Notation mit den nachgestellten Operatoren (aka. RPN (UPN ist wohl Deutsch)).

Benutzername hat folgendes geschrieben:

Ich meld mich wieder, wenns Neuigkeiten und/oder Fragen gibt :stupid:

Anschliessend einige Ausdrücke, die ich testen würde:

1-(-1) = 2 (Doppelnegation)
-2^2 = -4 (Hoch vor Punkt vor Strich)
(-2)^2 = 4 (ausser bei Klammerung...)
2^3^4 = mathematisch gesehen 2.4179e+024, bei Taschenrechnern (z.B. der Firma TI) z.T. aber auch 4096
1+(-(1+2)) = -2 (Negation einer Klammer)

je nachdem sollten auch folgende Ausdrücke akzeptiert werden:
1---2 = -3 (verschachtelte Minusoperationen)
1*-2 = -2 (Negation ohne explizite Klammerung)
1e+3^2 = 1000000 ("1e+3" ist eine korrekte Float-Zahl)
9^5e-1 = 3 (ditto)
2(3) = 6 (Standardoperator = "*")

LigH - Mo 08.08.05 19:06

UPN (Umgekehrte Polnische Notation) ist das, das mit dem Stack arbeitet - "Postfix-Notation". "Infix" ist die aus der Schule gewohnte Schreibweise.

Benutzername - Mi 10.08.05 17:13

So, er ist nun fertig :)

@delphifan: Danke für die Ausdrücke die ich testen sollte, klappt wunderbar :)

Aber zu deinem zweiten Beispiel hätt ich noch ne Frage:
Du sagtest ja, dass -2^2 = -4 ist, wegen Hoch vor Punkt vor Strich, hab ich auch verstanden :lol:
Aber angenommen, ich hätte --2^2. Wäre das dann das gleiche wie -(-2^2) oder wäre das dann -(-2)^2 ?
Da blick ich nämlich noch net ganz durch *g*

//edit: Noch was *g*
Gibts irgendwelche Vergleichswerte von der Geschwindigkeit her, wo ich in etwa liege?
Das wäre find ich ganz interessant zu wissen. :)

AXMD - Mi 10.08.05 17:22

--2^2 = 2^2 = 4

nur wenn du -(-2)^2 hast, erhältst du -4.

AXMD

Benutzername - Mi 10.08.05 17:27

Okay, Danke :)
Alles, was ich wissen wollte *g*

Dann bügel ich den Fehler noch schnell aus (war mir nämlich nicht sicher) und dann kann ich den Parser (mit Beispielprojekt) ja mal posten, wenns jemanden interessiert *g*

delfiphan - Mi 10.08.05 18:11

Ich teste ihn gern aus für dich. Ich hab sicher schon 5 verschiedene Parser auf Herz und Nieren geprüft ;)

Geschwindigkeitsmässig müsste man unterscheiden zwischen Parsen und Auswerten. Mein Parser und auch andere Parser parsen zuerst den Ausdruck und erzeugen daraus einen Bytecode, Maschinencode oder sonst eine schnell auswertbare Struktur (wie z.B. Bäume). So kann ein Ausdruck schnell mehrmals ausgewertet werden (z.B. zum Graphen zeichnen).

Die eigentliche Auswertung geht dann relativ schnell; das Parsen geht etwas länger.

Benutzername - Mi 10.08.05 18:20

Okay, dann wende ich mich mal per PN an delfiphan und wenn dann alles funktioniert, stell ich ihn hier rein :)

delfiphan - Mi 10.08.05 18:22

Die PN schreibst du am besten an delfiphan :) ;)
Bin ja schon gespannt...