使用正则表达式
星期五, 十一月 21st, 2008使用正则表达式
[原文地址] http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=regularExpressions
[翻译] liruqi
介绍
正则表达式是一个描述匹配模式的特殊的字符串。相信你们中许多人已经在输入例如ls(dir) *.txt的时候见过并使用正则表达式，来获取扩展名为txt的文件列表。正则表达式不仅仅用于模式匹配，也可以进行文本处理。在SRM中正则表达式用起来非常方便。许多需要一些代码量的问题，可以用正则表达式几行搞定，非常飘逸。
正则表达式的具体描述
一个正则表达式（regex）是一个或者多个非空的分支，用‘|’分隔开。它匹配任意一个括号中的匹配模式。下面的正则表达式可以匹配三个单词”the”, “top”, “coder”中的任意一个。
REGEX is : the|top|coder
INPUT is : Marius is one of the topcoders.
Found the text ”the” starting at index 17 and ending at index 20.
Found the text ”top” starting at index 21 and ending at index 24.
Found the text ”coder” starting at index 24 and ending at index 29.
一个分支是一个或者多个块连接而成。每个块匹配了，一个分支才匹配。
一个块是一个原子表达式（不可再分的符号），后面很可能跟着’*', ’+', ’?', 或者边界。原子表达式跟着’*'匹配一个能够跟原子表达式匹配0次或多次的序列。原子表达式跟着’+'匹配一个能够跟原子表达式匹配1次或多次的序列。原子表达式跟着’?'匹配一个能够跟原子表达式匹配0次或1次的序列。
下面的正则表达式匹配任何连续出现的单词’top’ 和 ’coder’.
REGEX is: (top|coder)+
INPUT is: This regex matches topcoder and also codertop.
Found ”topcoder” starting at index 19 and ending at index 27.
Found ”codertop” starting at index 37 and ending at index 45.
一个范围是指’{‘跟着一个无符号十进制整数，可能跟着一个’,'，可能跟着另一个十进制整数，总是跟着’}'。如果有两个整数，前面一个不能够大于后面一个。一个原子表达式跟着一个只有一个整数i没有逗号的范围，匹配一个刚好匹配i个原子表达式的连续序列。一个原子表达式跟着一个只有一个整数并带上逗号的范围，匹配一个匹配i个或者更多个的原子表达式的连续序列。一个原子表达式跟着一个两个整数i和j的范围，匹配一个匹配从i个到j个的原子表达式的连续序列。下面的正则表达式匹配长度为2，3，4的’1′字符串。
REGEX is: 1{2,4}
INPUT is: 101 + 10 = 111 , 11111 = 10000 + 1111
Found the text ”111″ starting at index 11 and ending at index 14.
Found the text ”1111″ starting at index 17 and ending at index 21.
Found the text ”1111″ starting at index 33 and ending at index 37.
我们不难观察到，该过程是贪心地匹配最长的可匹配序列，而且匹配串不能重叠。一个原子表达式是包含在’()’中的（匹配一个正则表达式模式），一个括号表达式（看下面），’.'（匹配任意一个字符），’^'（匹配行首的空字符串），’$'行尾的空字符串），‘\’后面跟着`^.[$()|*+?{\'中的任意一个（将其当作一般的字符）或者一个没有其它意义的字符（匹配单个字符）。还有另外一种类型的原子表达式，引用符'\'后面跟着一个非0的十进制数d，匹配前面出现的第d个括号内的子表达式匹配的序列(根据子表示的左括号的位置从左到右编号)。因此，例如'([bc]\1)’匹配’bb’或者’cc’，但是不匹配’bc’。
下面的正则表达式匹配两个由小写字母组成的、并以任意字符隔开的单词。
Current REGEX is: ([a-z]+).\1
Current INPUT is: top-topcoder|coder
I found the text ”top-top” starting at index 0 and ending at index 7.
I found the text ”coder|coder” starting at index 7 and ending at index 18.
一个括号表达式是一个字符表包含在’[]‘中。它一般匹配字符表中的任意单个字符。如果字符表是以’^'开头的，它匹配任意不在字符表中的单个字符。如果字符表中两个字符被’-'隔开，那么这是一个表示字符闭区间的简写（例如，’[0-9]‘ 匹配任何数字）。除了’]',’^',’-' 之外的所有特殊字符，包括’\',在括号表达式中都没有特殊意义。
下面的正则表达式匹配任意三个不是’b',’c',’d' 开头,且以‘at’结尾的连续字符。
Current REGEX is: [^b-d]at
Current INPUT is: bat
No match found.
Current REGEX is: [^b-d]at
Current INPUT is: hat
I found the text ”hat” starting at index 0 and ending at index 3.
这个例子组合了上面讲到的大多数的概念。正则表达式匹配一个html标签的起始、结束对。
REGEX is: <([a-zA-Z][a-zA-Z0-9]*)(()|[^>]*)>(.*)</\1>
INPUT is: <font size=”2″>TopCoder is the</font> <b>best</b>
Found ”<font size=”2″>TopCoder is the</font>” starting at index 0 and ending at index 37.
Found ”<b>best</b>” starting at index 38 and ending at index 49.
([a-zA-Z][a-zA-Z0-9]*) 匹配任意一个起始为字母，后跟字母或者数字的单词。(() | [^>]*) 匹配空字符串或者不以’>’结尾的任意字符串。\1将会被前面与([a-zA-Z][a-zA-Z0-9]*)匹配的单词替换掉。
上面的描述是一个基本正则表达式内容的覆盖。一个按照以上规则写出来的正则表达式应该都可以在Java(>=1.4) 和 C++(POSIX EXTENDED)环境里工作。如果想更深入地了解的不同语言的扩展支持，你可以查看参考部分的内容。
使用正则表达式
Java语言
java（1.4或以上）有一个包”java.util.regex”，可以容许使用正则表达式。
这个包包含三个类：Pattern, Matcher 和 PatternSyntaxException.
一个Pattern对象是一个编译了的正则表达式形式。Pattern类不提供公共的构造函数。要创建一个pattern，你必须调用一个公共静态的编译方法，然后返回一个Pattern对象。
一个Mather对象是解释pattern并对输入字符串执行匹配操作的引擎。像Pattern类一样，Matcher没有定义公共的构造函数。你可以通过在Pattern对象中调用公共的匹配方法来得到一个Matcher实例。
一个PatternSyntaxException对象是一个找到正则表达式有语法错误的未检查的异常。
例子(从参考[4]上抄的):
Pattern pattern;
Matcher matcher;
pattern = Pattern.compile(<REGEX>);
matcher = pattern.matcher(<INPUT>);
boolean found;
while(matcher.find()) {
System.out.println(“Found the text \”" + matcher.group() + ”\” starting at index ” + matcher.start() + ” and ending at index ” + matcher.end() + ”.”);
found = true;
}
if(!found){
System.out.println(“No match found.”);
}
Java String 类中也提供了下列方法：
boolean matches(String regex) 返回当前字符串是否匹配正则表达式regex
String replaceAll(String regex,String replacement) 返回一个字符串，该字符串是用replacement替换掉当前字符串中所有匹配表达式regex的字串。
String replaceFirst(String regex, String replacement) 返回一个字符串，该字符串是用replacement替换掉当前字符串中第一个匹配表达式regex的字串。
String[] split(String regex) 从匹配regex的子串上断开，将当前字符串分割未若干子串.
C++语言
许多Topcoder成员相信在tc赛场上正则表达式是Java相较于C++的一个强大的优势。但C++程序员不必因此绝望，因为正则表达式也可以在C++里使用。
有很多的C++的正则表达式解释库可以用，不幸的是，它们不是很兼容。但幸运的是，作为一个tc赛场上的成员，我们不需要应付这么多的互不兼容的库。如果你打算在比赛中用正则表达式，你只需要在POSIX_regex和GNU_regex两个API中选择其中一个即可。要使用这些API，头文件”regex.h”必须包含。它们都需要进行两个步骤：先通过一个函数调用来编译正则表达式，然后通过另外一个函数调用使用编译好的正则表达式来搜索或者匹配一个字符串。
下面是两个API的简短的描述，喜欢哪一个由你自己来决定了。
POSIX_regex
包含对两种不同的正则表达式语法的支持—基本的和扩展的。基本的正则表达式类似于ed的语法；扩展的正则表达式更像egrep中的，增加了’|’,’ +’和’?’运算符，不需要在括号里的子表达式或者大括号里的范围加反斜杠。基本的是默认的，但是更多人喜欢扩展的正则表达式。
你可以通过POSIX搜索一个给定的正则表达式，你不能够匹配她。要实现搜索，你必须先在一个模式缓冲区中用’regcomp’编译她。表达式编译到了模式缓冲区之后，你可以在一个null结尾的字符串中使用’regexec’搜索该模式。如果’regcomp’或者’regexec’函数执行失败，她们会返回错误代码。你可以用’regerror’来获取错误信息。你必须用’regfree’来释放为模式缓冲区分配的内存。
可以从参考目录[2][3]中获取这些函数使用方法的深入描述。
例子：
下面是一段展示如何使用这些函数的代码片段：
regex_t reg;
string pattern = ”[^tpr]{2,}”;
string str = ”topcoder”;
regmatch_t matches[1];
regcomp(®,pattern.c_str(),REG_EXTENDED|REG_ICASE);
if (regexec(®,str.c_str(),1,matches,0)==0) {
cout << ”Match ”
cout << str.substr(matches[0].rm_so,matches[0].rm_eo-matches[0].rm_so)
cout << ” found starting at: ”
cout << matches[0].rm_so
cout << ” and ending at ”
cout << matches[0].rm_eo
cout << endl;
} else {
cout << ”Match not found.”
cout << endl;
}
regfree(®);
GNU_regex
GNU_regex的API有更丰富的函数。你可以用她来匹配一个字符换或者在一个字符串中模式搜索。这些函数的使用方法类似于POSIX提供的函数的使用方法：首先必须用’re_compile_pattern’来编译模式，获取用于搜索和匹配的的模式缓冲区。搜索和匹配的函数分别是’re_search’和’re_match’。如果是搜索的话，一个fastmap可以用来优化搜索速度。没有fastmap，搜索算法试图在字符串中一些连续的位置匹配模式。Fastmap告诉算法一个匹配可以从那个字符开始。Fastmap可以用’re_compile_fastmap’来构造。GNU_regex同时提供了’re_search’和’re_match2’函数用于搜索和匹配一段数据。你必须用’regfree’来释放为模式缓冲区分配的内存。
可以从参考目录[3]中获取这些函数使用方法的深入描述。
例子：
string pattern = ”([a-z]+).\\1″;
string str = ”top-topcoder|coder”;
re_pattern_buffer buffer;
char map[256];
buffer.translate = 0;
buffer.fastmap = map;
buffer.buffer = 0;
buffer.allocated = 0;
re_set_syntax(RE_SYNTAX_POSIX_EXTENDED);
const char* status = re_compile_pattern(pattern.c_str(),pattern.size(),&buffer);
if (status) {
cout << ”Error: ” << status << endl;
}
re_compile_fastmap(&buffer);
struct re_registers regs;
int ofs = 0;
if (re_search(&buffer,str.c_str(),str.size(),0,str.size(),®s)!=-1) {
cout << ”Match ”
cout << str.substr(regs.start[0],regs.end[0]-regs.start[0])
cout << ” found starting at: ”
cout << regs.start[0]
cout << ” and ending at ”
cout << regs.end[0]
cout << endl;
} else {
cout << ”Match not found.”
cout << endl;
}
regfree(&buffer);
真实的SRM范例
为了明确起见，下面的例子都是用Java写的。一个C++使用者可以用POSIX或者GNU正则表达式API来构造同Java类似的函数(replace_all, split, matches).
CyberLine (SRM 187 div 1, level 1)
import java.util.*;
public class Cyberline
{
public String lastCyberword(String cyberline)
{
String[]w=cyberline.replaceAll(“-”,”")
.replaceAll(“[^a-zA-Z0-9]“,” ”)
.split(“ ”) ;
return w[w.length-1];
}
}
UnLinker (SRM 203 div 2, level 3)
import java.util.*;
public class UnLinker
{
public String clean(String text)
{
String []m = text.split(“((http://)?www[.]|http://)[a-zA-Z0-9.]+[.](com|org|edu|info|tv)”,-1);
String s = m[0] ;
for (int i = 1 ; i < m.length ; ++i)
s = s + ”OMIT” + i + m[i] ;
return s ;
}
}
CheatCode (SRM 154 div 1, level 1)
import java.util.*;
public class CheatCode {
public int[] matches(String keyPresses, String[] codes) {
boolean []map = new boolean[codes.length] ;
int count = 0 ;
for (int i=0;i<codes.length; ++i)
{
String regex = ”.*” ;
for (int j=0; j<codes[i].length(); ) {
int k = 1;
while ((j+k)<codes[i].length() && codes[i].charAt(j+k)==codes[i].charAt(j)) k++;
regex = regex + codes[i].charAt(j) + ”{“+k+”,}”;
j+=k;
}
regex = regex + ”.*” ;
if (keyPresses.matches(regex))
{
map[i] = true ;
count++ ;
}
}
int []res = new int[count] ;
int j=0;
for (int i= 0 ; i < codes.length; ++i)
if(map[i] == true)
res[j++]=i ;
return res ;
}
}
1. The regex(7) linux manual page
2. The regex(3) linux manual page
3. http://docs.freebsd.org/info/regex/regex.info.Programming_with_Regex.html
4. http://www.regular-expressions.info/
5. http://java.sun.com/docs/books/tutorial/extra/regex/
(本文pdf下载地址: http://acm.hust.edu.cn/download/regex.pdf)