[NotABigFan]

#programowanie #python #regexp
Powiedzmy, że mam sobie drzewo binarne liczb całkowitych zapisanych w stringu za pomocą nawiasów. Np.: "((- 1 -) 0 (((- 1 -) 1 (- 1 -)) 0 (- 0 -)))" czyli drzewo to "-" lub "(lewePoddrzewo liczba prawePoddrzewo)". Jest jakieś wyrażenie regularne które da mi trzy grupy dla niepustego drzewa tak, żeby się nawiasy zgadzały? Próbowałem czegoś takiego:
r'\((\(.+\)|-) (\d+) (\(.+\)|-)\)' ale dostałem grupy:

(- 1 -) 0 (((- 1 -) 1 (- 1 -))
 0
(- 0 -))

[S.....s]

@NotABigFan: musi być regex? bo to tak jakbyś zupe chciał widelcem jeść

[MQs]

@NotABigFan: Jak przelecisz przez string i nawiasy przerobisz na tokeny z oznaczeniem poziomu zagnieżdżenia - np. jakieś (1| ... (2|....|2) ...|1)(1|...|1) to później zbudujesz drzewo rekursywnie łatwym wyrażeniem.

[NotABigFan]

@SuppressWarnings: Chcę napisać funkcję parsującą takie stringi do pamięci i gdyby taki regexp istniał to funkcja parsująca byłaby bardzo prosta.

[NotABigFan]

@MQs: Nie no chodziło mi o coś bardziej wysokopoziomowego

[asciiterror]

@NotABigFan: szczerze to nie sądzę żeby dało się to zrobić regexem, jest zbyt prosty. Regex działa w taki sposób że idzie od lewej do prawej i próbuje dopasować wzorzec, a tutaj musiałby liczyć jeszcze dodatkowo ile po drodze miał nawiasów otwierających i zamykających żeby wiedzieć kiedy skończy się lewePoddrzewo. Jeżeli znasz maksymalną wysokość drzewa to może wtedy dałoby się, ale to będzie monstrum.

[NotABigFan]

@asciiterror: Co prawda wiem, że język złożony ze zbalansowanych nawiasów nie jest regularny ale "prawdziwe" regexy potrafią matchować też niektóre języki nieregularne np.: https://stackoverflow.com/questions/3644266/how-can-we-match-an-bn-with-java-regex

[nesti32]

@NotABigFan: Nie czuje, ze regex bylby dobrym wyjsciem z twojego problemu. Napisz wlasny parser do tego problemu. Regexy nie zawsze wyjsciem : P

[NotABigFan]

@nesti32: To nie jest tak, że nie potrafię rozwiązać tego problemu inaczej tylko chciałem sprawdzić jak to zrobić regexem w pythonie. Właśnie czytam: https://www.regular-expressions.info/balancing.html i to chyba będzie to. Jak już rozwiążę problem to wkleje tutaj

[asciiterror]

@NotABigFan:

The .NET regex flavor [...]

https://stackoverflow.com/a/4108649
sprawdź czy da się zrobić to w Pythonie w ogóle, np. ?>

[NotABigFan]

@asciiterror: Z tego co ustaliłem w 're' się nie da ale moduł 'regex' wprowadził rekurencyjne dopasowania wzorem tych z perla i próbuje coś z tego sklecić. ?> dopasowuje tylko pierwszy zamykający nawias więc odpada

[NotABigFan]

@SuppressWarnings: @MQs: @asciiterror: @nesti32:
r'(\((?>[^\(\)]+|(?R))*\)|\d+|-)' dla modułu regex działa jeżeli usunąć skrajne nawiasy ( ͡° ͜ʖ ͡°). Czyli da sie da ( ͡° ͜ʖ ͡°)

[MQs]

@NotABigFan: Nie pisałem, że się nie da. Pisałem, ze lepiej zrobić inaczej.