Hilfestellung bei Rekursion

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Hilfestellung bei Rekursion

    Hallo,
    In der letzten Zeit habe ich mich viel mit PHP Programmierung beschäftigt. Auf dem Gebiet der OOP fühle ich mich mittlerweile relativ sicher und habe mich mittlerweile ein wenig in rekursives Programmieren eingearbeitet. Bei PHP reichen die Online Lektüren aber leider selten über die Rekursion mit einfachen Zahlenaufgaben hinaus.

    Mit Zahlen ist die Rekursion relativ plausibel für mich, schwierig wird es wenn ich sie auf andere Gebiete anwenden möchte. Insofern suche ich hier nach kleinen Denkanstößen!
    Ich würde gerne eine verschachtelte Textdatei aufspalten, wobei die Anzahl der verschachtelten Ebenen unbekannt ist. Ein Beispiel:

    HTML-Code:
    (anfang)
    (ende)
    (anfang)
        (anfang)
        (ende)
    (ende)
    (anfang)
        (anfang)
            (anfang)
            (ende)
        (ende)
    (ende)
    Um das ganze einfach zu halten möchte ich die Inhalte erst einmal in ein Array speichern, sobald also die Rekursion eine weitere Ebene gefunden hat, den Inhalt und eine Kennung über array_push() einzutragen.

    Ab hier fehlt mir ein Denkansatz.

    Mit freundlichen Grüßen,
    ranopalepu

  • #2
    Hallo,

    jede rekursive Funktion braucht eine Abbruchbedingung. In deinem Falle ist das die Prüfung ob das aktuelle Element ein ende-Tag ist. Wenn nicht, geht die Rekursion eine Ebene tiefer. Nicht vergessen, dass die Funktion einen Rückgabewert hat und jeder rekursive Aufruf diese Rückgabe entsprechend entgegennehmen und in seinem eigenen Ergebnis aggregieren muss.

    Ein vorgeschalteter Tokenizer würde die rekursive Funktion noch weiter vereinfachen.

    Gruß,

    Amica
    [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
    Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
    Super, danke!
    [/COLOR]

    Kommentar


    • #3
      Danke für die Antwort,

      Das (ende) das Abbruchkriterium ist, hat mir sehr geholfen, darüber habe ich schon eine ganze Weile gegrübelt. Als Rückgabewert könnte sich doch eine künstliche ID im Sinne der aktuellen „Tiefe“ anbieten, oder?

      Wo würdest du mit dem Tokenizer trennen? Immer wenn mich (ende) wieder auf die oberste Ebene zurückbringt?

      Kommentar


      • #4
        Zitat von ranopalepu Beitrag anzeigen
        Als Rückgabewert könnte sich doch eine künstliche ID im Sinne der aktuellen „Tiefe“ anbieten, oder?
        Nö, davon hast du ja nichts. Ich denke, du willst ein Array haben? Also ist der Rückgabewert immer ein (evtl. auch leeres) Array. Die aktuelle Tiefe interessiert dich im Idealfall nicht die Bohne, du arbeitest ja rekursiv. Wenn du iterativ arbeitest, dann brauchst du die Tiefe.

        Mit dem Tokenizer würde ich nach Tokens trennen. Bisher sehe ich drei Tokenkandidaten:
        1. begin "(anfang)"
        2. end "(ende)"
        3. text <alles andere>
        Zuletzt geändert von AmicaNoctis; 29.03.2010, 19:28.
        [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
        Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
        Super, danke!
        [/COLOR]

        Kommentar


        • #5
          Zitat von AmicaNoctis Beitrag anzeigen
          Mit dem Tokenizer würde ich nach Tokens trennen.
          Sorry, ich hatte mich wohl noch nicht ausreichend über Tokenizer informiert, bislang kannte ich den Begriff Token nur im Zusammenhang mit Sicherheitsaspekten.

          Zitat von AmicaNoctis Beitrag anzeigen
          Bisher sehe ich drei Tokenkandidaten:
          1. begin "(anfang)"
          2. end "(ende)"
          3. text <alles andere>
          Inwiefern werden mir diese Trennungen dann helfen? Soll es einfacher werden die Suchmuster auf den Inhalt anzuwenden oder soll es die Aufbereitung für das Array vereinfachen?

          Kommentar


          • #6
            Zitat von ranopalepu Beitrag anzeigen
            Inwiefern werden mir diese Trennungen dann helfen?
            Es befreit deine rekursive Funktion von der Prüfung der Zeichenkette hinsichtlich der Tags und dem Zusammenstückeln des Reststrings. Davon abgesehen kannst du später den Tokenizer austauschen, falls sich diese Tags ändern, ohne dafür die rekursive Funktion selbst anfassen zu müssen. Außerdem ist es so übersichtlicher.
            [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
            Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
            Super, danke!
            [/COLOR]

            Kommentar


            • #7
              Ich habe mich jetzt ein wenig mit dem Tokenizer beschäftigt, habe aber keinerlei Informationen darüber gefunden, ob man dem in PHP integrierten Tokenizer um eigens definierte Tokens erweitern kann. Ist das möglich?

              Wenn ja, wäre mir das lieber als dass ich mit explode() oder split() das Rad neu erfinden würde, wäre mit 3 verschiedenen Token dann auch deutlich aufwändiger.

              Kommentar


              • #8
                Der eingebaute Tokenizer ist dafür nicht geeignet. Der tokenisiert nur PHP-Code. So schwer ist es ja auch nicht:
                PHP-Code:
                    function tokenize ($pString) {
                        
                $list preg_split("<(\\(anfang\\)|\\(ende\\))>"$pString, -1PREG_SPLIT_DELIM_CAPTURE);
                        
                $tokens = array();
                        foreach (
                $list as $k => $v) {
                            if (
                $v == "(anfang)") {
                                
                $tokens[] = (object) array("class" => "begin""content" => $v);
                            }
                            else if (
                $v == "(ende)") {
                                
                $tokens[] = (object) array("class" => "end""content" => $v);
                            }
                            else if (
                trim($v) != "") {
                                
                $tokens[] = (object) array("class" => "text""content" => trim($v));
                            }
                        }
                        return 
                $tokens;
                    } 
                [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
                Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
                Super, danke!
                [/COLOR]

                Kommentar


                • #9
                  Danke dass du dich so Hilfsbereit zeigst!

                  Sieht nach einem guten Weg aus, so gelöst auf jeden Fall besser als mein Alternativweg ausgesehen hat. Für mich aber noch nicht nachvollziehbar ist, wieso du dich dazu entschieden hast die Token als Object zu setzten und nicht einfach als Array?

                  Kommentar


                  • #10
                    Weil ich es schöner finde, später
                    PHP-Code:
                    $token->class 
                    zu schreiben, als
                    PHP-Code:
                    $token["class"
                    .
                    [COLOR="DarkSlateGray"]Hast du die [COLOR="DarkSlateGray"]Grundlagen zur Fehlersuche[/color] gelesen? Hast du Code-Tags benutzt?
                    Hast du als URL oder Domain-Beispiele example.com, example.net oder example.org benutzt?
                    Super, danke!
                    [/COLOR]

                    Kommentar

                    Lädt...
                    X