86. Regular Expression

정규 표현식(정규식, Regular Expression, Regex/Regexp, Rational Expression)은 규칙을 가진 문자열의 집합을 표현하기 위해 사용되는 형식 언어이다. 일부 프로그래밍 언어와 텍스트 편집기는 문자열의 검색 및 치환 등을 위해 정규 표현식을 지원하고 있으며, 표준 라이브러리에 정규 표현식이 제공되지 않는 대부분의 프로그래밍 언어는 별도의 라이브러리를 통해서 정규 표현식을 사용할 수 있다. python과 JAVA는 표준 라이브러리에 정규 표현식이 제공되며, C++의 경우 C++11 표준에 정규 표현식이 추가되어 C++11 표준부터는 정규 표현식을 사용할 수 있다. C에도 정규 표현식이 존재하지만 POSIX 환경에서만 사용이 가능하다.

 

정규 표현식의 기본적인 문법은 다음과 같다.

1. 문법적인 의미를 갖고 있지 않는 모든 문자(이를 메타 문자라고 한다)는 문자 그대로 해석된다.	a → "a"
2. \ 문자 뒤에 메타 문자가 나오는 경우 앞에 나오는 \는 무시되며 뒤의 메타 문자는 문법적인 의미가 없는 일반 문자로 해석된다.	\? → "?" \\ → "\"
3. | 문자는 좌우의 문자열 중 하나와 대응된다.	a|b → "a", "b"
4. ( )는 메타 문자의 범위를 명시한다.	ab|c → "ab", "c" a(b|c) → "ab", "ac"
5. ? 문자는 앞에 나오는 문자가 최대 한 번 나타날 수 있음을 의미한다.	ab?c → "ac", "abc"
6. * 문자는 앞에 나오는 문자가 임의의 횟수만큼 반복될 수 있음을 의미한다.	ab*c → "ac", "abc", "abbc", "abbbc", ...
7. + 문자는 앞의 나오는 문자가 한 번 이상 반복될 수 있음을 의미한다.	ab+c → "abc", "abbc", "abbbc", "abbbbc", ...
8. {$n$}은 앞 문자가 $n$번 반복됨을 의미한다.	a{3}b → "aaab"
9. {$n,$}은 앞 문자가 $n$번 이상 반복됨을 의미한다.	a{2,}c → "aac", "aaac", "aaaac", "aaaaac", ...
10. {$n, m$}은 앞 문자가 $n$번 이상 $m$번 이하로 반복됨을 의미한다.	a{2, 4}b → "aab", "aaab", "aaaab"
11. . 문자는 임의의 문자 하나와 대응된다. 단일행 모드의 경우 새줄 문자는 제외한다.	a.b → "aab", "abb", "acb", "adb", ...
12. ^ 문자는 문자열 또는 행의 시작을 의미한다.
13. $ 문자는 문자열 또는 행의 끝을 의미한다.
14. [ ]는 [ ] 사이의 문자 중 하나와 대응된다. | 문자를 여러 개 쓴 것과 같은 의미이다.	b[acf]c → "bac", "bcc", "bfc"
15. [^ ]는 [^ ] 사이에 없는 문자 중 하나와 대응된다.	a[^bde] → "aa", "ac", "af", "ag", ...
16. [ - ]는 [ ]에 포함되는 문자의 범위를 명시한다.	[a-d]c → "ac", "bc", "cc", "dc"
17. (그밖의 메타 문자)[각주:1]	\w = [A-Za-z0-9_] (낱말) \W = [^A-Za-z0-9_] (낱말이 아닌 문자) \a = [A-Za-z] (알파벳) \d = [0-9] (숫자) \D = [^0-9] (숫자가 아닌 문자) \l = [a-z] (소문자) \u = [A-Z] (대문자) \x = [A-Fa-f0-9] ($16$진수) \p = [\x20-\x7E] (공백 및 보이는 문자) \b = (낱말 경계) \s = [ \t\n\v\f\r] (공백 문자)[각주:2] \S = [^ \t\n\v\f\r] (공백이 아닌 문자)

정규식의 패턴의 변경과 관련된 패턴구분자, 패턴변경자는 여기서는 다루지 않았으나 많은 정규식에 포함되며 이것 때문에 정규식이 복잡해지기도 하므로 주의해야 한다.

---

C++11 표준에 추가된 헤더파일 <regex>는 C++에서 정규 표현식을 사용할 수 있게 해 준다. 기본적인 기능으로 다음과 같은 것들이 존재한다. 더 자세한 내용은 여기에서 확인할 수 있다.

 

std::regex	regex 객체
std::regex_match	문자열이 정규식에 대응되는지 확인한다.
std::regex_search	정규식에 대응되는 문자열을 찾는다.
std::regex_replace	원하는 패턴의 문자열을 다른 문자열로 치환한다.
std::smatch	정규식에 대응되는 문자열을 std::string 형태로 반환한다.

연습문제에 코드가 있으므로 참고하면 좋다.

 

[연습문제]

 

BOJ 2671. 잠수함식별 (Gold V)

입력되는 문자열이 문제에 주어진 정규 표현식에 대응하는지 확인한다. C++의 regex를 이용하면 다음과 같이 구현할 수 있다.

#import<bits/stdc++.h>
using namespace std;
string s;
regex r("(100+1+|01)+");
smatch m;
int main()
{
    cin >> s;
    if(regex_match(s, m, r))cout << "YES";
    else cout << "NO";
}

 

→ solved.ac tag: regex

---

1. Perl/Tcl/vim 기준이다. 각각의 메타 문자가 지원되는 범위가 다르므로 확인해야 한다. 자세한 내용은 여기에서 확인할 수 있다. [본문으로]
2. vim 에디터의 경우 \\s는 [ \t]를 의미하며 \\_s가 공백 문자 전체를 의미한다. [본문으로]