October 1, 2007 / by Zsolt Soczó

Regex legbelső párok keresésére

Érdekes kérdés jött fel a devportálon.
Párokat kell keresni egy szövegben, de úgy, hogy a legbelső párokat találjuk meg.

Pl. begin end begin end, ebben két begin end-et kell találni, nem pedig egy nagyot, amiben benne van egy end begin.

A párost könnyű megfogni, amit nehezebb, hogy szűkítsük le a legkisebb halmazra a kifejezést.

Esetünkben úgy gondolkodhatunk, hogy begin aztán akármiből legalább egy majd end, és a kettő között nem lehet end. Ezzel megakadályozhatók az átlapolt eredmények.

A problémát a zero-width negative lookahead assertion tudja megoldani, amely “Continues match only if the subexpression does not match at this position on the right.”

Ez egy ilyen zero-width negative lookahead assertion izé: (?!end). Azt jelenti, hogy jobbról (azaz a ) után) nem lehet olyan, hogy end karakterek.

Azaz a példánkra: begin(.(?!end)).+?end

Ahhoz, hogy ez több sorra is menjen, a . értelmezését ki kell terjeszteni a \n-re is, .netben a Single Line mód biztosítja ezt.

Jó cikk a témában.

LEAVE A COMMENT

2 COMMENTS

  • Szindbad October 3, 2007

    Ilyesmire regexpet hasznalni velemenyem szerint design hiba. A regexpel a regularis nyelvet lehet felismerni (a veges allapotgepek nyelve, azaz amit veges allpotgepekkel fel lehet ismertetni), a pelda viszont (tetszolegesen sok egymasba agyazott nemterminalisok) nem regularis nyelv, veges allapotgeppel felismerni nem lehet (vagy csak nem tul szep hackkel). Ilyen problemak megoldasara veremautomatat illik hasznalni, az sokkal elegansabb, atlathatobb, kevesbe hack. SZVSZ.

  • Soczó Zsolt October 3, 2007

    Abszolút igazad van, sok esetben olyan dolgokra is regexet használunk/nak, amire nem való. Ebben az esetben a kérdező egyszerűen sok forráskódban szeretett volna tömeges cseréket végrehajtani, erre nem akart saját kódot írni, inkább egy search/replace kellett neki, valami hekkelt regexxel. Így megbocsájtható a dolog, szerintem.