[Java] Mithilfe von 2 Stacks (logischen) Ausdruck parsen

[neogeo]

Hallo erstmal! :)

Um gleich zur Sache zu kommen: Ich habe logische Ausdrücke a la

"((A | B) & C)"

als Strings vorliegen. Die Buchstaben repräsentieren dabei Mengen, genauer gesagt handelt es sich dabei um Sets, also die Abbildung von Mengen in der Sprache Java.
Das logische "und" bzw. "oder", also | und &, wird durch union und intersect ausgedrückt. Sets in Java haben dafür ja schon Methoden wie z.B. addAll oder retainAll.

Desweiteren habe ich schon eine Methode gebaut, um die Stringausdrücke in ein String-Array zu überführen und alles unnötige (Leerzeichen z.B.) zu entfernen, außerdem wird die korrekte Klammerung überprüft.

Ich hab aus obigen also ein Array erzeugt erzeugt wie:
["(","(","A","|","B",")","&","C",")"]

Soweit, so gut. Jetzt soll der Ausdruck ausgewertet werden. Als Rahmenbedingung ist vorgegeben, dass das ganze zeichenweise durchlaufen werden soll und mit 2 Stacks funktionieren soll und bei jeder schließenden Klammer berechnet werden soll.

Und hier weiß ich nicht weiter, habt ihr eine Idee?
Bäume, irgendwelche anderen Notationen etc. sollen nicht verwendet werden!

Bisher haue ich alle Operanden (also Mengen) auf Stack 1, alle Operatoren auf Stack 2 und bei jeder schliessenden Klammer werden die 2 letzten Mengen und der letzte Operator gepoppt, das ganze verbandelt und die Ergebnismenge wieder auf den Operandenstack gelegt.

Für obigen Ausdruck funktioniert das, für die meisten anderen Ausdrücke natürlich nicht. Öffnende Klammern betrachte ich z.B. noch garnicht und bei einer schließenden Klammer werden auch immer nur die letzten beiden Operanden verarbeitet.
Irgendwas habe ich auf jeden Fall nicht beachtet.


Vielen Dank :)

[Gnafoo]

Ich vermute einmal, es läuft darauf hinaus, einen LL(1)-Parser zu basteln, der an den entsprechenden Stellen im Code direkt die Berechnungen ausführt. Das grobe Vorgehen wäre:

1.) Grammatik der Sprache definieren
2.) Prüfen ob die Grammatik LL(1) ist
3.) Ggf. linksfaktorisieren und Linksrekursion eliminieren
4.) Parser ausprogrammieren
5.) Berechnungscode ergänzen

Dabei hat man die Wahl, ob man einen Parser mit Tabelle (und explizitem Stack) oder ausprogrammiert durch rekursiven Abstieg (d. h. implizitem Stack) schreibt. Wahrscheinlich ist hier die Version mit Tabelle gemeint, wobei Stack 1 für den Parser selbst notwendig ist, während Stack 2 zur Berechnung der Ergebnisse verwendet wird. Ich schmeiße jetzt mal ein paar Wikipedia-Links (mit Codebeispielen (y)) in die Runde:

http://en.wikipedia.org/wiki/LL_parser
http://en.wikipedia.org/wiki/Recursive_descent_parsers
http://en.wikipedia.org/wiki/Left_recursion

Beim rekursiven Abstieg ist die Berechnung denke ich am anschaulichsten: im Prinzip geht man rekursiv entsprechend den Regeln der Grammatik abwärts, bis man bei einem Terminal (sprich einer deiner Mengen) angekommen ist. Die muss man dann auf den Stack pushen. Wenn eine Regel vollständig verarbeitet wurde (d.h. die rechte Seite wurde vollständig erkannt), dann steigt man wieder auf. Passiert das bei einer Regel mit Operation, dann führt man die Berechnung mit den Mengen auf dem Stack durch.

Ich denke, dass es so funktionieren würde. Es sollte zumindest ein brauchbarer Startpunkt sein. Wenn du die Grammatik (ohne Linksrekursion etc.) formulieren kannst und die Berechnung sinnvoll an den Regeln festmachen kannst, dann ist der größte Teil schon erledigt. Die Umsetzung sollte dann relativ 1:1 laufen.

PS: wenn man die Variante mit dem rekursiven Abstieg wählt braucht man vermutlich gar keinen expliziten Stack mehr. Die Methoden geben dann einfach das resultierende Set zurück.

[Yavion]

(...) Stack 1 für den Parser selbst notwendig ist, während Stack 2 zur Berechnung der Ergebnisse verwendet wird. (...)

Das macht Sinn.
Ich habe mich beim Lesen des Posts gefragt, warum jemand für das Parsen hier 2 Stacks benötigen würde bzw das eine Vorgabe für eine entsprechende Aufgabenstellung ist.