代码之家  ›  专栏  ›  技术社区  ›  polygenelubricants

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

nested-reference lookaround palindrome regex java
  •  21
  • polygenelubricants  · 技术社区  · 15 年前

    How does this regex find triangular numbers? (首先引入嵌套引用)和 How can we match a^n b^n with Java regex? (进一步阐述了展望“计数”机制)。这一部分介绍了一种特定形式的嵌套断言,当与嵌套引用结合使用时,Java正则表达式可以匹配大多数人认为“不可能”的内容:回文!!

    回文的语言是非- regular ;实际上 context-free 相关问题 ).

    然而,Java的regex引擎既不支持这些“高级”特性。但是“某人” ( ) 成功地编写了下面的regex,它似乎做得很好( see also on 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));
        }
    }
}

    所以这看起来是可行的,但是怎么做呢?

    工具书类

    这不是检测回文的最佳方法;它是 O(N^3)

    你不会想的 使用 regex检测回文的原因与您不想检测回文的原因相同 使用 找到质数的正则表达式。也就是说,你会 学习 学习 如何使用正则表达式进行素性测试:它很有趣,很有挑战性,很有教育意义。

    相关问题

    1 回复  |  直到 8 年前
        1
  •  18
  •   Community CDub    8 年前

    大局

    我们将首先从全局算法的角度来研究这个正则表达式,然后稍后再仔细研究具体的实现细节。regex几乎是以下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代码,但它工作得很好,而且最吸引人的是,它几乎可以直接翻译成regex,并且有一个近乎一对一的映射。这里又是正则表达式,为了方便起见在这里复制,注释以突出惊人的相似性: 

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

    : annotated and expanded version of the source code on ideone.com

    (可以忽略 assertEntirety 现在:把它看作一个黑箱正则表达式机制,它可以对 不管我们现在在哪里。)

    所以基本的算法是,当我们从左到右扫描字符串时,我们尝试在回文约束下构建一个后缀。然后我们检查是否能够以这种方式构建完整的字符串。如果可以的话,那么这个字符串就是回文。另外,作为一个特例,空字符串是一个微不足道的回文。

    一旦理解了全局算法,我们就可以检查regex模式是如何实现它的。

    怎么回事 String.replace

    Java中的正则表达式模式最终只不过是字符串,这意味着它们可以像任何字符串一样通过字符串操作派生出来。是的,我们甚至可以使用正则表达式来生成正则表达式模式——一种元回归方法,如果你愿意的话。

    int 常数(最终只包含一个数字): 

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

    分配给的号码 X 是一个文字整数:我们可以 清晰可见 Y 它使用了一个表达式,但是这个公式似乎传达了 这个数字代表什么。即使没有正确命名这些常数,我们仍然得到这样的想法 是的 可能表示一周内的秒数,即使我们可能无法立即知道数值是多少。另一方面 我们确切地知道这个数字,但对它所代表的东西却不太了解。

    在代码片段中使用字符串替换是一种类似的情况,但对于字符串正则表达式模式而言。而不是显式地将模式写成一个文本字符串,有时 系统逻辑推导 从更简单的部分得到的值(“公式”)可能更有意义。这在regex中尤其如此,在regex中,我们了解模式的功能通常比看到它看起来像一个字符串文字更为重要(不管怎样,它不是一个很好看的东西,而是所有额外的反斜杠)。

    为了方便起见,在此再次复制部分代码片段: 

    // 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         |
     //        |_______________________________|

    毫无疑问,在这种情况下,“公式”比最终的字符串“值”可读性强得多。

    当然,有很多更复杂的方法以编程的方式生成regex模式,当然也有可能以这样一种方式编写,即模糊化而不是强调其含义,但即使是简单的字符串替换的小心使用仍然会令人惊奇(希望如本例所示)。

    教训 :考虑正则表达式模式的编程生成。

    怎样做 add 工作?

    这个 (?:(.) add)+ 添加

    • 这个 (.) 捕获到组1中,允许稍后进行反向引用
    • 资产技术
      • 我们稍后将更详细地讨论这个问题;只要把它看作是对整个字符串进行断言的一种方法

    应用于的模式 在里面 添加 具体如下: 

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

    (.) 从左到右,我们尝试在同一个字符前加上前缀(使用backreference to \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部分中,我们展示了回溯 ? 可能导致同样的重置问题
        • 我们用所有格量词解决了这个问题 ?+ ,但此处不适用

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

    教训 :仔细分析模式中贪婪/不情愿重复之间的相互作用。

    为什么我们需要一个 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

    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公司 资产技术 模式的 \2 )因此在我们的设置中是绝对必要的。我们需要确认的是,我们确实一直在努力增加后缀。如果是这样的话,我们就有了回文。

    :仔细分析可选自引用匹配的任何可能意外的副作用。

    主菜: 资产技术

    虽然我们可以编写一个Java正则表达式模式来检测回文,但这里除了 已经在本系列的前几个部分中介绍过。这里唯一的新事物是这个神秘的黑匣子,这个强大的机制神奇地让我们去做原本“不可能”的事情。

    这个 资产技术

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

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

    围绕 我们,也许在前面或后面,从我们站的地方。以这种方式在了望台上嵌套一个了望台,我们就可以隐喻性地“飞向天空”,并看到整个画面。

    将此元模式抽象为 有点像编写预处理替换宏。到处都有嵌套的lookaround可能会损害可读性和可维护性,因此我们将其封装到 资产技术 它不仅隐藏了其内部工作的复杂性,而且通过赋予一个适当的名称来进一步强调它的语义。

    教训 考虑抽象元模式来隐藏复杂性和传达语义。

    附录:Java中的无限长查找

    细心的读者会注意到 包含 在后面看,这使得它的理论最大长度是无限的。不,Java不支持无限长的lookbehind。是的,正如这里已经很好地演示过的,它无论如何都是有效的。官方称之为“臭虫”;但“某人” (*眨眼*) 也可以认为这是一个“隐藏的特征”。

    相关问题

    推荐文章
    Harsh Joshi  ·  我想检查字符串是否为回文[闭合]
    8 年前
    md.ashif313  ·  使字符串回文的最小插入次数
    8 年前
    Kevin Mangal  ·  谁能告诉我为什么这个方法不适用于寻找回文?
    8 年前
    iswg  ·  Ruby最长回文
    9 年前
    Codes316  ·  确定字符串是否为回文
    9 年前
    user3259144  ·  正在检查回文
    11 年前
    user3434094  ·  带方法的Palindrome.java
    11 年前
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号