在"aa67bc54c9"中,是否有任何方法可以使用正则表达式打印"aa"67次,"bc"54次等等？

Question

我在接受实习的采访中被问到这个问题,我建议的第一个解决方案是尝试使用正则表达式(我通常在采访中有点难过).像这样的东西

(?P<str>[a-zA-Z]+)(?P<n>[0-9]+)

我认为它会匹配字符串并将它们存储在变量"str"中,而将数字存储在变量"n"中.怎么样,我不确定.

所以它匹配"a1b2c3"类型的字符串,但这里的一个问题是它也匹配"a1b"类型的字符串.有谁能建议解决这个问题的解决方案？

另外,还有其他正则表达式可以解决这个问题吗？

Answer 1

你知道为什么"正则表达式"被称为"常规"吗？:-)

这将是一个太长的解释,我只是概述了方式.为了匹配模式(即确定给定字符串是"有效"还是"无效"),理论信息学家将使用有限状态自动机.这是一个具有有限数量状态的抽象机器; 每个tick它从输入读取一个char并跳转到另一个状态.读取特定字符时从特定状态跳转到何处的模式是固定的.有些状态标记为"OK",有些状态标记为"FAIL",因此通过检查机器状态,您可以检查文本是否"有效"(即有效的电子邮件).

例如,这台机器只接受"nice"作为其"有效"字(来自维基百科的图片):

理论上可以区分无效的一组"有效"词语称为" 常规语言 ".并非每一组都是常规语言:例如,有限状态自动机无法检查字符串中的括号是否平衡.

但是,与定义"有效"的复杂性相比,构建状态机是一项复杂的任务.因此,数学家(主要是S. Kleene)指出,每种常规语言都可以用" 正则表达式 " 来描述.他们有*s和|s,是我们现在所知的regexps的原型.

它与这个问题有什么关系？ 主题中的问题基本上是非常规的. 它不能用任何像有限自动机那样工作的东西来表达.

其实质是它应该包含一个能够保存任意数字的存储单元(在您的情况下重复计数).有限自动机和经典正则表达式不能做到这一点.

然而,现代正则表达式更具表现力,据说可以检查平衡的括号!但这可以作为一个很好的例子,你不应该使用正则表达式来完成他们不适合的任务.更不用说它包含代码片段; 这使得表达远非"常规".

回答最初的问题,你不能只使用"常规"来解决你的问题.但是,正如tster的回答一样,正则表达式可以帮助您解决这个问题

也许,我应该更接近tster的答案(请在那里做一个"+1"!)并说明为什么它不是"正则表达式"解决方案.人们可能认为它只是包含print语句(不是必需的)而循环 - 循环概念与有限状态自动机表达能力兼容.但还有一件难以捉摸的事情:

while ($line =~ s/^([a-z]+)(\d+)//i)
{
    print $1 
             x  # <--- this one
               $2;
}

读取字符串和数字并重复打印给定次数的字符串(数字是任意整数)的任务在有限状态机上是无法撤销的,没有额外的内存.您使用内存单元来保留该数字并减少它,并检查它是否大于零.但是这个数字可能是任意大的,并且它与有限状态机可用的有限存储器相矛盾.

然而,经典模式/([abc]*){5}/与"常规"重复固定次数相匹配并没有错.我们基本上具有对应于"匹配模式一次","匹配模式两次"......"匹配模式5次"的状态.它们的数量是有限的,这就是差异的要点.

Answer 2

怎么样:

while ($line =~ s/^([a-z]+)(\d+)//i)
{
    print $1 x $2;
}

Answer 3

直接回答你的问题:

• 不,正则表达式匹配文本而不打印任何内容,因此无法单独使用正则表达式.

您提供的正则表达式将匹配一个字符串/数字对; 然后,您可以使用适当的机制重复打印.来自@tster的Perl解决方案非常紧凑.(它不使用您在正则表达式中应用的名称;我很确定这无关紧要.)

其余细节取决于您的实现语言.