这个Java正则表达式如何检测回文？

Question

^{这是一系列教育正则表达式文章的第三部分.它遵循这个正则表达式如何找到三角形数字？(首先介绍嵌套引用)和如何将^ nb ^ n与Java正则表达式匹配？ (前瞻性"计数"机制进一步详述).这部分介绍了一种特定形式的嵌套断言,当与嵌套引用结合使用时,Java正则表达式可以匹配大多数人认为"不可能"的东西:回文!}

回文的语言是非常规的 ; 它实际上是无上下文的(对于给定的字母表).也就是说,现代正则表达式实现不仅仅识别常规语言,Perl/PCRE的递归模式和.NET的平衡组可以很容易地识别回文(参见:相关问题).

但是,Java的正则表达式引擎既不支持这些"高级"功能.然而"某人" ^(*wink*)成功编写了以下正则表达式,这似乎做得很好(参见ideone.com):

public class Palindrome {
    // asserts that the entirety of the string matches the given pattern
    static String assertEntirety(String pattern) {
        return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
    }

    public static void main(String[] args) {
        final String PALINDROME =
            "(?x) | (?:(.) add)+ chk"
                .replace("add", assertEntirety(".*? (\\1 \\2?)"))
                .replace("chk", assertEntirety("\\2"));

        System.out.println(PALINDROME);
        // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)

        String[] tests = {
            "",     // true
            "x",    // true
            "xx",   // true
            "xy",   // false
            "xyx",  // true
            "xxx",  // true
            "xxyx", // false
            "racecar",                // true
            "step on no pets",        // true
            "aManaPlanaCanalPanaMa",  // true
            "this is impossible",     // FALSE!!!
        };
        for (String test : tests) {
            System.out.printf("[%s] %s%n", test, test.matches(PALINDROME));
        }
    }
}

所以这似乎有效,但如何？

参考

• java.util.regex.Pattern
• regular-expressions.info/Freespacing(?x),Lookarounds (?=…)/(?<=…)等

---

常见的感觉警告!

这不是检测回文的最佳方法; 它O(N^3)充其量只是.以更通用的编程语言执行此检测既更有效又更直接.

您不希望使用正则表达式来检测回文,原因与您不想使用正则表达式查找素数相同.也就是说,您将研究非递归非平衡组正则表达式如何检测回文,原因与研究正则表达式如何用于素性测试的原因相同:它很有趣,有挑战性,有教育意义.

相关问题

• 如何使用正则表达式检查字符串是回文？- 不可能"!(除非...)
• 如何检查给定的字符串是否是回文？ - 许多语言的非正则表达式解决方案
• 如何确定一个数字是否是正则表达式的素数？

Answer 1

大图

我们将首先从整体大图算法中查看此正则表达式,然后稍后详细了解具体的实现细节.正则表达式几乎是以下Java代码的直接翻译:

static boolean isPalindrome(String s) {
   if (s.isEmpty()) {
      return true;
   }
   String g2 = null;
   for (char ch : s.toCharArray()) {
      String g1 = String.valueOf(ch);
      // "add"
      if (g2 != null && s.endsWith(g1 + g2)) {
         g2 = g1 + g2;
      } else if (s.endsWith(g1)) {
         g2 = g1;
      } else {
         break;
      }
   }
   return s.equals(g2); // "chk"
}

这显然不是检查回文的最直接/最有效的Java代码,但它有效,而且最令人着迷的是,它几乎可以通过近似一对一的映射直接转换为正则表达式.这里再次使用正则表达式,为方便起见,在此处复制,注释以突出显着的相似之处:

//  isEmpty  _for-loop_
//       ?  /          \
    "(?x) | (?:(.) add)+ chk"
//             \_/  ?
//             g1   loop body                   ___g2___
//                                             /        \
           .replace("add", assertEntirety(".*? (\\1 \\2?)"))
           .replace("chk", assertEntirety("\\2"));
                           // s.equals(g2)

附件: ideone.com上源代码的注释和扩展版本

(assertEntirety现在可以随意忽略细节:只需将其视为黑盒正则表达式机制,无论我们目前在哪里,都可以对整个字符串进行断言.)

所以基本的算法是我们尝试构建一个后缀,受一个回文约束,因为我们从左到右扫描字符串.然后我们检查我们是否能够以这种方式构建完整的字符串.如果可以的话,那么这个字符串就是一个回文.此外,作为特殊情况,空字符串通常是回文.

一旦理解了大图算法,我们就可以检查正则表达式模式如何实现它.

什么与所有String.replace？

Java中的正则表达式模式最终只是字符串,这意味着它们可以通过字符串操作以任何字符串的方式派生.是的,我们甚至可以使用正则表达式生成正则表达式模式 - 如果你愿意的话,这是一种元重复的方法.

考虑这个初始化int常量的例子(最终只包含一个数字):

final int X = 604800;
final int Y = 60 * 60 * 24 * 7;
// now X == Y

分配给的数字X是一个字面整数:我们可以清楚地看到数字是多少.这不是Y使用表达式的情况,但是这个公式似乎传达了这个数字代表什么的想法.即使没有对这些常量进行适当的命名,我们仍然认为Y可能代表一周内的秒数,即使我们可能不会立即知道数值是什么.另一方面,X我们确切地知道这个数字,但我们对它所代表的内容的了解较少.

在代码片段中使用字符串替换是类似的情况,但对于字符串正则表达式模式.而不是将模式明确地写为一个文字字符串,有时从较简单的部分中获得该值的系统和逻辑推导("公式")可能更有意义.对于正则表达式来说尤其如此,我们理解模式的作用往往比能够看到它看起来像字符串文字的东西更重要(无论如何都不是很好看,所有额外的反斜杠都是什么) .

为方便起见,此处再次复制了一部分片段:

// the "formula"
     final String PALINDROME =
        "(?x) | (?:(.) add)+ chk"
           .replace("add", assertEntirety(".*? (\\1 \\2?)"))
           .replace("chk", assertEntirety("\\2"));

// the "value"
     System.out.println(PALINDROME);
     //                       ____add_____             chk_
     //               _______/            \____   _______/ \_____
     // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)
     //        |  \_/             \______/     |
     //        |   1                 2         |
     //        |_______________________________|

毫无疑问,在这种情况下,"公式"比最终字符串"值"更具可读性.

有一些更复杂的方法可以以编程方式生成正则表达式模式,并且当然可以以这样的方式编写,即混淆而不是强调其含义,但是即使是简单的字符串替换也会有意思地使用它们(如希望这样显示)例).

课程:考虑以编程方式生成正则表达式模式.

add工作怎么样？

该(?:(.) add)+结构,其中add是做某种"计数"的说法,已经彻底在前面两个部分进行讨论.但值得注意的是两个功能:

• 所述(.)捕获到组1,允许反向引用稍后
• 断言assertEntirety不是仅仅展望我们目前的立场
  • 我们稍后会详细讨论这个问题; 只是把它想象成一种在整个字符串上断言的方法

施加到图案assertEntirety在add如下:

# prefix   _suffix_
#    ?    /        \
    .*?   ( \1 \2? )
#         \________/   i.e. a reluctant "whatever" prefix (as short as possible)
#          group 2          followed by a suffix captured into group 2

请注意,组2是自引用的,带有可选的说明符,这是本系列第2部分中已讨论过的技术.毋庸置疑,第2组是我们在这种模式中的"反击":它是一个后缀,我们将尝试在"循环"的每次迭代中向左增长.当我们(.)从左到右迭代时,我们尝试将相同的字符(使用反向引用\1)添加到我们的后缀.

再回想一下上面模式的Java代码翻译,为方便起见,这里转载:

if (g2 != null && s.endsWith(g1 + g2)) {   // \2? is greedy, we try this first
   g2 = g1 + g2;
} else if (s.endsWith(g1)) {    // since \2? is optional, we may also try this
   g2 = g1;
} else {        // if there's no matching suffix, we "break" out of the "loop"
   break;
}

\2?可选的事实意味着一些事情:

• 它为自我引用提供了"基本案例"(我们这样做的主要原因!)
• 由于\2?是后缀模式的一部分(因此在整个模式中稍后出现),前缀部分必须是不情愿的,因此.*?而不是.*.这可以\2?锻炼其贪婪.
• "计数器"也可以"重置"并给出"错误"的结果
  • 在第2部分中,我们展示了回溯如何?导致同样有问题的重置
    • 我们通过使用所有格量词解决了这个问题?+,但这不适用于此

第三点将在下一节进一步阐述.

课程:仔细分析模式部分中贪婪/不情愿重复之间的相互作用.

相关问题

• 之间的差异.*?和.*对正则表达式
• 正则表达:谁更贪婪？

为什么我们需要一个chk阶段？

如前一节所述,可选和可追溯\2?意味着我们的后缀在某些情况下会缩小.我们将逐步检查此输入的这种情况:

 x y x y z y x
?
# Initial state, \2 is "uninitialized"
             _
(x)y x y z y x
  ?
  # \1 captured x, \2 couldn't match \1\2 (since \2 is "uninitialized")
  #                but it could match \1 so it captured x
           ___
 x(y)x y z y x
    ?
    # \1 captured y, \2 matched \1\2 and grew to capture yx
             _
 x y(x)y z y x
      ?
      # \1 captured x, \2 couldn't match \1\2,
      #                but it could match \1 so it shrunk to capture x (!!!)
           ___
 x y x(y)z y x
        ?
        # \1 captured y, \2 matched \1\2 and grew to capture yx
         _____
 x y x y(z)y x
          ?
          # \1 captured z, \2 matched \1\2 and grew to capture zyx
       _______
 x y x y z(y)x
            ?
            # \1 captured y, \2 matched \1\2 and grew to capture yzyx
     _________
 x y x y z y(x)
              ?
              # \1 captured x, \2 matched \1\2 and grew to capture xyzyx

我们可以修改我们的模式(和相应的Java代码)以省略chk阶段,并看到确实发生了这种情况:

    // modified pattern without a chk phase; yields false positives!
    final String PALINDROME_BROKEN =
        "(?x) | (?:(.) add)+"
            .replace("add", assertEntirety(".*? (\\1 \\2?)"));

    String s = "xyxyzyx"; // NOT a palindrome!!!

    Matcher m = Pattern.compile(PALINDROME_BROKEN).matcher(s);
    if (m.matches()) {
        System.out.println(m.group(2)); // prints "xyzyx"
    }

如上所述"xyxyzyx",这不是一个回文,被错误地报告为一个,因为我们没有检查增长的后缀最终是否成为完整的字符串(在这种情况下它显然没有).因此,在我们的设置中,chk阶段(这是assertEntirety模式的一个阶段\2)是绝对必要的.我们需要确认我们确实设法一直增加后缀.如果是这种情况,那么我们自己就是一个回文.

课程:仔细分析可选的自引用匹配的任何可能无意的副作用.

主菜: assertEntirety

虽然我们可以编写一个Java正则表达式模式来检测回文,但这里的所有内容除了assertEntirety已经在本系列的前几部分中已经介绍过了.这里唯一新的东西就是这个神秘的黑盒子,这个强大的机制让我们神奇地允许我们去做"不可能"的事情.

该assertEntirety构造基于以下嵌套外观的元模式:

(?<=(?=^pattern$).*)

" 我可以在我身后的某个地方看到一个可以向前看的地方,看看 ^pattern$ "

"环顾四周 "这个名字意味着与我们当前职位的相对性:我们正在寻找我们周围,也许是在我们所站立的前方或后方.通过以这种方式在后视镜中嵌套前瞻,我们能够比喻"飞向天空"并查看整个画面.

将这个元模式抽象成assertEntirety有点像编写预处理替换宏.在任何地方嵌套的外观都可能会损害可读性和可维护性,因此我们将其封装到assertEntirety其中,这不仅隐藏了其内部工作的复杂性,而且还通过赋予其适当的名称来进一步强调其语义.

课程:考虑抽象元模式以隐藏复杂性并传达语义.

附录:Java中无限长的lookbehind

敏锐的读者会注意到,它assertEntirety包含一个.*外观,它使其理论最大长度无限.不,Java并没有正式支持无限长的外观.是的,因为它在这里得到了充分的证明,无论如何都可行.正式它被归类为"虫子"; 但"某人" ^(*wink*)也可以将其视为"隐藏的功能".

这个"bug"肯定会在将来被"修复".删除此隐藏功能将破坏Java正则表达式回文问题的特定解决方案.

相关问题

• 正则表达式在Java中没有明显的最大长度