Tiefe einer Verschachtelung mittels Stack

[Istnichtschlimm]

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 ?

[Klotzkopp]

mit Hilfe eines einfachen FIFO Stacks

Was soll ein FIFO-Stack sein?

[Istnichtschlimm]

Ups ich meinte LIFO Stack...

Ein Stack ist "Stapel" auf den man Werte legen kann. Also man hat die folgenden Aktionen zur Auswahl:

push = legt etwas auf die Sptize des Stapels

pop = hol den obersten Wert vom Stapel und liefert den Wert

peek = liefert den Wert auf der Spitze des Stapels ohne diesen zu entfernen

Bsp. push(1),push(2) liefert

2

1

Wenn ich jetzt pop ausführe erhalte ich den obersten Wert also 2.

Deshalb die Bezeichnung LIFO (Last in First Out) d.h. was man zuletzt oben drauf gelegt hat bekommt man als erstes wieder zurück...

[Klotzkopp]

Ups ich meinte LIFO Stack...

Dachte ich mir

Ich würde einfach bei "Klammer auf" die neue Tiefe auf den Stack legen, und bei "Klammer zu" die Tiefe wieder vom Stack holen und ausgeben.

[Istnichtschlimm]

Naja ich glaube so leicht ist es nicht.

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

dann ergibt sich folgender Baum:

http://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 ?

[Der_Lampe]

und wo ist jetzt dein problem? bin ich nur zu müde oder funktioniert klotzkopp's methode auch bei deinem beispiel?! :schlaf:

[Klotzkopp]

Ich hatte das falsch verstanden.

Ich dachte, bei der Eingabe ({}[()]) soll ({2}[(3)2]1) herauskommen. Es soll aber wohl ({1}[(1)2]3) sein.

[Der_Lampe]

achso also soll praktisch angezeigt werden wie viel klammernpaare sich in dem momentanen klammerpaar befinden?

[Istnichtschlimm]

achso also soll praktisch angezeigt werden wie viel klammernpaare sich in dem momentanen klammerpaar befinden?

Ja....und ich hab immer noch keine Idee wie das gehen soll :upps

[lilith2k3]

Wie wäre es mit folgendem Schnellschuss:

Du hast eine Funktion:

ermittleKlammernpaare().

Und statt eines dummen Stacks, benutzt Du eine verkettete Liste.

ermittleKlammernpaare:=selbst+ermittleKlammernpaare(next);

Und selbst ist bei jedem Element eben 1.

E.g. 3 Elemente:

Selbst+Selbst+Selbst=3

Suchst Du dann die Tiefe von Element 2, so führst Du eben ermittleKlammernpaare() auf dem zweiten Element aus.

Du brauchst dann nur einen Iterator, der durch die Liste an Klammernpaaren wandert.

[Istnichtschlimm]

Das würde bei meinem Beispiel auch wieder Fehlschlagen^^

Also ich bin jetzt an dem Punkt angelangt wo ich auch auf andere Datenstrukturen als einen Stack zurückgreifen würde...

[lilith2k3]

Warum?

( ( ( ) ) )

3 2 1

War doch das, worauf Du hinauswolltest, oder etwa nicht?

[Istnichtschlimm]

Hm also wenn ich dich richtig verstanden habe dann würde ich für die äußerste Klammer von ({}[()]) eine Tiefe von 4 erhalten weil selbst + 3 Klammerpaare = 4

Dabei hat die äußerste Klammer hier eine Tiefe von 3! Sieht man wenn man sich das als Baum vorstellt:

http://img228.imageshack.us/img228/2...benanntdcx.jpg

[lilith2k3]

Das kommt auf Deine Implementation an... Dann hast Du eine Liste, die Listen als Elemente hat.

Wenn Du ({}[()]) zerlegst, hast Du in der Äußeren Klammer {1} und (3), in der {1}, in der [2] und der letzten (1).

Dann erfolgt die Berechnung mit leicht modifiziertem Algorithmus:

1. Ermittle alle Klammernpaare aller Nachfolgeelemente aller Unterlisten.

2. Gib den höchsten Wert zurück oder, wenn kein Nachfolger da, gib "Selbst" zurück.

Statt einer Liste benötigst Du eben einen Baum(Liste mit Listen als Unterelement quasi). Und die Berechnungsfunktion läßt sich prima rekursiv implementieren. Voilà!

Bearbeitet 20. November 2010 von lilith2k3

[Istnichtschlimm]

Sorry ich komm grad nicht ganz mit....

Kannst du das ganze als Pseudocode (oder evtl sogar in Java ) schreiben ?

[lilith2k3]

public class TreeNode {


    ArrayList<TreeNode> SubNodes = new ArrayList<TreeNode>();


    public void AddNode(TreeNode node)

    {

        if (node != this) SubNodes.add(node);

    }


    public int CalculateLevel()

    {

        int Level=1;

        int MaxSubLevel = 0;

        int TempLevel=0;


        if (SubNodes.size()>0){

            for(TreeNode item: SubNodes)

            {

                TempLevel=item.CalculateLevel();

                if (TempLevel > MaxSubLevel) MaxSubLevel=TempLevel;

            }

        }

        else return Level;


        return Level+MaxSubLevel;

    }


}

[/PHP]