텍스트의 여러 부분에서 다른 기호를 여러 번 일치시키는 정규식

Question

나무에 유용한 Newick 형식을 구문 분석해야합니다. 또 다른 예를 들어,

(A,B,(C,D)E)F 

나 : 그것은 노드 표시 괄호, 쉼표 및 문자 시리즈처럼 보이는

(,(((,(,)),),)) 

(,) 요소는 같은 부모 노드를 의미한다. 내 목적 (두 리프 사이의 경로 길이를 측정하기 위해)에 중첩 된 요소를 찾는 것이 필연적으로 필요합니다.

그럼, 내 질문은 다른 기호를 동일한 횟수만큼 일치시키는 방법입니까?

CCCAAABBACCCABCCAAABBBBBBACCCCCABBBABBCCAABB 

정규식가 반환해야합니다 : ['AABB','AB','AAABBB','AB','AB','AABB']

반복 횟수가 다른 때마다

예를 들어, 내가 문자열 AB 패턴과 일치하고 싶다. 따라서 A{n}B{n}가 작동하지 않습니다.

감사합니다.

Answer 1

정규식 은이 할 수없는 고전적인 예제입니다.

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages "보조 정리 사용"에서 "a^nb^n"이라는 단어는 정규 표현이 아니므로 (정규 표현식에서는 인식 할 수 없음) 증명할 수 있습니다.

정규식을 사용하면 지정된 최대 n에 대해서만 정규 표현식을 만들 수 있습니다. 그러나 큰 n에 대한 표현은 평가하는 데 오랜 시간이 걸릴 수 있습니다.

추신. 공식 문법 (http://en.wikipedia.org/wiki/Formal_grammar) 또는 카운터 자동화 (http://en.wikipedia.org/wiki/Counter_automaton)를 사용하여 문제를 해결할 수 있습니다.