GingerBear
快速攻陷正则表达式
说实话，应该说正则表达式在面试的时候比较少碰到，不是刷题的重点。但本着 “打好基础” 的精神，快速攻破这个 “看似牛逼，其实不难，又很有用” 的东西能够填补上我们知识上的漏洞，如果在面试时能用到，一定会加分不少。正则表达式也是Steve Yegge的技术面试题的五个大方向的一个大方向。
下面摘自Google工程师徐宥的这篇博客编程珠玑番外篇-C.正则表达式精义-1
正则表达式是什么?为啥会有这个东西？
正则表达式是一种描述性的语言, 用来概括一类字符串 (或者说一个字符串集合). 我们当然可以用自然语言来描述一类字符串, 比如我们说,
- 以 “010 开头的电话号码”,
- “夹在HTML 的 和 中间的内容”,
- “含有 hello 的字符串”,
- “负数”,
- “IP地址”
- “邮箱地址”, 等等.
最基本的正则表达式, 只有三句话:
一个字符串是一个正则表达式, 比如 aaa, 就是一个正则表达式, 它描述了一个字符串集合, 这个字符串集合里面只有 aaa 这一个元素
两个正则表达式可以直接串起来, 比如 aaabbb 其实, 是由六个正则表达式 a a a b b b 接起来组成的. 我们先笼统的说, 接起来就等于把描述的内容接起来, 等一下再详细解释接起来的含义.
两个字符串, 比如 aaa 和 bbb, 用 | 连起来, 变成了 aaa|bbb, 也构成一个正则表达式, 它描述的字符串集合是原来分别的并集, 比如 aaa|bbb 描述了一个集合, 这个集合里面有 {aaa, bbb} 两个字符串.
好了, 就这两三话, 就可以解释正则表达式最基本的思维方式了: 用一个表达式, 去描述一类字符串(或者说, 一个集合)
拓展开
光有这两个, 还不够强大, 因为上面的正则表达式, 我写几个, 就描述了几个字符串, 也就是说, 描述来, 描述去, 都是有限的集合, 不能描述无限的集合. 而我们想要描述的整数啊, 域名啊, 邮箱地址啊, 都是一切就有可能的, 因此, 我们有必要引入一个新的记号, 能够描述无限的集合,
一个正则式 X 可以加上一个 *, 用来描述任意多个原来 X 描述的字符串拼起来的字符串.
这句话比较费解, 我们用例子来说明一下, 比如 a* 这个正则表达式, 我们知道 a 描述了一类字符, 这类字符里面只有一个 a, 所以, a* 描述了一个或者多个 a.
我们再看 a | b* , 按照定义, 这个正则表达式描述了 a 和 b, bb, bbb 等. 如果我们引入一个括号, 写成 (a|b)* , 那么 a|b 就变成一个整体, 描述了 a 或者 b, 这时候, (a|b)* 就是一切只由 a, b 组成的字符串. 这里的括号, 是为了避免歧义, 表示 * 是作用在 a|b 整体上的. 这时候, (a|b) 描述了 a 和 b, 整体加了一个 , 意味者我们可以任意选 a 或者 b 一个接一个拼起来, 所以, aba, aab 都是在 (a|b) 的那一类里面的. 注意, * 可以匹配 0 个, 就是说, 这里面包含了什么都没有. 比如说 ab_c 也描述了 ac, 因为中间可以有 0 个 b. 如果您想至少要一个b, 可以写成 abb_c.
为了帮助您理解接起来, 我们再看一个复杂的例子, o(n|ff). 我们知道, n|ff 描述了 n 或者 ff. 当我们直接把 o 接在前面的时候, 描述的是 on 或者 off. 就是说, 接起来的时候, 要把 o 和后面每种情况都组合一次. 我们再看 (a|o)(n|ff). 前面描述的是 a 或者 o, 后面描述的是 n 或者 ff, 接起来, 描述了 an, aff, on, off.
我们都知道, 正则表达式描述的是一类字符串, 所以, X 和 Y 在接起来变成 XY 以后, 自然的变成了描述 每一种 X 里面的字符串和 Y里面字符串接起来的情况. 同样, * 好像把 X 和自己接起来多次一样 (可以是任意次), 每次只要接起来的是X里面的字符串, 就一定被 X* 所表述.
(熟悉集合的朋友立即知道 正则表达式是用一个表达式代表了一个集合, X|Y 等价于两个集合的并集, 而 XY 拼起来等价于他们所有的元素 x, y 拼起来的集合).
好了, 恭喜您, 您已经学会正则表达式了
真的, 你已经全部学会了正则表达式的知识. 不过不着急, 我们先回顾一下正则表达式的要点:
- 正则表达式由普通的字符, 以及几个特殊的字符, 即 括号 (), 或者 | 和 星号 * 组成. 用来描述一类字符.
- | 表示或者. 如果有两个正则表达式 X 和 Y, 那么 X|Y 就描述了原来 X 描述的和 Y 描述的.
- 正则表达式可以接起来, 变成一个更长的, 描述了一个各个部分被那些被接起来的正则表达式描述的字符串.
- () 是为了避免歧义.
我们上面说的这四个, 就是 100% 如假包换的正则表达式了. 以后的, 都是为了更加方便的使用正则表达式, 而又引入的一些扩展. 恰恰是这些扩展, 让初学者陷入了细节的泥潭. 我们在下一节, 一个一个的来对付诸如 +, [, -, ], ^, $, {m}, 等这些非基本的高级的功能. 需要强调的是, 这些高级的功能, 其实都只是为了人书写方便, 而且是完全可以用我们这里说的最基本的几个规则代替的. 这些高级功能, 我们下节再讲.
练习
写出匹配以下性质字符串的正则表达式:
- 字符串 2009
- 周曙光同学有两个名字, 分别叫做 zola 和 zuola, 人们常常混淆. 请帮周曙光同学设计一个正则表达式, 可以帮他匹配自己的名字.
- 二进制数字 (最少有一位, 但只含有 0 或者 1的)
- 非零的十进制数字 (有至少一位数字, 但是不能以0开头)
练习软件
http://gskinner.com/RegExr/
练习文件
0108200920088964 zuola -d zooooola world hello -012012 2009 0909 zola zhou 0101001 zuola
注：把上面这段文本复制到软件里
答案
- 2009
- z(|u)ola [或者您可以写成 zuola|zola]
- (0|1)(0|1)*
- (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
你会看到第四题的答案很笨拙, 居然写了这么长. 后面的大部分细节, 就是为了诸如此类的写得更加简洁一点.
完全get这个技能
MDN里一篇很短的正则表达式的介绍，几乎就是正则表达式的全部（使用JavaScript）。Regular Expressions 喜欢看视频的话看这里Best of Fluent 2012: /Reg(exp){2}lained/: Demystifying Regular Expressions
回头再来试试Steve Yegge的技术面试题的五个大方向中正则表达式的练习
题目一
Last year my team had to remove all the phone numbers from 50,000 Amazon web page templates, since many of the numbers were no longer in service, and we also wanted to route all customer contacts through a single page.
Let's say you're on my team, and we have to identify the pages having probable U.S. phone numbers in them. To simplify the problem slightly, assume we have 50,000 HTML files in a Unix directory tree, under a directory called "/website". We have 2 days to get a list of file paths to the editorial staff. You need to give me a list of the .html files in this directory tree that appear to contain phone numbers in the following two formats: (xxx) xxx-xxxx and xxx-xxx-xxxx.
How would you solve this problem? Keep in mind our team is on a short (2-day) timeline.
题目二
Let's say you're on my team, and I've decided I'm a real stickler for code formatting. But I've got peculiar tastes, and one day I decide I want to have all parentheses stand out very clearly in your code.
So let's say you've got a set of source files in C, C++, or Java. Your choice. And I want you to modify them so that in each source file, every open- and close-paren has exactly one space character before and after it. If there is any other whitespace around the paren, it's collapsed into a single space character.
For instance, this code:
foo (bar ( new Point(x, graph.getY()) ));
Would be modified to look like this:
foo ( bar ( new Point ( x, graph.getY ( ) ) ) ) ;
I tell you (as your manager) that I don't care how you solve this problem. You can take the code down to Kinko's Copies and manually cut and paste the characters with scissors if you like.
How will you solve this problem?
想到一个小题：设计一个正则表达式，判断一个字符串是否满足
- 包含至少一个小写字母
- 包含至少一个大写字母
- 包含至少一个特殊符号
- 包含至少一个数字
- 长度至少6位，最多30位
今天做leetcode里面的Valid Number这道题时， 发现了使用正则表达式的高效之处。对于给定的一个string是不是valid number来说， 如果分别判断各种条件的话写起来代码量极大而且很容易漏判，但如果用正则表达式来解的话就方便太多了！把代码贴出来分享一下：
是的！
On Mon, Feb 24, 2014 at 5:38 PM, fordreamzzz [email protected]:
今天做leetcode里面的Valid Number这道题时， 发现了使用正则表达式的高效之处。对于给定的一个string是不是valid number来说， 如果分别判断各种条件的话写起来代码量极大而且很容易漏判，但如果用正则表达式来解的话就方便太多了！把代码贴出来分享一下： public class Solution { public boolean isNumber(String s) { if(s.trim().isEmpty()){
return false;
}
String regex = "[-+]?(\d+.?|.\d+)\d*(e[-+]?\d+)?";
if(s.trim().matches(regex)){
return true;
}else{
return false;
}
} }
— Reply to this email directly or view it on GitHubhttps://github.com/GingerBear/IS-Job-Hunting/issues/8#issuecomment-35948954 .
偶然间搜索到你的这个帖子，发现LZ应该我测试一下，最好找个2000行以上的测试用例吧，最好测试用例能包括邮箱，邮编，电话，各种进制等各类文本。我是初学，找练习题时刚好发现你的4个题目，第3，4题答案都严重有问题啊
