这个正则表达式替换如何反转字符串？

Question

_{这是一系列教育正则表达式文章的第四部分.它展示了嵌套引用的组合(请参阅:这个正则表达式如何找到三角形数？？)在断言中"计数"(参见:我们如何匹配^ nb ^ n与Java正则表达式？)可用于反转字符串.以编程方式生成的模式使用元模式抽象(请参阅:此Java正则表达式如何检测回文？).这是系列中的第一次,这些技术用于替换而不是整个字符串匹配.}

提供了完整的Java和C#实现.鼓舞人心的报价包括在内.

使用正则表达式反转字符串似乎不是一个好主意,如果它完全可能,它甚至不会立即显而易见,如果是这样,人们可能会尝试这样做.

虽然它仍然不是一个好主意,但至少现在我们知道这是可能的,因为这是一种方法:

C#^{_{(也在ideone.com上)}}

using System;
using System.Text.RegularExpressions;

public class TwoDollarReversal {    
public static void Main() {
   string REVERSE = 
      @"(?sx) . grab$2"
         .Replace("grab$2",
            ForEachDotBehind(
               AssertSuffix(@"((.) \1?)")
            )
         );
   Console.WriteLine(
      Regex.Replace(
         @"nietsniE treblA --
         hguone llew ti dnatsrednu t'nod uoy ,ylpmis ti nialpxe t'nac uoy fI",

         REVERSE, "$2"
      )
   );
   // If you can't explain it simply, you don't understand it well enough
   // -- Albert Einstein
}      
// performs an assertion for each dot behind current position
static string ForEachDotBehind(string assertion) {
   return "(?<=(?:.assertion)*)".Replace("assertion", assertion);
}
// asserts that the suffix of the string matches a given pattern
static string AssertSuffix(string pattern) {
   return "(?=.*$(?<=pattern))".Replace("pattern", pattern);
}

}

Java ^{_{(也在ideone.com上)}}

class TwoDollarReversal {

public static void main(String[] args) {
   String REVERSE =
      "(?sx) . grab$2"
         .replace("grab$2",
            forEachDotBehind(
               assertSuffix("((.) \\1?)")
            )
         );

   System.out.println(
      "taerG eht rednaxelA --\nyrt lliw ohw mih ot elbissopmi gnihton si erehT"
         .replaceAll(REVERSE, "$2")
   );
   // There is nothing impossible to him who will try
   // -- Alexander the Great"
}

static String forEachDotBehind(String assertion) {
   return "(?<=^(?:.assertion)*?)".replace("assertion", assertion);
}
static String assertSuffix(String pattern) {
   return "(?<=(?=^.*?pattern$).*)".replace("pattern", pattern);
}

}

C#和Java版本似乎都使用相同的整体算法,仅在抽象的实现细节中有微小的变化.

显然,这不是逆转字符串的最佳,最直接,最有效的方法.也就是说,为了学习正则表达式; 如何概念化模式; 引擎如何工作以匹配它们; 如何将各个部分组合在一起构建我们想要的东西; 如何以可读和可维护的方式这样做; 只是为了学习新东西的纯粹快乐,我们可以解释一下它是如何工作的吗？

---

附录:备忘单!

这是使用的基本正则表达式构造的简要描述:

• (?sx)是嵌入的标志修饰符.s启用"单行"模式,允许点匹配任何字符(包括换行符).x启用自由间隔模式,其中忽略未转义的空格(#并可用于注释).
• ^并且$是开始和结束的锚点.
• ?作为重复说明符表示可选(即零或一).作为例如重复量词,.*?它表示重复*(即零或多)重复是不情愿的 /非贪婪的.
• (…)用于分组.(?:…)是一个非捕获组.捕获组保存匹配的字符串; 它允许后退/前进/嵌套引用(例如\1),替换替换(例如$2)等.
• (?=…)是一个积极的前瞻 ; 它看起来有权断言给定模式的匹配.(?<=…)是正回顾后 ; 它向左看.

语言参考/其他资源

• MSDN - 正则表达式语言元素 -System.Text.RegularExpressions
• Java教程/基本类/正则表达式 -java.util.regex.Pattern

Answer 1

概观

在较高级别,模式匹配任何一个字符.,但另外执行一个grab$2操作,捕获与组2匹配的字符的反转"配合".此捕获通过构建长度匹配的输入字符串的后缀来完成前缀的长度直到当前位置.我们通过应用assertSuffix一个将后缀增加一个字符的模式来重复执行此操作forEachDotBehind.第1组捕获此后缀.在第2组中捕获的该后缀的第一个字符是匹配的字符的反转"配偶".

因此,用其"配合"替换每个匹配的字符具有反转字符串的效果.

它是如何工作的:一个更简单的例子

为了更好地理解正则表达式模式的工作原理,让我们首先将它应用于更简单的输入.此外,对于我们的替换模式,我们只是"转储"所有捕获的字符串,以便我们更好地了解正在发生的事情.这是一个Java版本:

System.out.println(
    "123456789"
        .replaceAll(REVERSE, "[$0; $1; $2]\n")
);

以上打印(如ideone.com上所示):

[1; 9; 9]
[2; 89; 8]
[3; 789; 7]
[4; 6789; 6]
[5; 56789; 5]
[6; 456789; 4]
[7; 3456789; 3]
[8; 23456789; 2]
[9; 123456789; 1]

因此,例如[3; 789; 7]意味着点匹配3(在组0中捕获),相应的后缀是789(组1),其第一个字符是7(组2).请注意,这7是3"配偶".

                   current position after
                      the dot matched 3
                              ?        ________
                      1  2 [3] 4  5  6 (7) 8  9
                      \______/         \______/
                       3 dots        corresponding
                       behind      suffix of length 3

请注意,角色的"配偶"可能在其右侧或左侧.角色甚至可能是自己的"伴侣".

如何构建后缀:嵌套引用

负责匹配和构建增长后缀的模式如下:

    ((.) \1?)
    |\_/    |
    | 2     |       "suffix := (.) + suffix
    |_______|                    or just (.) if there's no suffix"
        1

请注意,在组1的定义中是对自身(with \1)的引用,尽管它是可选的(with ?).可选部分提供了"基本案例",这是一种在不引用自身的情况下匹配的方法.这是必需的,因为当组尚未捕获任何内容时,尝试匹配组引用始终会失败.

一旦第1组捕获了某些内容,可选部分就永远不会在我们的设置中运行,因为我们上次刚刚捕获的后缀仍然会出现在那里,并且我们总是可以将另一个字符添加到此后缀的开头(.).这个前置角色被捕获到第2组.

因此,该模式试图将后缀增加一个点.forEachDotBehind因此,重复这一次将产生后缀,其长度恰好是前缀到我们当前位置的长度.

如何assertSuffix与forEachDotBehind工作:元图案抽象

请注意,到目前为止,我们已经将assertSuffix其forEachDotBehind视为黑盒子.事实上,将这个讨论留在最后是一个刻意的行为:名称和简要文档表明他们做了什么,这足以让我们写下和阅读我们的REVERSE模式!

仔细观察后,我们发现这些抽象的Java和C#实现略有不同.这是由于两个正则表达式引擎之间的差异.

.NET正则表达式引擎允许在后台进行完全正则表达式,因此这些元模式看起来更自然.

• AssertSuffix(pattern) := (?=.*$(?<=pattern)),即我们使用前瞻一直到字符串的末尾,然后使用嵌套的lookbehind将模式与后缀匹配.
• ForEachDotBehind(assertion) := (?<=(?:.assertion)*),即我们只是.*在一个lookbehind 匹配,标记断言与非捕获组内的点.

由于Java并没有正式支持无限长度的后台(但在某些情况下它无论如何都有效),它的对应物有点尴尬:

• assertSuffix(pattern) := (?<=(?=^.*?pattern$).*),即我们使用lookbehind一直到字符串的开头,然后使用嵌套的前瞻来匹配整个字符串,在前缀模式前加上.*?不情愿地匹配一些不相关的前缀.
• forEachDotBehind(assertion) := (?<=^(?:.assertion)*?),即我们使用不情愿重复的锚定后观,即^.*?(同样标记断言以及非捕获组内的点).

应该注意的是,虽然这些元模式的C#实现在Java中不起作用,但Java实现在C#中工作(参见ideone.com).因此,实际上不需要为C#和Java提供不同的实现,但C#实现有意利用更强大的.NET正则表达式引擎支持,以更自然地表达模式.

因此,我们展示了使用元模式抽象的好处:

• 我们可以独立开发,检查,测试,优化等这些元模式实现,也许可以利用特定于风味的功能来获得额外的性能和/或可读性.
• 一旦这些构建模块被开发和经过充分测试,我们就可以简单地将它们用作更大模式的一部分,这使我们能够在更高层次上表达想法,从而获得更易读,更易维护,更便携的解决方案.
• 元模式促进了重用,而程序化生成意味着重复性降低

虽然这个概念的这种特殊表现是相当原始的,但它也可以进一步发展,并开发一个更强大的程序化模式生成框架,其中包含经过充分测试和优化的元模式库.

也可以看看

• Martin Fowler - 组成正则表达式
• .NET正则表达式 - 平衡组定义 - 元模式的一个很好的例子!

结束思想

需要重申的是,用正则表达式反转字符串在实践中并不是一个好主意.它比必要的更复杂,性能也很差.

也就是说,这篇文章表明,CAN其实也可以做,而且当在使用元模式抽象较高水平表示,该解决方案实际上是相当的可读性.作为解决方案的一个关键组成部分,嵌套引用再次展示在希望是另一个引人入胜的示例中.

不太明显,或许该文章也显示了解决一开始可能看似困难(甚至"不可能")的问题所需的决心.也许它也表明了思想的清晰度,这是对主题的更深刻理解,是大量研究和努力工作的结果.

毫无疑问,正则表达式可能是一个令人生畏的主题,当然它不是为解决你所有的问题而设计的.然而,这不是仇恨无知的借口,如果你愿意学习,这是一个令人惊讶的深刻知识.