Tiefe der Verschalchtelung mit Hilfe eines Stacks

Neue Frage »

Istdochnichtschlimm Auf diesen Beitrag antworten »
Tiefe der Verschalchtelung mit Hilfe eines Stacks
Hey,
hat jetzt zwar nicht wirklich was mit Mathe zu tun aber ich denke an so einer kniffligen Aufgabe haben auch Mathematiker Spaß Augenzwinkern

Also ich möchte mit Hilfe eines einfachen FIFO Stacks die Tiefe einer Verschachtelung (bsp Klammern) ermitteln.Die Tiefe steht jeweils bei der schließenden Klammer:

Bsp:

(
(
)
)

Führt zu

(
(
1)
2)

Das heißt die innere Klammer hat eine Tiefe von 1 (eben nur sich selbst) und die äußere Klammer eine Tiefe von 2.

Hat jmd eine Idee wie man sowas mit einem Stack realisieren kann ?
Istdochnichtschlimm Auf diesen Beitrag antworten »

Wichtig ist dass der zu bearbeitende Ausdruck von Klammern nur ein einziges mal von oben nach unten gelesen werden kann...
 
 
Mazze Auf diesen Beitrag antworten »

Du speicherst die öffnenden Klammern auf dem Stack. Jedes mal wenn Du eine schließende Klammer findest, schreibst Du die Anzahl der Stackelemente als tiefe hinzu und entfernst eine öffnende Klammer vom Stack. Wenn Du an die Anzahl der Stackelemente nicht herankommst, musst Du eine laufende Nummer mit auf den Stack packen.

Aber im Informatikboard wärst Du mit der Frage besser aufgehoben.
Istdochnichtschlimm Auf diesen Beitrag antworten »

Sorry ich meinte einen LIFO Stack,....
Mazze Auf diesen Beitrag antworten »

Ein Stack ist immer LIFO, denn sonst hast Du eine Queue und keinen Stack. Ist aber ansich nur eine Benennungsfrage. An meiner "Lösung" ändert sich damit aber nichts.
Istdochnichtschlimm Auf diesen Beitrag antworten »

Achso....jetzt verstehe ich deine Lösung Augenzwinkern Du hast aber "Tiefe" falsch verstanden...mit Tiefe ist das so gemeint dass man sich den Ausdruck quasi als Baum vorstellt und die Tiefe beschreibt dann die Tiefe des Teilbaumes der zum jeweiligen Klammerpaar gehört...sowie in meinem Bsp.

Nach deinem Algorihmus wären die Werte genau vertauscht d.h. du würdest in deinem Fall
(
(
2)
1)

erhalten
Mazze Auf diesen Beitrag antworten »

Achso, naja, muss man nur leicht modifizeren. Du legst zusätzlich auf den Stack die aktuelle Tiefe. Wenn man eine schließende Klammer findet, erhöht man die Tiefe und ordent sie der Klammer zu. Trifft man auf eine öffnende Klammer , reduziert man die Tiefe (mit Minimum 0).
Istdochnichtschlimm Auf diesen Beitrag antworten »

Naja ich glaube so leicht ist es nicht.

Nehmen wir z.b. ({}[()])

dann ergibt sich folgender Baum:

img228.imageshack.us/img228/2711/unbenanntdcx.jpg


D.h. der oberste Knoten bzw das äußerste Klammerpaar () hat eine Tiefe von 3 (sich selbst + 2 Klammerpaare).

Weil man das maximum der beiden Unterbäume wählt ist das ganze komlizierter oder nicht ?
Mazze Auf diesen Beitrag antworten »

Nach meinem Algorithmus :

( lesen, Stack tiefe 0
{ lesen, Stack tiefe 0
} lesen, Stack tiefe um 1 erhöhen - {} hat also Tiefe 1
[ lesen, Stack tiefe um 1 verringern, Stacktiefe 0
( lesen, Stack tiefe 0
) lesen, Stack tiefe um 1 erhöhen - () hat also Tiefe 1
] lesen, Stack tiefe um 1 erhöhen - [()] hat also Tiefe 2
) lesen, Stack tiefe um 1 erhöhen - ({}[()]) hat also Tiefe 3

Muss das irgendwie anders sein?
Istdochnichtschlimm Auf diesen Beitrag antworten »

Ok dann folgendes Bsp bei dem ich was falsches erhalte:

img143.imageshack.us/img143/2176/unbenanntxxh.jpg

( lesen, Stack tiefe 0
( lesen, Stack tiefe 0
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 1
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 1
( lesen, Stack tiefe um 1 verringern, Tiefe = 0
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 1
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 2
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 3
( lesen, Stack tiefe um 1 verringern, Tiefe = 2 ) lesen, Stack tiefe um 1 erhöhen, Tiefe = 3
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 4
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 5
) lesen, Stack tiefe um 1 erhöhen, Tiefe = 6


Beim Fett gedruckten der Fehler...offensichtlich ist das eine Klammer die geöffnet und direkt wieder geschlossen wird,...d.h. es ergibt sich hierfur eine Tiefe von 1....hab ich was falsch verstanden ?
Mazze Auf diesen Beitrag antworten »

Ja, das ist tatsächlich ein Fehler. Gut bemerkt.

Man kann folgendes festhalten. Entweder hat eine schließende Klammer tiefe 1 oder es folgt mindestens eine weitere schließende Klammer. Die weitere Klammer hat dann aber nicht zwangsläufig Tiefe 2, wie dein Beispiel schön zeigt.

Ich muss da nochmal drüber nachdenken, aber ich denke man muss sich die Anzahl der offenen Klammern mit auf den Stack packen.
Istdochnichtschlimm Auf diesen Beitrag antworten »

Noch nen guten Einfall gehabt ? Augenzwinkern

Ich zerbrech mir den Kopf aber komme einfach nicht drauf :/
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »