Klammerpermutation?

[tuxedo]

Servus,
hab mal wieder ne tolle Aufgabe bekommen wo mir wieder n bisschen der Ansatz fehlt. Wie immer will ich keine Lösung von euch haben sondern einfach n paar Schlagwörter oder Ideen zur Aufgabe.

Meine erste Idee zur Aufgabe war/ist daß es sich irgendwie um eine Art Permutation handelt. Aber hier gehts ja um klammern und nicht um zahlenreihenfolgen...

Schreiben Sie ein Programm, welches eine natürliche Zahl n einliest und alle korrekt geklammerten
Ausdrucke, bestehend aus n öffnenden und n schliessenden Klammern ausgibt. Die Zahl der
gefundenen Klammerausdrücke soll zum Schluss ausgegeben werden. Schreiben Sie Ihr Programm
ohne Verwendung von Rekursion! Für n = 3 soll die Ausgabe also wie folgt aussehen:
((()))
(()())
(())()
()(())
()()()
Es waren 5 Klammerungen.

Gruß
Alex

 

[Bleiglanz]

nettes Problem, machs rekursiv

wenn n=1 dann gibts nur "()"

wenn n>1 dann erstelle die Liste für n-1 und nenne sie L

gib eine Liste zurück aus

"()"+ x sowie x + "()" sowie "("+x+")"

wobei x die Liste L durchläuft (nimm ein java.util.Set aus Strings, dann entstehen dabei auch keine Duplikate

vorsicht, stimmt vielleicht nicht, kommt mir jetzt zu einfach vor

 

[tuxedo]

Ja, rekursiv hätt ichs auch gemacht, aber ich MUSS es iterativ machen... Das ist ja mein Problem :-(
Mal sehen ob ich weiter komm'.

- Alex

 

[Bleiglanz]

das ist dämlich!

hier eine dämliche Lösung:

iteriere über alle Bitfolgen der Länge 2n, interpretiere 0 als öffnende klammer, 1 als schliessende klammer

anzahl 0 und 1 ungleich => wegwerfen

über ein stackmodell prüfen, ob so ein ausdruck korrekt ist (also durchlaufen, für ein 0 ein X auf den Stack legen, für ein 1 ein X vom Stack runter -> am ende muss der Stack leer sein und wenn ein 1 kommt und der Stack leer ist gibts auch einen fehler)