用于查找最多n个连续模式的正则表达式

Question

让我们说我们的模式是大写字母的正则表达式(但我们可能有比搜索大写更复杂的模式)

至少要找到 n个连续模式(在这种情况下,我们正在寻找的模式只是一个大写字母),我们可以这样做:

(使用Ruby)

somestring = "ABC deFgHij kLmN pQrS XYZ abcdEf"

at_least_2_capitals = somestring.scan(/[A-Z][A-Z]+/)
=> ["ABC", "XYZ"]
at_least_3_capitals = somestring.scan(/[A-Z]{3}[A-Z]*/)
=> ["ABC", "XYZ"]

但是,如何搜索最多 n个连续模式,例如,最多连续一个大写字母:

matches = somestring.scan(/ ??? /)
=> [" deFgHij kLmN pQrS ", " abcdEf"]

---

详细的策略

我读到我需要否定"至少"正则表达式,将其变为DFA,否定接受状态,(然后将其转换回NFA,尽管我们可以保留原样),所以将其写为正则表达式.如果我们将我们的模式看作接收'1'并且没有接收到接收'0'的模式,我们可以绘制一个简单的DFA图(其中n = 1,我们最多想要一个模式):

具体来说,我想知道这是如何成为一个正则表达式.一般来说,我希望找到如何用正则表达式找到"最多",因为我的正则表达式技能感到特别"至少"单独发痒.

---

旅行危险 - 在精神上不是正确的解决方案

请注意,这个问题不是这篇文章的重复,因为使用公认的方法会给出:

somestring.scan(/[A-Z]{2}[A-Z]*(.*)[A-Z]{2}[A-Z]*/)
=> [[" deFgHij kLmN pQrS X"]]

这不是DFA所展示的,不仅仅是因为它错过了第二次寻求的匹配 - 更重要的是,它包括'X',它不应该,因为'X'后面是另一个资本,而且从DFA我们看到一个资本,其次是另一个资本,不是接受国.

你可以建议

somestring.split(/[A-Z]{2}[A-Z]*/)
=> ["", " deFgHij kLmN pQrS ", " abcdEf"]

(感谢橡皮鸭)

但我仍然想知道如何仅使用正则表达式找到最多n次出现.(知识!)

Answer 1

为什么你的尝试不起作用

您当前的尝试存在一些问题。

1. X作为匹配的一部分的原因是它.*是贪婪的并且消耗尽可能多的 - 因此，只留下所需的两个大写字母来与尾随位匹配。这可以通过非贪婪量词来解决。
2. 您没有获得第二场比赛的原因是双重的。首先，您需要有两个尾随大写字母，但实际上是字符串的结尾。其次，比赛不能重叠。第一个匹配至少包含两个尾随大写字母，但第二个匹配需要在开始时再次匹配这些字母，这是不可能的。
3. 还有更多隐藏的问题：尝试使用四个连续大写字母的输入 - 它可能会给你一个空匹配（假设你使用非贪婪量词 - 贪婪量词有更糟糕的问题）。

用当前的方法修复所有这些问题是很困难的（我尝试过但失败了 - 如果您想查看我的尝试，请检查这篇文章的编辑历史记录，直到我决定完全放弃这种方法）。那么让我们尝试一些别的东西吧！

寻找另一种解决方案

我们想要匹配什么？忽略边缘情况，即匹配从字符串的开头开始或在字符串的结尾结束，我们希望匹配：

(非大写) 1 个大写 (非大写) 1 个大写 (非大写) ... .

这非常适合 Jeffrey Friedl 的展开循环。看起来像

[^A-Z]+(?:[A-Z][^A-Z]+)*

现在边缘情况又如何呢？我们可以这样表述它们：

1. 我们希望在匹配的开头允许有一个大写字母，前提是它位于字符串的开头。
2. 我们希望在匹配的末尾允许有一个大写字母，前提是它位于字符串的末尾。

要将这些添加到我们的模式中，我们只需将大写字母与适当的锚组合在一起，并将两者标记为可选：

(?:^[A-Z])?[^A-Z]+(?:[A-Z][^A-Z]+)*(?:[A-Z]$)?

现在它真的起作用了。更好的是，我们不再需要捕获了！

概括解决方案

该解决方案很容易推广到“至多n个连续大写字母”的情况，通过将每个字母更改[A-Z]为[A-Z]{1,n}，从而允许n最多大写字母，而目前只允许一个大写字母。

请参阅 的演示n = 2。