Liste in Baumstruktur einlesen

[martin86]

Hallo!
Folgendes Problem:
Ich habe einen Vector, indem ich Wertepaare einer rekursiven Datenstruktur (ähnlich wie XML, jedoch nur mit Open/Close-Tags und Textinhalt - bereits vollständig ipmlementiert) gespeichert habe und soll dieses nun in einer Baumstruktur darstellen.
Bsp:

Vector<MyPair>: [(OPEN, "tag1"), (OPEN, "tag2"), (TEXT, "text1"), (CLOSE, "tag2), (TEXT "text2"), (CLOSE, "tag1")]

repräsentiert folgende Baumstruktur:
<tag1>
<tag2>text1</tag2>
text2
</tag1>

diese wird mit meiner datenstruktur erstellt mit:

Text t1 = new Text("text1");
Text t2 = new Text("text2");
Element e1 = new Element("tag1");
Element e2 = new Element("tag2");

e2.add(t1);
e1.add(e1);
e1.add(t2);

Wie kann ich dies automatisch realisieren. am einfachsten dürfte das wohl mit Rekursion gehen, aber ich weiss nicht
wie ich diese Baumhierarchie durchlaufen soll. Muss ich da nicht irgendwie alle Ebenen zwischenspeichern, damit diese später zur Verfügung stehen, wenn ich später noch elemente in dieser ebene einfügen will??
Hat irgendjemand Ideen?

mfg martin

[/code]

 

[SlaterB]

wenn die Elemente in der richtigen Reihenfolge stehen, dann musst du dir nicht alles merken,
ansonsten wäre es eh schwer, falls nicht alle Elemente eine eindeutige Id haben,

so, du musst natürlich etwas von Rekursion verstehen,
wenn du noch gar nix dazu kennst dann empfehle ich erstmal, mit einfacheren Dingen zu üben, z.B. die Fakultät zu einer Zahl rekursiv auszurechen,

hier würde die Rekursion etwa wie folgt aussehen:

int rek(Element, Liste, index) {
// aktuelle Element in der Liste muss ein open sein,
// Element erstellen, im parent-Element einfügen

// weitere Elemente anschauen:
// wenn open, dann rek() aufrufen (*),
// wenn normaler Text, dann als Text-Element einfügen
// wenn Close dann fertig
}

die rek-Operation gibt den aktuellen Index zurück, damit der Aufrufer nach (*) weiß, bei welchem Index es weitergeht,
außerdem wird immer das aktuelle Element übergeben,
damit Unterelemente darin eingefügt werden können

 

[martin86]

Hallo!
Zuerst mal danke für die Antwort!

Also die Elmente stehen in meinen Vector in genau der Reihenfolge, wie sie gelesen wurden und es können in einer bereits durchlaufenen Ebene durchaus auch noch später Elemente/Texte hinzugefügt werden, d.h der Baum ist nicht symmetrisch, was vermutlich das Problem ist.

z.B ist auch möglich:

<report>
  <title>mytitle</title>
  <sentence>This is <emphasis>my</emphasis> sentence!</sentence>
</report>

Habe deinen Vorschlag jetzt übersetzt und erhalte nun natürlich aber einen symmetrischen Baum (=falsch)!

<report>
   <title>mytitle
        <sentence>This is
             <emphasis>my</emphasis>
        </sentence>
    </title>
</report>

Mein Code:

Tree t = new Element(list.get(0).name)  //root element
makeTree(t, index);

private Tree buildTree(Tree t, int index) {
     if(index >= list.size())
                 return t;
     if(list.get(index).type == Type.TEXT) {   //text
	  t.add(new Text(list.get(index).name));
	  buildTree(t, ++index);
     }
    else if(list.get(index).type == Type.OPENTAG) //element
	  t.add(buildTree(new Element(list.get(index).name), ++index));
    else
       buildTree(t, ++index);
    return t;
 }

 

[Wildcard]

Gibt es eigentlich einen bestimmten Grund warum du auf diese Liste bestehst, anstatt die Struktur realitätsnahe in einem Objektbaum abzubilden?

EDIT:
Oder möchtest du genau das, und die Liste ist nur eine Art Zwischenschritt nach dem Parsen? ???:L
Ist doch eine recht einfache Grammatik. Ich würde mir das vermutlich einfach durch einen Generator wie AntLR erzeugen lassen.
http://www.antlr.org/

 

[SlaterB]

@martin86
hmm, das ist schon ziemlich gut geworden,
dadurch, dass du etwa bei einem Text-Element die Rekursion mit dem gleichen t aufrufst, sparst du dir, mehrere Elemente aus der Liste abzufragen,
daran hatte ich nicht gedacht,

ein wichtiger Schritt dürfte nun noch sein, bei einem close gleich zu returnen,
dann müsste sentence erst von report aus gefunden werden, nicht von title,

ich glaube aber, dass du dann Probleme mit dem index bekommen wirst,
das klappt bisher nur durch die Symmetrie so gut,
also: wie in meinem Vorschlag als Rückgabewert den index weitergeben,
nachdem von report aus die Rekursion zu title aufgerufen und abgearbeitet wurde,
muss der report-Aufruf wissen, dass der nächste zu untersuchende Index der von sentance ist