정규식을 사용하여 문자열이 회문인지 확인하는 방법은 무엇입니까?
제가 대답 할 수없는 인터뷰 질문이었습니다.
정규식을 사용하여 문자열이 회문인지 확인하는 방법은 무엇입니까?
추신 이미 " 주어진 문자열이 회문인지 확인하는 방법? "이라는 질문이 있으며 다른 언어로 많은 답변을 제공하지만 정규 표현식을 사용하는 답변은 없습니다.
이 질문에 대한 대답은 "불가능하다"는 것입니다. 보다 구체적으로 면접관은 당신이 계산 이론 수업에 관심을 기울 였는지 궁금해합니다.
계산 이론 수업에서 유한 상태 기계에 대해 배웠습니다. 유한 상태 머신은 노드와 에지로 구성됩니다. 각 모서리에는 유한 알파벳의 문자가 주석으로 표시됩니다. 하나 이상의 노드는 특수한 "수락"노드이고 한 노드는 "시작"노드입니다. 주어진 단어에서 각 문자를 읽을 때 우리는 기계에서 주어진 가장자리를 횡단합니다. 수락 상태가되면 기계가 그 단어를 "수락"한다고 말합니다.
정규식은 항상 동등한 유한 상태 기계로 변환 될 수 있습니다. 즉, 정규 표현식과 동일한 단어를 허용하고 거부하는 것입니다 (실제 세계에서 일부 정규 표현식 언어는 임의의 함수를 허용하지만 계산되지 않음).
모든 회문을 받아들이는 유한 상태 기계를 만드는 것은 불가능합니다. 증명은 임의로 많은 수의 노드가 필요한 문자열, 즉 문자열을 쉽게 만들 수 있다는 사실에 의존합니다.
a ^ xba ^ x (예 : aba, aabaa, aaabaaa, aaaabaaaa, ....)
여기서 a ^ x는 x 번 반복됩니다. 이것은 적어도 x 개의 노드가 필요합니다. 왜냐하면 'b'를 본 후에 우리는 그것이 회문인지 확인하기 위해 x 번 다시 카운트해야하기 때문입니다.
마지막으로 원래의 질문으로 돌아가서 면접관에게 유한 고정 길이보다 작은 모든 회문을 받아들이는 정규식을 작성할 수 있다고 말할 수 있습니다. 회문을 식별해야하는 실제 응용 프로그램이있는 경우 임의로 긴 응용 프로그램을 포함하지 않을 것이므로이 답변은 이론적 불가능 성을 실제 응용 프로그램과 구별 할 수 있음을 보여줍니다. 그래도 실제 정규 표현식은 동등한 4 줄 프로그램보다 훨씬 길다 (독자를위한 쉬운 연습 : 회문을 식별하는 프로그램 작성).
PCRE 엔진은 재귀 정규식을 지원 하지만 ( Peter Krauss의 답변 참조 ), 추가 코드없이이를 달성하기 위해 ICU 엔진 (예 : Apple 에서 사용)에서 정규식을 사용할 수 없습니다 . 다음과 같이해야합니다.
이것은 회문을 감지하지만 루프가 필요합니다 (정규 표현식이 계산할 수 없기 때문에 필요합니다).
$a = "teststring";
while(length $a > 1)
{
$a =~ /(.)(.*)(.)/;
die "Not a palindrome: $a" unless $1 eq $3;
$a = $2;
}
print "Palindrome";
불가능합니다. 회문은 일반 언어로 정의되지 않습니다. (참조, 나는 계산 이론에서 무언가를 배웠다)
Perl 정규식 사용 :
/^((.)(?1)\2|.?)$/
많은 사람들이 지적했듯이 엄격하게하려면 정규 표현식으로 간주 할 수 없습니다. 정규식 은 재귀를 지원하지 않습니다.
다음 은 모든 유형의 캐릭터에 대해 4 글자 회문 (예 : deed)을 감지하는 것입니다.
\(.\)\(.\)\2\1
다음 은 문자 만 확인하는 5 글자 회문 (예 : 레이더)을 감지하는 것입니다.
\([a-z]\)\([a-z]\)[a-z]\2\1
따라서 가능한 각 단어 길이에 대해 다른 정규식이 필요한 것 같습니다. Python 메일 링리스트 의이 게시물 에는 이유에 대한 세부 정보가 포함되어 있습니다 (Finite State Automata 및 pumping lemma).
당신이 얼마나 확신하는지에 따라이 대답을 드리겠습니다.
정규 표현식으로는하지 않을 것입니다. 정규식의 적절한 사용이 아닙니다.
예 , .Net에서 할 수 있습니다!
(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))
몇몇 사람들이 이미 말했듯이, 일반적인 회문을 감지하는 단일 정규식은 없지만 특정 길이까지 회문을 감지하려면 다음과 같은 것을 사용할 수 있습니다.
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
StackOverflow는 "정규식? 아니요, 지원하지 않습니다. 지원할 수 없습니다 ." 와 같은 답변으로 가득 차 있습니다 .
진실은 정규 표현식이 더 이상 정규 문법 과 관련이 없다는 것입니다. 현대 정규식은 재귀 및 균형 그룹과 같은 기능을 특징으로하며 그 구현의 가용성은 계속 증가하고 있습니다 (예를 들어 여기에서 Ruby 예제 참조). 제 생각에는 우리 분야의 정규식이 프로그래밍 개념이 아니라는 오래된 믿음에 매달리는 것은 단지 비생산적입니다. 더 이상 가장 적절하지 않은 단어 선택 때문에 그들을 미워하는 대신, 우리가 사물을 받아들이고 계속 나아갈 때입니다.
다음 은 Perl 자체를 만든 Larry Wall 의 인용문입니다 .
(…) 일반적으로 실제 정규 표현식과 약간만 관련이있는 "정규 표현식"이라고 부르는 것과 관련이 있습니다. 그럼에도 불구하고이 용어는 패턴 매칭 엔진의 기능과 함께 성장했기 때문에 여기서는 언어 적 필요성에 맞서 싸우려고하지 않을 것입니다. 그러나 저는 일반적으로 "정규식"(또는 앵글로색슨 분위기 일 때 "정규식")이라고 부를 것입니다.
다음 은 PHP의 핵심 개발자가 작성한 블로그 게시물 입니다 .
기사가 꽤 길었기 때문에 여기에 주요 요점을 요약했습니다.
- 프로그래머가 사용하는 "정규식"은 형식 언어 이론의 맥락에서 원래의 정규성 개념과 거의 공통점이 없습니다.
- 정규식 (최소 PCRE)은 모든 문맥 자유 언어와 일치 할 수 있습니다. 따라서 잘 구성된 HTML 및 거의 모든 다른 프로그래밍 언어와도 일치 할 수 있습니다.
- 정규 표현식은 최소한 일부 상황에 맞는 언어와 일치 할 수 있습니다.
- 정규식의 일치는 NP 완전합니다. 따라서 정규 표현식을 사용하여 다른 NP 문제를 해결할 수 있습니다.
즉, 다음을 사용하여 회문을 정규식과 일치시킬 수 있습니다.
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
... 분명히 정규 문법과는 아무런 관련이 없습니다.
자세한 정보 : http://www.regular-expressions.info/balancing.html
이제 Perl에서 할 수 있습니다. 재귀 참조 사용 :
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
print $istr," is palindrome\n";
}
마지막 부분 http://perldoc.perl.org/perlretut.html을 기반으로 수정
루비에서는 명명 된 캡처 그룹을 사용할 수 있습니다. 그래서 이런 식으로 작동합니다.
def palindrome?(string)
$1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end
시도해보세요 ...
1.9.2p290 :017 > palindrome?("racecar")
=> "racecar"
1.9.2p290 :018 > palindrome?("kayak")
=> "kayak"
1.9.2p290 :019 > palindrome?("woahitworks!")
=> nil
Regex Golf의 5 단계 (A man, a plan)에 대한 제 답변 입니다. 브라우저의 정규식 (Chrome 36.0.1985.143을 사용하고 있음)으로 최대 7 자까지 작동합니다.
^(.)(.)(?:(.).?\3?)?\2\1$
다음은 최대 9 자입니다.
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
작동하는 최대 문자 수를 늘리려면 반복적으로 .? 와 (:? () \ n..??)? .
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/
Oniguruma 엔진 (루비에서 사용)에 유효합니다.
실제로 정규 표현식보다는 문자열 조작으로 수행하는 것이 더 쉽습니다.
bool isPalindrome(String s1)
{
String s2 = s1.reverse;
return s2 == s1;
}
나는 이것이 인터뷰 질문에 실제로 답하지 않는다는 것을 알고 있지만, 당신은 그것을 사용하여 당신이 작업을 수행하는 더 나은 방법을 어떻게 아는지를 보여줄 수 있습니다. 그리고 당신은 모든 문제를 못처럼 보는 전형적인 "망치를 가진 사람이 아닙니다." . "
Perl에서 ( Zsolt Botykai의 답변 참조 ) :
$re = qr/
. # single letter is a palindrome
|
(.) # first letter
(??{ $re })?? # apply recursivly (not interpolated yet)
\1 # last letter
/x;
while(<>) {
chomp;
say if /^$re$/; # print palindromes
}
PCRE 표현식 (MizardX에서 제공) :
/^((.)(?1)\2|.?)$/
테스트 해 보셨나요? Win XP Pro의 내 PHP 5.3에서는 다음과 같은 오류가 발생합니다. aaaba 실제로 식 표현식을 약간 수정하여 다음과 같이 읽습니다.
/^((.)(?1)*\2|.?)$/
무슨 일이 일어나고 있는지는 외부 문자 쌍이 고정되어 있지만 나머지 내부 문자는 고정되어 있지 않다는 것입니다. 이것은 "aaaba"와 "aabaacaa"를 잘못 전달하지만 "aabaaca"에서는 제대로 실패하기 때문에 정답이 아닙니다.
이것에 대한 수정이 있는지 궁금합니다. 또한 Perl 예제 (JF Sebastian / Zsolt 작성)가 내 테스트를 올바르게 통과합니까?
비엔나의 Csaba Gabor
재귀 정규 표현식이 가능합니다!
회문을 포함하는 문자열을 감지하는 간단하고 자명 한 알고리즘 :
(\w)(?:(?R)|\w?)\1
에서 rexegg.com/regex-recursion 튜토리얼 작동 방법을 설명합니다.
모든 언어에서 잘 작동합니다. 여기에는 PHP를 사용하여 개념 증명과 동일한 소스 (링크)에서 수정 된 예제가 있습니다.
$subjects=['dont','o','oo','kook','book','paper','kayak','okonoko','aaaaa','bbbb'];
$pattern='/(\w)(?:(?R)|\w?)\1/';
foreach ($subjects as $sub) {
echo $sub." ".str_repeat('-',15-strlen($sub))."-> ";
if (preg_match($pattern,$sub,$m))
echo $m[0].(($m[0]==$sub)? "! a palindrome!\n": "\n");
else
echo "sorry, no match\n";
}
출력
dont ------------> sorry, no match
o ---------------> sorry, no match
oo --------------> oo! a palindrome!
kook ------------> kook! a palindrome!
book ------------> oo
paper -----------> pap
kayak -----------> kayak! a palindrome!
okonoko ---------> okonoko! a palindrome!
aaaaa -----------> aaaaa! a palindrome!
bbbb ------------> bbb
비교
정규식 ^((\w)(?:(?1)|\w?)\2)$은 동일한 작업을 수행하지만 "포함"대신 예 / 아니오로합니다.
추신 : "o"가 palimbrome이 아니라 "able-elba"하이픈 형식이 회문이 아닌 "ableelba"가있는 정의를 사용하고 있습니다. 이름 지정 definition1 .
"o"및 "able-elba"가 palindrone 인 경우 이름을 definition2로 지정 합니다 .
다른 "palindrome regexes"와 비교하면,
^((.)(?:(?1)|.?)\2)$\w제한 없이 위의 기본 정규식은 "able-elba"를 허용합니다.^((.)(?1)?\2|.)$( @LilDevil ) definition2를 사용하십시오 ( "o"및 "able-elba"를 허용하므로 "aaaaa"및 "bbbb"문자열 인식도 다릅니다).^((.)(?1)*\2|.?)$( @Csaba ) definition2를 사용하십시오 .
참고 : 비교하기 위해 비교 된 $subjects각 정규식에 대해 더 많은 단어를 추가 할 수 있습니다 .
if (preg_match('/^((.)(?:(?1)|.?)\2)$/',$sub)) echo " ...reg_base($sub)!\n";
if (preg_match('/^((.)(?1)?\2|.)$/',$sub)) echo " ...reg2($sub)!\n";
if (preg_match('/^((.)(?1)\2|.?)$/',$sub)) echo " ...reg3($sub)!\n";
if (preg_match('/^((.)(?1)*\2|.?)$/',$sub)) echo " ...reg4($sub)!\n";
ZCHudson이 지적한 대로 회문 집합이 일반 언어가 아니기 때문에 회문이 일반적인 정규 표현식으로는 수행 할 수없는 것이 있는지 확인합니다.
나는 Airsource Ltd 가 "불가능하다"는 것이 면접관이 찾고있는 종류의 대답이 아니라고 말했을 때 완전히 동의하지 않습니다. 인터뷰에서 나는 좋은 후보자를 만날 때 이런 종류의 질문을하고, 우리가 그에게 뭔가 잘못하도록 제안했을 때 그가 올바른 주장을 찾을 수 있는지 확인합니다. 나는 그가 더 나은 것을 안다면 잘못된 방법으로 무언가를 시도 할 사람을 고용하고 싶지 않습니다.
perl로 할 수있는 일 : http://www.perlmonks.org/?node_id=577368
회문으로 구성된 언어는 일반 언어가 아니라 문맥이없는 언어라고 면접관에게 설명하겠습니다.
모든 회문과 일치하는 정규 표현식은 무한 합니다. 대신 나는 그가 받아 들일 수있는 회 문의 최대 크기로 제한 할 것을 제안합니다. 또는 모든 회문이 필요한 경우 최소한 일부 유형의 NDPA를 사용하거나 단순한 문자열 반전 / 같음 기술을 사용하십시오.
캡처 그룹이 부족해지기 전에 정규식으로 할 수있는 최선의 방법 :
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
이것은 최대 19 자 길이의 모든 회문과 일치합니다.
모든 길이를 프로그래밍 방식으로 해결하는 것은 간단합니다.
str == str.reverse ? true : false
아직 인라인으로 주석을 달 수있는 담당자는 없지만 MizardX에서 제공하고 Csaba에서 수정 한 정규식은 PCRE에서 작동하도록 추가로 수정할 수 있습니다. 내가 찾은 유일한 실패는 단일 문자 문자열이지만 별도로 테스트 할 수 있습니다.
/^((.)(?1)?\2|.)$/
다른 문자열에서 실패하게 만들 수 있다면 댓글을 달아주세요.
#!/usr/bin/perl
use strict;
use warnings;
print "Enter your string: ";
chop(my $a = scalar(<STDIN>));
my $m = (length($a)+1)/2;
if( (length($a) % 2 != 0 ) or length($a) > 1 ) {
my $r;
foreach (0 ..($m - 2)){
$r .= "(.)";
}
$r .= ".?";
foreach ( my $i = ($m-1); $i > 0; $i-- ) {
$r .= "\\$i";
}
if ( $a =~ /(.)(.).\2\1/ ){
print "$a is a palindrome\n";
}
else {
print "$a not a palindrome\n";
}
exit(1);
}
print "$a not a palindrome\n";
From automata theory its impossible to match a paliandrome of any lenght ( because that requires infinite amount of memory). But IT IS POSSIBLE to match Paliandromes of Fixed Length. Say its possible to write a regex that matches all paliandromes of length <= 5 or <= 6 etc, but not >=5 etc where upper bound is unclear
In Ruby you can use \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b to match palindrome words such as a, dad, radar, racecar, and redivider. ps : this regex only matches palindrome words that are an odd number of letters long.
Let's see how this regex matches radar. The word boundary \b matches at the start of the string. The regex engine enters the capturing group "word". [a-z] matches r which is then stored in the stack for the capturing group "letter" at recursion level zero. Now the regex engine enters the first recursion of the group "word". (?'letter'[a-z]) matches and captures a at recursion level one. The regex enters the second recursion of the group "word". (?'letter'[a-z]) captures d at recursion level two. During the next two recursions, the group captures a and r at levels three and four. The fifth recursion fails because there are no characters left in the string for [a-z] to match. The regex engine must backtrack.
The regex engine must now try the second alternative inside the group "word". The second [a-z] in the regex matches the final r in the string. The engine now exits from a successful recursion, going one level back up to the third recursion.
After matching (&word) the engine reaches \k'letter+0'. The backreference fails because the regex engine has already reached the end of the subject string. So it backtracks once more. The second alternative now matches the a. The regex engine exits from the third recursion.
The regex engine has again matched (&word) and needs to attempt the backreference again. The backreference specifies +0 or the present level of recursion, which is 2. At this level, the capturing group matched d. The backreference fails because the next character in the string is r. Backtracking again, the second alternative matches d.
Now, \k'letter+0' matches the second a in the string. That's because the regex engine has arrived back at the first recursion during which the capturing group matched the first a. The regex engine exits the first recursion.
The regex engine is now back outside all recursion. That this level, the capturing group stored r. The backreference can now match the final r in the string. Since the engine is not inside any recursion any more, it proceeds with the remainder of the regex after the group. \b matches at the end of the string. The end of the regex is reached and radar is returned as the overall match.
here is PL/SQL code which tells whether given string is palindrome or not using regular expressions:
create or replace procedure palin_test(palin in varchar2) is
tmp varchar2(100);
i number := 0;
BEGIN
tmp := palin;
for i in 1 .. length(palin)/2 loop
if length(tmp) > 1 then
if regexp_like(tmp,'^(^.).*(\1)$') = true then
tmp := substr(palin,i+1,length(tmp)-2);
else
dbms_output.put_line('not a palindrome');
exit;
end if;
end if;
if i >= length(palin)/2 then
dbms_output.put_line('Yes ! it is a palindrome');
end if;
end loop;
end palin_test;
You can also do it without using recursion:
\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
or to exclude the empty string:
\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
Works with Perl, PCRE, Ruby, Java
A slight refinement of Airsource Ltd's method, in pseudocode:
WHILE string.length > 1
IF /(.)(.*)\1/ matches string
string = \2
ELSE
REJECT
ACCEPT
my $pal='malayalam';
while($pal=~/((.)(.*)\2)/){ #checking palindrome word
$pal=$3;
}
if ($pal=~/^.?$/i){ #matches single letter or no letter
print"palindrome\n";
}
else{
print"not palindrome\n";
}
\b([a-z])?([a-z])?([a-z])?\2\1\b/gi
Matches 5 letter palindromes such as refer and kayak. It does this using (non-greedy) matching of any three letters, followed by the 2nd and 1st matched letters.
'developer tip' 카테고리의 다른 글
| 내일 날짜를 dd-mm-yy 형식으로 얻는 방법 JavaScript (0) | 2020.10.15 |
|---|---|
| 문자열을 부울로 변환하는 방법 (0) | 2020.10.15 |
| 높은 응집력이란 무엇이며 어떻게 사용 / 만드는가? (0) | 2020.10.15 |
| emacs는 3 개의 짝수 창으로 분할됩니다. (0) | 2020.10.15 |
| 프로그래밍 방식으로 UIView의 고정 높이 제약 조건을 업데이트하는 방법은 무엇입니까? (0) | 2020.10.15 |