Komplexe nicht gieriger Matching mit regulären Ausdrücken

Question

Ich versuche, Zeilen aus einer HTML-Tabelle zu analysieren, mit Zellen spezifische Werte mit regulären Ausdrücken in Python enthalten. Mein Ziel in diesem (konstruierten) Beispiel ist es, die Zeilen mit "Kuh" zu bekommen.

import re 

response = ''' 
<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
''' 

r = re.compile(r'<tr.*?cow.*?tr>', re.DOTALL) 

for m in r.finditer(response): 
    print m.group(0), "\n" 

Meine Ausgabe ist

<tr class="someClass"><td></td><td>chicken</td></tr> <tr class="someClass"><td></td><td>chicken</td></tr> <tr class="someClass"><td></td><td>cow</td></tr>

<tr class="someClass"><td></td><td>cow</td></tr>

<tr class="someClass"><td></td><td>cow</td></tr>

Während mein Ziel zu bekommen, ist

<tr class="someClass"><td></td><td>cow</td></tr>

<tr class="someClass"><td></td><td>cow</td></tr>

<tr class="someClass"><td></td><td>cow</td></tr>

verstehe ich, dass die nicht-gierig? funktioniert in diesem Fall nicht, weil Backtracking funktioniert. Ich habe mit negativen Look Behinds und Lookahead herumgespielt, kann es aber nicht zum Laufen bringen.

Hat jemand Vorschläge?

Ich bin mir dessen bewusst Lösungen wie schöne Suppe, usw., aber die Frage ist, über reguläre Ausdrücke zu verstehen, das Problem nicht per se.

Um Anliegen der Menschen ansprechen über keine regulären Ausdrücke für HTML verwenden. Das allgemeine Problem, das ich will nur mit regulären Ausdrücken lösen, ist aus

response = '''0randomstuffA1randomstuff10randomstuffA2randomstuff10randomstuffB3randomstuff10randomstuffB4randomstuff10randomstuffB5randomstuff1''' 

dem Ausgang

0randomstuffB3randomstuff1 

0randomstuffB4randomstuff1 

0randomstuffB5randomstuff1 

und randomstuff sollte als zufällige Zeichenfolge zu bekommen interpretiert werden (aber mit 0 oder 1 nicht).

Answer 1

Ihr Problem hängt nicht mit der Gierhaftigkeit zusammen, sondern mit der Tatsache, dass die Regex-Engine versucht, an jeder Position in der Zeichenfolge von links nach rechts erfolgreich zu sein. Deshalb erhalten Sie immer das am weitesten links Ergebnis und die Verwendung eines nicht-gierigen Quantifier wird die Startposition nicht ändern!

Wenn Sie so etwas wie schreiben: <tr.*?cow.*?tr> oder 0.*?B.*?1(für Ihr zweites Beispiel) die Muster werden zuerst versucht:

<tr class="someClass"><td></td><td>chicken</td></tr>... 
# ^-----here 

# or 

    0randomstuffA1randomstuff10randomstuffA2randomstuff10randomstuffB3ra... 
# ^-----here 

Und die erste .*? essen Zeichen bis „Kuh“ oder „B“. Ergebnis, das erste Spiel ist:

<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 

für Ihr erstes Beispiel, und:

0randomstuffA1randomstuff10randomstuffA2randomstuff10randomstuffB3randomstuff1 

für die zweite.

Um zu erhalten, was Sie wollen, müssen Sie die Muster an unerwünschten Positionen in der Zeichenfolge fehlschlagen. Um das zu tun ist .*? nutzlos, weil zu freizügig.

Sie können z. B. verbieten, dass ein </tr> oder ein 1 vor "Kuh" oder "B" auftritt.

# easy to write but not very efficient (with DOTALL) 
<tr\b(?:(?!</tr>).)*?cow.*?</tr> 

# more efficient 
<tr\b[^<c]*(?:<(?!/tr>)[^<c]*|c(?!ow)[^<c]*)*cow.*?</tr> 

# easier to write when boundaries are single characters 
0[^01B]*B[^01]*1 

Answer 2

Wenn Ihre 'Antwort'-Zeichenfolge immer Zeilenumbrüche enthält, können Sie tun, was Sie ohne Regex benötigen. Verwenden Sie die integrierte Funktion split, um eine Liste jeder Zeile zu erstellen. Dann die Liste iterieren und sehen, ob ‚Kuh‘ in der Zeile ist:

response = ''' 
<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>chicken</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
<tr class="someClass"><td></td><td>cow</td></tr> 
''' 

lines = response.split('\n') 
cows = [] 
for line in lines: 
    if 'cow' in line: 
     cows.append(line) 
print(cows) 

Ausgang:

['<tr class="someClass"><td></td><td>cow</td></tr>', '<tr class="someClass"><td></td><td>cow</td></tr>', '<tr class="someClass"><td></td><td>cow</td></tr>'] 

Answer 3

Sie wirklich gar nicht für diese regex müssen.

Sobald Sie das hinzufügen? Quantifizierer zu Ihrem Ausdruck, haben Sie den Token faul (nicht gierig) gemacht.

Wie auch immer, man konnte einfach tun:

for line in example: 
    if 'cow' in line: 
     print(line) 

keine Regex erforderlich.

Wenn Sie wissen wollen, was ein „genügsam“ Spiel tut, tut es dies:

import re 

lazy = r'[a-z]*?b' 
#    ^^ lazy 
greedy = r'[a-z]*b' 
#    ^greedy 

string = 'aaabbbaaabbb' 

print(re.match(lazy, string)) 
print(re.match(greedy, string)) 

Ausgang

<_sre.SRE_Match object; span=(0, 4), match='aaab'> 
<_sre.SRE_Match object; span=(0, 12), match='aaabbbaaabbb'> 

Beachten Sie, dass das erste Spiel bis zum ersten ‚b übereinstimmen "Es trifft. Das ist, weil es versucht, so oft wie möglich (faul) zu entsprechen.

Die gierige Übereinstimmung wird bis zum letzten 'b' übereinstimmen, da sie so oft wie möglich zu suchen versucht.

Beide Übereinstimmungen werden 'nach Bedarf zurückgeben', das heißt, wenn es andere Token gibt, die übereinstimmen könnten, könnten diese stattdessen verwendet werden.

Answer 4

Wenn die Eingabezeichenfolge jedes Tag in einer separaten Zeile enthält, würde Moses Koledoye's answer funktionieren.
Wenn jedoch die Tags über mehrere Zeilen verteilt sind, würde folgendes erforderlich:

import re 


response = ''' 
<tr class="someClass 
"><td></td><td>chicken</td></tr><tr class="someClass"><td></td><td>chic 
ken</td></tr><tr class="someClass"><td></td><td>cow</td></tr><tr class="someC 
lass"><td></td><td>cow</td></tr><tr 
class="someClass"><td></td><td>c 
ow 
</td></tr> 
''' 


# Remove all the newlines 
# Required only if words like 'cow' and '<tr' are split between 2 lines 
response = response.replace('\n', '') 

r1 = re.compile(r'<tr.*?tr>', re.DOTALL) 
r2 = re.compile(r'.*cow.*', re.DOTALL) 

for m in r1.finditer(response): 
    n = r2.match(m.group()) 
    if n: 
     print n.group(), '\n' 

Beachten Sie, dass dies auch funktionieren würde, wenn die Tags auf separaten Linien waren wie im Beispiel Zeichenfolge gezeigt vorgesehen, so Dies ist eine allgemeine Lösung.