Wie am besten Parsen?

[Ultimator]

Das war schön ausführlich und gut erklärt, danke alzaimar
Allerdings sollte es nur ein kleiner Matheparser werden, ohne "Sprachfeatures" oder sowas *g*
Ich hab mir schon Routinen geschrieben, die mir eben true zurückgeben, wenn ein Zeichen ein Punkt-Operator, ein Strich-Operator oder so ist.
Außerdem wird ein Term bereits ordentlich zerlegt,
aus

Code:

45*(60-18)+382/(+102)-3^897

zerlegt er also

Code:

45  *  (  60  -  18  )  +  382  /  (  +  102  )  -  3  ^  897

Das klappt soweit schon ganz gut

Ich denke, wenn ich auf eine "(" stoße, schaue ich, ob dahinter ein "-" ist mit einer anschließenden Zahl, und dann wieder die ")", dann speichere ich die negative Zahl in der Klammer in eine Variable, sehe dann, was nach der Klammer für ein Rechenzeichen kommt (speicher ich in einen eigenen Variablen-Typen, der u.A. auch "KeinOperator" enthält), danach hol ich mir die andere Zahl und "verwurste" die beiden per Operator. OK, es gibt natürliuch auch den Fall, dass die Zahl in der Klammer die hintere der beiden zu verwurstenden Zahlen ist, aber das seh ich ja daran, ob in meiner Operator-Variable "KeinOperator" oder was anderes gespeichert ist
Denkt ihr, das wäre ein guter funktionierender Ansatz?
Performance spielt erstmal keine Rolle

[alzaimar]

Wenn Du mein Rezept nimmst, dann ergeben sich alle Sonderfälle automatisch. Versuch das mal. 'Nur' einen Matheparser kann man auch mit einem Stack schreiben, auf den man so lange die Zahlen raufschiebt, bis man auf einen 'schwächeren' Operator trifft (oder so ähnlich)
Die Reihenfolge ist (Starke zuerst): */ +- () <EOF>, */ ist stärker als +-, das ist stärker als () das ist stärker als EOF.

3+4*5: 3 push + push 4 push * push 5 push <ENDE> (stack = 5 * 4 + 3)
<Ende> ist schwächer als der letzte Operator (*) also 5*4 ausrechnen und auf den Stack. Stack = 20 + 3. <Ende> ist schwächer als + also weiter rechnen und fertig.

4*5+3: 4 push * push 5 push + ist schwächer als *, der oberste Operator, also 4*5 ausrechnen. Kein schwächerer Operator mehr auf dem Stack, also weitermachen. + push 3 push <Ende> ist schwächer als +, also ausrechnen. Ergebnis wieder 23 (oh Wunder!)

Probier das mal, das ist recht kompakt.

[edit] ob ein operator (+-) ein Vorzeichen ist, oder nicht, wird vom Token links vom Operator gesteuert. Wenn das letzte Token eine Zahl war, dann ist der Operator KEIN Vorzeichen, sonst schon.

[Ultimator]

Ja, das klingt auch plausibel und vor allem verständlich

Zitat von alzaimar:

[edit] ob ein operator (+-) ein Vorzeichen ist, oder nicht, wird vom Token links vom Operator gesteuert. Wenn das letzte Token eine Zahl war, dann ist der Operator KEIN Vorzeichen, sonst schon.

Danke! Endlich hat mal jemand das in Worte gefasst, worüber ich schon tagelang überleg (eigentlich peinlich )
Wird schon klappen

[Ultimator]

So, jetz muss ich nochmal was fragen
Ich pushe ja solang, bis ich auf einen schwächeren Operator komme.
Angenommen, ich hab

7-3/(5-4*2)
push 3 push - push 8 push / [is ja stärker als -] push (
Jetz hab ich die Klammer-Auf gepusht, also muss ich mich um den Teil in der Klammer kümmern.
Muss ich da jetzt immernoch weiter pushen, bis ich die Klammer-Zu gepusht hab?

Das mit den Klammern versteh ich noch nicht ganz, wenn du das bitte nochmal erklären könntest?

Könnte man das eventuell in eine rekursive Funktion packen, die dem nächsten Aufruf einfach immer nur den nächst-tieferen Klammerterm zum ausrechnen übergibt?

[alzaimar]

Die Klammern musst Du gesondert betrachten. Bei '(' wird auf den Stack gepackt und bei einem ')' der Stack bis zum '(' aufgelöst. Rekursiv muss da Nichts sein. Das ist ja grad das Lustige an der Methode. Ich vermute mal, Du wirst den Operatoren Werte zuweisen. Stärker ist der, dessen Wert größer ist. Sollte das nicht mit den Klammern genauso gehen? Eine '(' stoppt das Auflösen des Stacks für alle Operatoren, mit Ausnahme des ')'. Das ')' löst den Stack bis zum '(' auf und entfernt ds '(' dann.

Beispiel:
2/(3*4+5)
2 push / push ( push 3 push * 4 push + ...ausrechnen 3*4-> 12 push. der Operator auf dem Stack ist das '('=STOP, nicht mehr weitermachen
auf dem Stack ist jetzt 2 / ( 12+, also weitermachen.
5 push )...Auflösen bis zum (', also 12+5=17 : Stack = 2/(17. Top-Operator ist jetzt '(', wir haben ein ')', also weg damit. Stack = 2/17.
Nächstes Token zu Pushen: <End of Input>... Also 2/17 ausrechnen und fertig.

Die Reduzieren des Stacks geht immer nur soweit, bis der oberste Operator ein '(' ist. Der Einzige, der ein '(' eliminieren kann, ist ein ')'.

Der Stack enthält also zu jedem Zeitpunkt nur die Teile des bisher abgearbeiteten Ausdruckes, der infolge der Punkt-Vor-Strich- und der Klammer-Regeln noch nicht ausgerechnet werden konnten. Er wird jeweils zum frühest möglichen Zeitpunkt reduziert, d.h. die obersten Elemente ausgerechnet (und damit der Stack ja verkleinert). Damit werden auch Klammerebenen automatisch richtig behandelt, denn ein ')' bewirkt nur, das Alles, was 'rechts' von dem letzten '(' steht, reduziert, d.h. ausgerechnet, wird.

Mich würde der Code interessieren, wenn es läuft.

[Ultimator]

*Groschen fall*
Danke, jetz hab ichs endlich verstanden
Den Code kriegst du ganz bestimmt, hast ja auch viel dazu beigetragen
Aja: Bisher misst der Parser gerade mal 160 Zeilen.
Außerdem getrennte Tokenize-, Parse- und Lösungs-Funktionen, damit man nicht mehr machen muss als nötig, wenn man den Term einmal "getokenized" hat. Bin richtig stolz auf mich

Das stellt jetzt eigentlich kein Problem mehr dar, allerdings hab ich gestern rausgefunden, dass die Sache mit den Vorzeichen beim ^-Operator noch nicht ganz klappt, wegen der Sache mit -3^2 = -(3^2) = -9. Da muss ich erst nochmal schauen, wie da die Regel mit den Vorzeichen definiert ist.

Achja, noch was *g*
Angenommen, ich hab 6+5*(-3)-4
Dann muss ich das doch so machen:
push 6 push + push * push ( push -3 push ) usw.
Nachdem ich die ) gepusht hab, weiß ich ja, dass ( der letzte Operator war.
Tu ich da 3mal pop ausführen, um dann die -3 zu pushen?

[Nils_13]

Der Parser von c.wuensch hat einen Fehler: Wenn ich
diesen Code habe:

Delphi-Quellcode:

PROGRAM Testprojekt;
VAR realx, a, b: integer;
Procedure proc;
  begin
    b := abc
  end;

BEGIN
  a := cdefg;
  x := hijklmnop;
  Writeln (x); readln (y)
END.

und ich verwandle das erste VAR (unter PROGRAM), und parse und vorher PROGRAM in ROGRAM verwandelt habe, dann kommt mir der Parser mit zwei Fehlern, statt einem an:

Code:

"PROGRAM" erwartet !
Anweisungsteil erwartet !

Damit dieser Fehler nicht auftritt, muss der ürbsprüngliche Code
(

Delphi-Quellcode:

If Programm Then ...
Else ... ;

)
durch

Delphi-Quellcode:

  If Programm Then
  begin
   Form1.errormemo.Clear;
  end
  Else
  begin
    ShowMessage('Fehler im Programm');
  end;

ersetzt werden