Keskustelu: Ohjelmointikysymykset: PHP: Sisäkkäisen datan erottelu regexpillä

Tarkoitus olisi parsia dataa kaarisulkujen välistä regexpillä. Löysin Mastering Regular Expressions -sivulta tuohon regexpin, jota sitten yritin muuttaa PHP:lle ja suluista kaarisulkuihin, mutta ei oikein luonnistu, tulee vain tyhjää. Ilman ^ ja $ -metamerkkejä tuo kyllä natsaa entity data -kohtiin, mutta osa datasta voi sisältää kaarisulkuja, joten pitäisi saada siis poimittua kaarisulut vain rivien aluista. Vinkkiä jatkoon? Toinen homma on sitten keksiä tuohon vielä se syvyyden määrittely, johon em. sivulla annettiinkin Perl-vinkki.

_{Nykyinen regexp (preg_match_all-funktiolle)}

/^\{[^()]*(\{[^()]*\}[^()]*)*\}$/m

_{data (lyhenneltynä ja pseudoarvoilla)}

{
worldspawn data
{
solid data
}
{
entity data
{
brush data
}
{
brush data
}
}
}

Mitä säännöllisen lausekkeen pitäisi tarkalleen erottaa esimerkkidatasta?

Sehän se unohtu, mietinkin :).

Tuloksena pitäis olla jotain seuraavanlaista:

array(5) {

  [0] => "{
worldspawn data
{
solid data
}
{
entity data
{
brush data
}
{
brush data
}
}
}"

  [1] => "{
solid data
}"

  [2] => "{
entity data
{
brush data
}
{
brush data
}
}"

  [3] => "{
brush data
}"

  [4] => "{
brush data
}"

}

Ts. olisi tarkoitus eritellä kaikki toisiaan vastaavien kaarisulkujen välissä oleva data.

Säännölliset lausekkeet eivät pysty tunnistamaan rakenteita, joissa sisäkkäisten tasojen määrä on rajoittamaton. Jos sisäkkäisiä sulkupareja on korkeintaan tietty määrä (esim. viisi), säännöllisen lausekkeen voi muodostaa, mutta siitä tulee luultavasti pitkä ja sekava. Helpoimmalla päässet, jos selvität nuo tiedot ilman säännöllisiä lausekkeita esim. parilla for-silmukalla:

<?php

$data = "
{
worldspawn data
{
solid data
}
{
entity data
{
brush data
}
{
brush data
}
}
}
";

$rivit = array_map(trim, explode("\n", $data));

for ($i = 0; $i < count($rivit); $i++) {
    if ($rivit[$i] == "{") {
        $kerros = 0;
        $taso = "";
        for ($j = $i; $j < count($rivit); $j++) {
            $taso .= $rivit[$j] . "\n";
            if ($rivit[$j] == "{") $kerros++;
            if ($rivit[$j] == "}") $kerros--;
            if ($kerros == 0) break;
        }
        $tasot[] = $taso;
    }
}

print_r($tasot);

?>

Halunnet poimia kaikki tapaukset riippumatta sisäkkäisten sulkujen määrästä. Se ei taida normaalilla regexpillä onnistua. (Perlin ihmeohjelmat ovat toki asia erikseen.)

Mastering Regular Expressions kirjoitti:

You can construct a regular expression that matches nested constructs up to a certain depth, but not to any arbitrary level of nesting.

Luultavasti tehokkain vaihtoehto on kirjoittaa tehtävään oma merkkijonoalgoritmi. Helpollakin tietysti voi yrittää päästä lisäämällä silmukassa ehtoon aina yhdet sulkeet niin kauan, kuin osumia tulee.

Näppärässä lineaarisessa algoritmissa olisi taulu ja pino: taulu alku-loppu-pareja ja pino, jossa olisivat vain avoimet alkukohdat. Avaavan sulun kohdalla lisättäisiin tämä kohta avoimiin, sulkevan sulun kohdalla taas otettaisiin päällimmäinen avoin alkukohta ja merkittäisiin se päättyväksi.

kun (kohta = seuraava alku tai loppu tekstissä) < pituus,
  jos kohta on uusi alkukohta,
    lisätään kohta pinoon,
  muuten
    otetaan alku pois pinosta,
    lisätään ratkaisuksi (alku, loppu) eli (alku, kohta).

P.S. Tarkoitat ilmeisesti aaltosulkuja etkä kaarisulkuja.

http://fi.wikipedia.org/wiki/Sulkeet:

Eniten käytetään kaarisulkeita ( ). Muita sulkeita ovat hakasulkeet [ ], aaltosulkeet { } ja kulmasulkeet 〈 〉.

Aaltosulut, aivan. Ja maksimisyvyys on tiedossa, tämä on 3. Nykyinen regexp poimii arvot toisiksi ylimmältä tasolta. Sen verta kompleksinen tuo kumminkin taitaa olla että strposeilla pelaan, kiitoksia vaivannäöstä.