Soci (Soczó Zsolt) szakmai blogja

2007.10.01.

Regex legbelső párok keresésére

Filed under: Regex,Szakmai élet — Soczó Zsolt @ 12:18

É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.

2 Comments

  1. 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.

    Comment by Szindbad — 2007.10.03. @ 08:34

  2. 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.

    Comment by Soczó Zsolt — 2007.10.03. @ 09:03

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress