logo标签列表

使用反向引用实现按字母顺序排序的正则表达式

regexbackreferencecharacter-class
7

我最近遇到了一个谜题，需要找到一个正则表达式来匹配：

由小写英文字母组成的长度为5个字符的字符串，ASCII码按升序排列

有效的例子包括：

aaaaa
abcde
xxyyz
ghost
chips
demos

无效的示例包括：

abCde
xxyyzz
hgost
chps

我的当前解决方案很笨拙。我使用正则表达式：

(?=^[a-z]{5}$)^(a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*)$

使用非捕获分组来断言字符串长度为5，并验证该字符串由小写英文字母按顺序组成（请参见Rubular）。
相反，我想在字符类中使用回溯引用。例如：
^([a-z])([\1-z])([\2-z])([\3-z])([\4-z])$

我的解决方案的逻辑（请参见Rubular）是捕获第一个字符[a-z]，将其用作第二个字符类中的反向引用，以此类推。然而，在字符类中使用\1，\2等似乎是指ASCII值1、2……有效匹配任何四或五个字符的字符串。

我有两个问题：

  1. 我能在我的字符类中使用反向引用来检查升序字符串吗？
  2. 有没有更少hacky的解决这个难题的方法？
3
据我所知，你的临时解决方案已经达到了最好的效果，因为字符类与反向引用不兼容（但我很喜欢你的逻辑，似乎是一个好的功能）。你有特定的环境来运行这个正则表达式吗（只在 Ruby 或者通用的）？我相信 Stack Overflow 上的正则表达式专家们很快就会加入讨论并提供他们的专业意见。 - mickmackusa
2
哦，字符类中没有反向引用。原因是字符类在编译时组成。决定因素是反向引用是动态的，而在类内部不合格的是范围运算符。所以，他们说.. 没有动态范围 否则引擎会在 C++ 异常中崩溃。 - user557597
1
我遇到了一个谜题，需要寻找一个正则表达式。请确保引用该链接，以便我们能够嘲笑解谜者。 - user557597
1
好的，你的正则表达式看起来相当不错。可以稍微改进一下，使用：^(?=[a-z]{5}$)a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$。 - anubhava
1
重复的https://dev59.com/znA75IYBdhLWcg3wqK__。 - A1m
显示剩余4条评论
4个回答
4
我将以评论的形式发布此答案，而不是作为答案，因为它比评论具有更好的格式。
关于您的问题：
1. 我可以在字符类中使用反向引用来检查升序字符串吗？
不行。如果您查看backref regular-expressions部分，您会发现以下文档：
括号和反向引用不能在字符类中使用 括号不能在字符类中使用，至少不能作为元字符。当您在字符类中放置括号时，它被视为字面字符。因此，正则表达式[(a)b]匹配a、b、(和)。
反向引用也不能在字符类中使用。像(a)[\1b]这样的正则表达式中的\1要么是一个错误，要么是一个不必要的转义字面值1。在JavaScript中，它是一个八进制转义符。
关于您的第二个问题：
  1. 有没有更好的解决方案？

我的看法是，你的正则表达式已经很好了，你可以在开头稍微缩短一下，像这样：

(?=^.{5}$)^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$
    ^--- Here

正则表达式演示

1
我认为值得说明的是，为什么字符类中的反向引用是不可能的。反向引用可以指向匹配的子字符串，这个子字符串可以是任意长度，甚至可以为空。因此，像[\1-z]这样的代码可能会产生[-z]、[f-z]、[foo-z]等结果。这并没有太多意义，而且模式必须在运行时重新编译，从而防止优化。 - Lucas Trzesniewski
1
当看到文档引用时，如果它们没有提供某些基本用法不能使用的原因，这是令人不安的。字符类内的引用就是一个例子。但是，您始终可以为这种情况使用自己的推理，并且在这种情况下很容易知道原因。 - user557597
3
如果你愿意使用Perl(!)，这个代码可以实现：
/^([a-z])((??{"[$1-z]"}))((??{"[$2-z]"}))((??{"[$3-z]"}))(??{"[$4-z]"})$/
1
但是...那是作弊！ :) 如果您使用Perl，那么我想您可以直接编写断言：/^([a-z]{5})$(?(?{$1 eq (join "", sort split qr##, $1)})|(?!))/ - Lucas Trzesniewski
在某些时候，我认为你是否正在使用正则表达式解决方案是值得怀疑的。我认为我的解决方案更接近于连续性 :) - NetMage
2
啊，好的，这是一个有限集合，因此您可以始终使用交替方式列举它！这会在一个小的Perl REPL中发出一种“暴力”的正则表达式：
#include <stdio.h>

int main(void) {
  printf("while (<>) { if (/^(?:");
  for (int a = 'a'; a <= 'z'; ++a)
    for (int b = a; b <= 'z'; ++b)
      for (int c = b; c <= 'z'; ++c) {
        for (int d = c; d <= 'y'; ++d)
          printf("%c%c%c%c[%c-z]|", a, b, c, d, d);
        printf("%c%c%czz", a, b, c);
        if (a != 'z' || b != 'z' || c != 'z') printf("|\n");
      }
  printf(")$/x) { print \"Match!\\n\" } else { print \"No match.\\n\" }}\n");
  return 0;
}

现在：

$ gcc r.c
$ ./a.out > foo.pl
$ cat > data.txt
aaaaa
abcde
xxyyz
ghost
chips
demos
abCde
xxyyzz
hgost
chps
^D
$ perl foo.pl < data.txt
Match!
Match!
Match!
Match!
Match!
Match!
No match.
No match.
No match.
No match.

正则表达式只有大约220Kb大小;-)
啊，你的正则表达式把 Rubular 弄崩了（无法创建永久链接）。:-) 是的，它是 219 KB 原始数据，而且有效！ - Jedi
谢谢。我使用了来自@Jedi粘贴板的原始正则表达式文本，并将其通过这个三元工具进行了处理，制作了一个完整的正则表达式字典树。这大大减小了大小（160k 压缩，840k 格式化）。这里是一个Python测试。 - user557597
1
另外，我生成了全部的142,506个可能字符串，然后使用我制作的完整trie正则表达式来测试性能： Regex1: <省略> 选项：<无> 完成迭代：1/1（x 1） 每次迭代找到的匹配项：142506 经过时间：0.18秒，178.87毫秒，178871微秒 - user557597
2

由于有人已经使用 Perl 打破了僵局，因此我猜这是一个 Perl 解决方案...

请注意，这是一种基本的非正则表达式解决方案，恰好被塞入了 Perl 正则表达式的代码结构中。
有趣的是，如果某天您需要正则表达式/代码的协同作用，那么这是一个不错的选择。
到时候，您可能会使用一个非常复杂的模式代替简单的 [a-z] 字符，并使用与上一个字符的比较。
这就是威力所在！！

正则表达式：^(?:([a-z])(?(?{ $last gt $1 })(?!)|(?{ $last = $1 }))){5}$

Perl 代码

use strict;
use warnings;


$/ = "";

my @DAry = split /\s+/, <DATA>;

my $last;

for (@DAry)
{
    $last = '';
    if ( 
      /
         ^                             # BOS
         (?:                           # Cluster begin
              ( [a-z] )                     # (1), Single a-z letter
                                            # Code conditional
              (?(?{
                   $last gt $1                  # last > current ?
                })
                   (?!)                          # Fail
                |                              # else,
                   (?{ $last = $1 })             # Assign last = current
              )
         ){5}                          # Cluster end, do 5 times
         $                             # EOS
      /x )
    {
        print "good   $_\n";
    }
    else {
        print "bad    $_\n";
    }
}

__DATA__

aaaaa
abcde
xxyyz
ghost
chips
demos
abCde
xxyyzz
hgost
chps

输出

good   aaaaa
good   abcde
good   xxyyz
good   ghost
good   chips
good   demos
bad    abCde
bad    xxyyzz
bad    hgost
bad    chps
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接