Geklammerte Ausdrücke nach Divide&Conquer

[Lasse2000]

Hallo, ich sitze gerade an einer Aufgabe, bei der man vollständig geklammerte Ausdrücke z.B. (1 and ( 0 or 1)) nach dem Prinzip Divide & Conquer (sprich rekursiv) auswerten soll.
Habe jetzt mit der split() methode, den geklammerten Ausdruck in einzelne Tokens in dem entsprechenden Array gespeichert. Nun müsste ich aus den gegebenen Tokens, Teilausdrücken zusammenfassen und diese Teilausdrücke wieder zu Teilausdrücken usw. ... bis ich dannn zu dem Gesamtausdruck komme.
Da weiß ich aber nicht, wie man da vorgehen soll**** Was für Parameter brauch man zusätzlich für den rekursiven Aufruf**** Vielleicht kann mir ja wer weiterhelfen.

 

[theXs]

Hallo, ich sitze gerade an einer Aufgabe, bei der man vollständig geklammerte Ausdrücke z.B. (1 and ( 0 or 1)) nach dem Prinzip Divide & Conquer (sprich rekursiv) auswerten soll.
Habe jetzt mit der split() methode, den geklammerten Ausdruck in einzelne Tokens in dem entsprechenden Array gespeichert. Nun müsste ich aus den gegebenen Tokens, Teilausdrücken zusammenfassen und diese Teilausdrücke wieder zu Teilausdrücken usw. ... bis ich dannn zu dem Gesamtausdruck komme.
Da weiß ich aber nicht, wie man da vorgehen soll**** Was für Parameter brauch man zusätzlich für den rekursiven Aufruf**** Vielleicht kann mir ja wer weiterhelfen.

Wie genau willst du die Ausdrücke denn Auswerten?

Das erste was du gucken müsstest wäre ob die Anzahl an '(' der Anzahl von ')' entspricht, damit die Klammersprache erstmal syntaktisch korrekt ist.

Dann nehme ich an willst du die Ausdrücke per boolesche Funktion Auswerten, also das
(1 OR 0 ) --- true ist während
(1 AND 0) --- false ist

 

[Lasse2000]

Naja, das ist ja das Problem. Ich weiss nicht ganz genau, wie die Impelmentierung des Algorithmus aussehen soll. Es soll aufjedenfall nach dem Divide & Conquer Prinzip ausgewertet werden. Das bedeute ja, dass wir das Problem (11 and(10 or 00)) in Teilprobleme gesplittet werden müssen. Das mache ich, indem ich die split() methode anwende. Jetzt muss ich die einzelnen Tokens wieder in verschiedene Teilausdrücke zusammenfassen, sodass ich dann irgendwann das Ergebinis aus den Teilausdrücken bekomme. Ich weiss nur nicht, wie das aussehen soll.****

 

[theXs]

Naja, das ist ja das Problem. Ich weiss nicht ganz genau, wie die Impelmentierung des Algorithmus aussehen soll. Es soll aufjedenfall nach dem Divide & Conquer Prinzip ausgewertet werden. Das bedeute ja, dass wir das Problem (11 and(10 or 00)) in Teilprobleme gesplittet werden müssen. Das mache ich, indem ich die split() methode anwende. Jetzt muss ich die einzelnen Tokens wieder in verschiedene Teilausdrücke zusammenfassen, sodass ich dann irgendwann das Ergebinis aus den Teilausdrücken bekomme. Ich weiss nur nicht, wie das aussehen soll.****

Erstmal hat deine Tastatur bestimmt auch ne RETURN Taste - macht das Lesen unheimlich einfacher. Ansonsten poste doch mal die gesamte Aufgabe.

Nachtrag: Am einfachsten Ist es wenn du von dem Ausdruck ausgehst der am innersten liegt und diesen auswertest. Ausgehend von diesem Ausdruck kannst du dann expandieren und weitere Ausdrücke lösen.

Das kannst du meiner Meinung nach am einfachsten mit einem Regulären Ausdruck erreichen, dafür musst du aber erst kontrollieren das die Klammerzahl übereinstimmt. Dann suchst du einfach nach einem Ausdruck der eine ( und eine ) hat. KEINE andere Klammer.

 

[Lasse2000]

1.einlesen eines ausdrucks
2.aufteilen des ausdrucks mittels String.split(...) )
3.Auswerten der Teilausdrücke nach dem Design-Prinzip Divide-and-Conquer und
Zusammenfügen zum Ergebnis des Gesamtausdrucks (Einlesen von Hexadezimalzahlen mit
Integer.parseInt(s,16)). Als Übergabewerte zwischen verschiedenen Ebenen des Divideand-
Conquer Algorithmus verwenden Sie bitte nicht Strings!
4.Ausgeben des Ergebnisses (Ausgabe von Hexadezimalzahlen mit
Integer.toHexString(..))
Beispiel-Ausgaben (vor dem Gleichheitszeichen jeweils die Eingabe).
1e7 = 1e7
dead = dead
( 1 or 1 ) = 1
( 1 and 3 ) = 1
( not 1 and ff ) = fe
( 1 or ( 2 or a ) ) = b
( not ( 1 or c ) and f00f ) = f002