일부 정규 표현식을 도와주세요

Question

나는 용 책을 읽고 일부 정규 표현식 연습에 매달렸습니다. 흥미 롭습니다. 도움이 될만한 사람이 있습니까? 다음 언어 정규 표현식을 작성 해주세요 :

문제 1 :의 짝수 및 B의 홀수와의와 b 년대의
모든 문자열을.

문제 2 :
서브 시퀀스 abb를 포함하지 않는 모든 문자열. (S의 서브는 0 개 이상의 SEG의 반이 아니 반드시 연속적인 위치를 삭제하여 형성된 문자열 바나나의 서브 순서입니다.)

문제 3 :
없이 반복 자리 숫자의 모든 문자열을 (반복 된 숫자가 아니다 필연적으로 연속적이다).

문제 4 :
최대 한 자릿수의 반복 자릿수 (반복 자릿수는 반드시 연속적 일 필요는 없습니다).

우리가 잘 이해할 수 있도록 POSIX 문법을 사용하십시오. 또한 우리는 세 가지 기본 언어 연산, 즉 조합, 연결 및 클로저를 사용할 수 있을지 궁금합니다.

감사합니다.

Answer 1

엄격한 정규 표현식 (연결, 결합, 폐쇄)을 사용하면 POSIX 정규 표현식으로 변환 할 수 있습니다. POSIX regex를 가지고 있다면 더 정교한 regex 엔진으로 변환 할 수 있습니다.

가정은

이 대답은 자바 스크립트 정규식의 지원 수준을 가정 (예견을 가지고 있지만 숨김 모습), 하지만 우리는 또한지지 않습니다 (이 먼저 읽어)이 . 일치 예외없이 모든 문자. 여기서 정규 표현식은 문자열 전체가 패턴과 일치한다고 가정합니다.

1 문제

^(?=(?:b*ab*a)*b*$)(?=(?:a*ba*b)*a*ba*$)[ab]*$ 

따라서,이 문제에 대한 DFA를 구성 할 수 있고,이 존재에만 연결, 연합 클로저 정규식. (DFA의 주에있는 숫자는 a와 b의 수를 비교 한 것입니다).

그러나, 엄격한 정규 표현식 도출 아주 엉망이다; 둘러보기는 우리가 생각하는 방식을 단순화합니다. a 년대의 짝수 의미 b 임의로 사이에 유한 한 많은로 -

• (?=(?:b*ab*a)*b*$)
  은 전체 문자열 (b*ab*a)*b* 일치하는지 확인 (인해 ^와 $의 효과) 예견이고 및 주변.
• (?=(?:a*ba*b)*a*ba*$)
은 전체 (a*ba*b)*a*ba* 문자열과 일치하는지 검사 예견 인 - b '(S)의 홀수 의미로 a 임의로 및 주변 사이에 유한 한 많은.

위의 정규식을 사용하여 문자열을 검사하여 문자열이 지정된 속성을 충족시키는 지 확인해야합니다.

POSIX 정규식으로

, 당신은이 속성을 주장하는 이들 2 정규식에 대해 문자열 2 번을 테스트 할 수 있습니다

^(b*ab*a)*b*$ 
^(a*ba*b)*a*ba*$ 

그러나 엄격한 정규 표현식이 존재하고 가능하기 때문에, 일치하는 하나의 POSIX 정규식이 존재

속성을 충족시키는 문자열. DFA를 엄격한 정규 표현식으로 변환하는 방법은 this post을 참조하십시오.

문제 2

^(?!.*a.*b.*b).*$ 

그냥보고 미리, 하위 순서 abb 일치 할 수있는 방법이 없다는 것을 확인.

알파벳이 지정되지 않았으므로이 문자는 모든 문자로 해석 될 수 있으므로 엄격한 정규 표현식으로 작성할 수 있지만 비실용적입니다. 그러나, 쉽게 쓸 수있는 부정 문자 클래스가 허용되는 경우 :

([^a]*a[^b]*b[^b]*|[^a]*a[^b]*|[^a]*) 

(위의 엄격한 정규 표현식이지만, 쉽게 POSIX 정규 표현식으로 다시 쓸 수있다)

오른쪽에서 왼쪽으로 교대로 3 개의 항목이 DFA의 3 개 주에 해당합니다. 아직 찾을 수 없음 a; a이 있지만 앞에는 b이 없습니다. a 및 b 다음에 이어지지 만 아직 발견되지 않았습니다. b. DFA에서 다른 트랩 상태 (목표 상태로 전환 할 수 없음)가 있습니다. 서브 시퀀스 abb이 발견되었습니다.

문제 3

^(?!\d*(\d)\d*\1)\d+$ 

부정적인보기 미리를 사용하여, 우리는 단지 우리가 문자가 반복되는 찾을 수있는 경기가없는 것을 확인합니다. 이것은 숫자 문자열이므로 적어도 하나의 숫자 \d+을 지정하여 일치하는 빈 문자열을 허용하지 않습니다. 이 정규 표현식의 요지는 캡처 된 그룹 및 백 - 레퍼런스를 사용하는 것입니다.

이 정규식을 작성하는 것이 가능한 모든 일치 항목을 하나씩 나열하는 것과 거의 같기 때문에 다시 한번이 규칙은 엄격한 정규식이 있지만 실용적이지 않습니다. 총 일치 수는 Sum [i = 1..10] (10!/i!) (앞에 0을 허용)입니다. 다음 문자가 허용되는지 여부는 지금까지 처리 된 모든 문자에 크게 의존하기 때문에 주변에는 방법이 없습니다.

포착 그룹을 무효화 할 메커니즘이 없으므로 POSIX 정규 표현식에서도 실용적이지 않습니다.

문제 4

이 하나 더 나은 정규식 가지고 올 수 없습니다

...

^(?!(?=.*(.).*\1).*((?!\1).).*\2)(?!.*(.)(?:.*\3){2})\d+$ 

이 실패 2 조건은 다음과 같습니다 중 숫자가 2 회 이상 반복한다 또는 두 개의 다른 자릿수가 반복됩니다.

• (?!(?=.*(.).*\1).*((?!\1).).*\2)은 2 자리 숫자가 반복되지 않는지 확인합니다. 이 미리보기 (?=.*(.).*\1)은 한 문자가 반복되는 것을 선택하고 (적어도 두 번) .*((?!\1).).*\2은 ((?!\1).)으로 인해 이전에 확인한 것과 다른 자릿수를 선택하고 반복되는 자릿수를 찾습니다.
• (?!.*(.)(?:.*\3){2})은 숫자가 최대 두 번 반복되는지 확인합니다. 안쪽의 패턴은 3 개의 숫자 인스턴스와 일치합니다.

문제 3과 동일한 문제가 있으므로 엄격한 정규 표현식이나 POSIX 정규 표현식을 쓰는 것이 실용적이지 않습니다. 궁금한 점이 있으면 Sum [i = 1..10] (10!/i!) + Sum [i = 1..10] ((i + 1)C2 * 10!/i!) 개의 일치 항목 (0을 허용)이 있습니다. 문제 3, 4, 특히 문제 4

---

, 문자열은 숫자가 포함되어 있는지 확인 후 자리하고 반복되는 숫자를 확인하는 동안 루프를 정렬하는 것이 더 실용적입니다.