请教到底如何真的掌握“正则表达式”以及人和人的认知差距真的会有这么大吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1165 天前的主题，其中的信息可能已经有所发展或是发生改变。

昨晚入睡前，搜 Twitter 上关于“正则”的推文，突然看到有个人发了一条推，问了一个关于正则表达式写法的问题，问题原文是：“匹配一个字符串，其由且仅由偶数个 0 和奇数个 1 组成，不论顺序。”，我当时很惊讶，正则还能拿来进行这种奇数个或者偶数个字符出现的次数的吗，看了一下回复，真的有不少人给出了他们的答案，其中有一条回复很简短，正则表达式如下：(?=^1*((01*){2})$)(^([01]{2})[01]$)。经过实测，结果是符合提问者要求的。这次我真的被震惊到，真的是天外有天人外有人，当我以为自己对正则的写法略懂还在沾沾自喜的时候，其他人更是随随便便就写了一条如果我不用工具就测试不出来是否正确的表达式。他到底是怎么想到的，甚至在我用工具进行测试，再对表达式的字符逐个进行分析，还是不觉得自己真理解这样的写法为什么就能达到提问者的要求。这让我的挫败感更加深了。

大家如果只看这个正则的问题，也都能很容易地写出来符合要求的表达式吗？

第 1 条附言 · 2021-09-25 04:19:17 +08:00

主贴中，复制表达式的时候出错了。

实际应该是下面这个：

(?=^1*((01*){2})*$)(^([01]{2})*[01]$)

写法

正则

提问者

字符

31 条回复 • 2021-09-26 07:55:42 +08:00

hackyuan

2021-09-25 00:32:37 +08:00

不能轻易写出来，小部分时候愿意尝试一些有意思的正则问题，但更多时候选择用更简单的代码解决。

另外，复杂正则的效率似乎也不是很高？

ila

2021-09-25 00:50:06 +08:00 via Android

业务需求。
想想让你难忘而且被实现的需求。

0ZXYDDu796nVCFxq

2021-09-25 00:59:15 +08:00

这种数学关系的，稍微复杂一点的条件，正则就不行了

CEBBCAT

2021-09-25 00:59:31 +08:00

那个……V2 贴代码请善用 Markdown 或 Github Gist 功能

autoxbc

2021-09-25 02:12:47 +08:00

「每次你用正则解析序列化的结构数据，就是重新写了一次这种数据结构的解析器」

每次想写一个常人难以理解的正则时问问自己，你是解析器的作者吗，不是的话，用别人写好的解析器

每次想写一个常人难以理解的正则时问问自己，你喜欢读复杂的正则吗，不是的话，其他人也不喜欢

pinepara

2021-09-25 02:31:06 +08:00

从实际应用上看，这不是一个适合用正则表达式解决的问题。再强调一遍：

**这不是一个适合用正则表达式解决的问题**。

但是如果非要用正则解决，不失为一个有趣的练习。
1. 首先要指出的是题主给出的答案是错误，很容易验证： https://regexr.com/669d1
2. 所谓的『认知差距』可能主要是对数学思想的熟悉和熟练程度。具体到这个问题上，关键思想无非是把一个复杂的未知问题转化为一个或多个简单的已知问题。下面我来尝试一下：

题目要求是判断一个字符串『是否仅由偶数个 0 和奇数个 1 组成，不论顺序。』（不论顺序后略）

该条件等价于『由偶数个 0 和任意数量的 1 组成』且
『由奇数个 1 和任意数量的 0 组成』。

由此可以将原问题转化为三个子问题：
1. 如何判断一个字符串是否『由偶数个 0 和任意数量的 1 组成』
2. 如何判断一个字符串是否『由奇数个 1 和任意数量的 0 组成』
3. 如何判断一个字符串同时满足 1. 和 2.

首先解决问题 1：如何判断一个字符串是否『由偶数个 0 和任意数量的 1 组成』，这部分很简单，根据偶数的定义可以再次转化为『任意多个 1，加上由两个 0 和任意数量的 1 组成的小节重复任意多次』，写出如下正则表达式：

```
^1*(01*01*)*$
```

问题 1 解决之后再来看问题 2 『由奇数个 1 和任意数量的 0 组成』就会发现它等价于『至少包含一个 1，且去掉第一个 1 剩下的部分由偶数个 1 和任意数量的 0 组成』，后半段子命题完全同构于问题 1，唯一的区别是 0 和 1 在子命题里被互换了。不做赘述，正则表达式如下：

```
^0*10*(10*10*)*$
```

最后是问题 3：如何判断一个字符串同时匹配两个正则表达式，而且这两个正则都是精确匹配。这个问题没有什么技巧可言，熟悉正则表达式的断言的话的话可以轻松写出同时满足 `EXPRESSION_A` 和 `EXPRESSION_B` 的表达式：

```
(?=^<EXPRESSION_A>$)^<EXPRESSION_B>$
```

综合上述三个问题及其解答，可以得出最终满足题意的表达式：

```
(?=^(1*01*01*)*$)(?=^0*1(0*10*10*)*$)
```

可以自行验证： https://regexr.com/669bq

pinepara

2021-09-25 02:35:05 +08:00

@pinepara 不好意思最终答案出现了复制失误，应该是：

(?=^1*((01*){2})$)(^([01]{2})[01]$)

另外 V2EX 不支持 Markdown ？

pinepara

2021-09-25 02:35:44 +08:00

@pinepara 再次失误……应该是

(?=^1*(01*01*)*$)^0*10*(10*10*)*$

laydown

2021-09-25 03:03:33 +08:00

@pinepara 厉害，学习到了。的确，后来我也有反思，只用正则来解决似乎就是太为难自己了。尴尬，之前的那个表达式确实有遗漏。

MegrezZhu

2021-09-25 03:13:54 +08:00

根据我所剩无几的编译原理知识，正则似乎是 context-free 的？那它天然不太适合做这种 context sensitive 的事……或许现在的正则表达式实现加了许多其他的 feature 吧

wudicgi

2021-09-25 04:02:49 +08:00

这个不要光看正则表达式这么短，真要处理起来，这种需求就逐字符过一遍就搞定了，效率高代码还易读

laydown

2021-09-25 04:15:45 +08:00

@pinepara 我才注意到，原来的表达式不是那样的，在主题贴里复制过后，将星号都省略掉了。。
原来的如下（不知道这次有没有搞正确）：

> (?=^1*((01*){2})*$)(^([01]{2})*[01]$)

laydown

2021-09-25 04:17:35 +08:00

@CEBBCAT 感谢提醒，还真的复制过后，主贴里的表达式出错了。难怪部分字符是斜着的……

pinepara

2021-09-25 04:25:48 +08:00 via iPhone

@laydown 这个看起来依然有问题。但是可以确定思路是一样的，可以自行分析验证。

kidding

2021-09-25 06:09:08 +08:00

想起之前学有限状态机的时候...作业基本都是这种东西。
所以遇到这种问题的时候会在脑袋里想一下 FSM 的画法，而正则和 FSM 又是等价的，所以大概就知道 RegEx 能不能写出来了。

但问题又来了，我现在又不是在上这门课，明明有更简单易懂的方法干嘛要写正则为难自己。

O5oz6z3

2021-09-25 08:21:54 +08:00

跑个题，其他人未必随便吧，不是古语云台上十分钟

learningman

2021-09-25 08:41:49 +08:00 via Android

@MegrezZhu 有上下文相关的扩展。

Tink

2021-09-25 09:25:54 +08:00 via Android

这个真的有点牛逼

pkookp8

2021-09-25 11:26:46 +08:00 via Android

正则的知识一直停留在基础中的基础
主要用来过滤，替换一些特定文字
真遇到了 ip，mac 的判断，我还是老老实实的写代码。
主要为了易读
像楼主给的正则，说实话，写出来也很少人(至少我不懂)看得懂
但是如果翻译成任意程序语言，大概 90%以上的人能看懂

pkookp8

2021-09-25 11:28:00 +08:00 via Android

@pkookp8 不过每次看到别人给出一个题目，然后有人能写出正则
总是佩服，心里会感叹，这 tm 也能用正则搞定，好牛逼

nlzy

2021-09-25 12:51:30 +08:00 via Android

这题也可以看成是 DFA 的典型例题，就像 #15 说的：“作业基本都是这种东西”。而 DFA 和正则表达式可以互相转换，所以构造出 DFA 再一步步转成正则就可以做出来了。

我做了做，得到了 ^(0(11)*0)*(1|01(11)*0)(0(11)*0)*((1|01(11)*0)(0(11)*0)*(1|01(11)*0)(0(11)*0)*)*$

最后的结果我自己也看不懂，这只是我机械地套用公式得到的，所以楼主没必要为看不懂这些正则而灰心丧气啦。

ch2

2021-09-25 12:59:53 +08:00

@MegrezZhu #10 不，正则表达式比 context-free 能力更弱

ipwx

2021-09-25 14:45:24 +08:00

@ch2 DFA 还好。一旦用上比如贪婪或者前项断言，正则就会变成 NFA，那效率就 hhhh

agagega

2021-09-25 17:06:29 +08:00

很正常。

中学和大学学数学物理的时候，我一直有种强烈的感觉：课本上学的和题目里的是两个东西。书上讲的是什么叫不等式，什么叫微分积分。但作业里的习题本质上考验的是另一种东西，只不过套上了不同知识的皮。你要么知道这个「另一种知识」，要么足够聪明能自己悟出来，否则学了书本也没有用。

WuSiYu

2021-09-25 19:31:57 +08:00

DFA 手推版：^(0(11)*0)*(01(11)*0|1)((0(11)*0)*|(0(11)*10|1)(0(11)*0)*(01(11)*0|1))*$
也就是形式语言中的正则表达式（只有乘、加、闭包、括号），可见和工业界的 regex 还是有比较大的风格差异
性能角度，DFA 理论上是更快的，不过在上班我肯定写个 for

ecnelises

2021-09-25 19:32:51 +08:00

前面用到了额外断言的答案比较好理解。解释一下楼上面这个答案吧：

^(0(11)*0)*(1|01(11)*0)(0(11)*0)*((1|01(11)*0)(0(11)*0)*(1|01(11)*0)(0(11)*0)*)*$

如果让 X=(0(11)*0), Y=(1|01(11)*0)，那么整个其实是 X*YX*(YX*YX*)* （开头结尾的符号省略了，不影响理解），而这个的意思其实是出现奇数个 Y 间隔任意个 X.

为什么 X 可以随意出现呢？因为 X 一定代表了偶数多个 0 和 1，无论是我们想要的奇数个 1 还是偶数个 0，减去偶数个 0 和偶数个 1 都没关系。Y 也不难理解了，因为穷举了所有奇数个 1 出现的情况。奇数个 1 出现奇数次还是奇数，所以满足要求。