正则表达式有趣的应用 - 匹配字符数为2的n次幂的单词

Question

正则表达式有趣的应用 - 匹配字符数为2的n次幂的单词

3

嘿！

我一直在寻找关于正则表达式的反思主题。我想要一个正则表达式，可以匹配在单词列表中包含2^n个字符的所有单词（其中n是自然数）。

为了简单起见，我们假设一个单词只是一串“o”的序列。
同时，让我们假设这个列表由单词和它们包含的字符数以及空格分隔而成。
当然，你不能使用这些数字，这只是为了阅读方便！

例如，在以下列表中：
o (1) ooo (3) oooooo (6) oooo (4) ooooooooo (9) oo (2) oooooooooooo (12) oooooooo (8)

我们应该得到以下匹配结果：

matches : 'o', 'oo', 'oooo', 'oooooooo'

您的正则表达式必须遵守一些规则：

不能使用递归
不能使用任何特定于语言（或少数语言）的功能

如果您能够找到一个在JavaScript中有效的方法（或诀窍），那就太棒了（尽管我认为这是不可能的）！
当然，它不需要在JavaScript中工作。
解决问题并不是重点，我只关心如何解决它！

编辑：

不幸的是，没有人找到我要找的东西。这个问题仍然开放回答，一定有好的答案！

顺便说一句，这是我想出来的，尽管应该有更好的：

\b(?:o|(?:(?(1)\1|o)(?=((?(1)\1\1|o))))+\1)\b

演示在这里。

- Gawil

然而，这只是一个特例，如果有人找到一个没有任何技巧的JavaScript正则表达式，那将更加令人惊叹！;) 编辑：也许结尾有点不清楚，我会澄清一下^^ - Gawil

https://regex101.com/r/tzAg8D/1 虽然这显然是一个有限的范围；) - 所以 NAA。 - Sebastian Proske

1

我投票关闭此问题，因为它属于https://codegolf.stackexchange.com/。 - Toto

哦，太好了，那正是我正在寻找的，谢谢！我会去试试看。 - Gawil

我修改了我的评论：这正是我寻找学习正则表达式的网站，但这绝对不是发布当前问题的地方，因为它显然不是谜题或代码高尔夫挑战，而是一个真正的正则表达式问题。 - Gawil

显示剩余3条评论

3个回答

2

这个正则表达式适用于支持捕获组1至9的反向引用的大多数正则表达式引擎。但它只能捕获最多2^11=2048个“o”。

\bo{1,2}\b|\b(((((((((o{4})\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?\b

在这里进行测试（链接）

或者……我们可以硬编码 2^n 的数字；）

\b(?:o|oo|o{4}|o{8}|o{16}|o{32}|o{64}|o{128}|o{256}|o{512}|o{1024}|o{2048})\b

- LukStorms

我认为你误解了问题。这里得到的是o和2n个o的序列，而不是2^n个o ;) - Gawil

哈哈，没问题！你的正则表达式确实几乎能够工作，但是我想要一个适用于任何2的幂次方的正则表达式！ - Gawil

是的，但是如果没有递归，似乎无法创建一个通用的正则表达式，能够在几乎任何正则表达式引擎上工作。但你可能已经意识到了这一点。 - LukStorms

我知道这是可能的，因为我已经做到了 ;) 但是我使用条件语句，所以它并不通用... 我还没有发布它，因为我正在等待一些聪明的人找到一个我甚至想不到的绝妙解决方案 ^^ - Gawil

0

这里有一个证明，表明你无法使用常规语言或甚至是上下文无关文法来实现这一点: https://cs.stackexchange.com/questions/32338/show-that-0i-where-i-is-a-power-of-2-is-not-context-free

因此，我认为没有带有反向引用或任何复杂扩展的正则表达式是不可能创建的。

根据http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html，带有反向引用的正则表达式是NP完全问题，因此反向引用足以使正则表达式工作。

- Alistra

当然，这是不可能的，使用常规正则表达式。任何需要使用任何形式的存储器显然都不是普通的。然而，当我谈到正则表达式时，我正在使用语言滥用，就像今天几乎每个人所做的那样。 - Gawil

第二篇文章非常有趣，谢谢分享！ - Gawil

你说“不能使用递归”。如果你的意思是指回溯引用，那么这个任务就不可能完成。 - Alistra

我所说的“递归”是指递归正则表达式（例如包含 (?R) 或 (?1) 的正则表达式）。 - Gawil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Imanuel · Accepted Answer

我知道，你说过不要递归，但是为了记录一下：

\b(?:o|(o(?1)?o))\b

在regex101.com上测试

我们来分解一下（这样我就能够理解它为什么起作用了）！忽略空格。

\b (?: o | ( o (?1)? o ) ) \b
\b                         \b # Word boundaries. Boring.
   (?: o |               )    # Just so it matches a single o, too.
           ( o (?1)? o )      # Now that's the interesting part.
           (           )      # Capture group 1
             o       o        # Matches an o each at the start and the end of the group
                              # -> the pattern matches from the outside to the inside.
               (?1)?          # Again the pattern of group 1, or nothing.
                              # -> Again one 'o' at the start and one at the end. Or nothing.

说实话，我不知道为什么它不能通过两个递归将oooooo（6）与~~three~~匹配。

编辑：我在这里提出了一个关于此的新问题。