正则表达式能处理嵌套操作吗？

Question

我有一些字符串，例如： "1+""2*3"*4"+"5*6"" 使用一些正则表达式，答案应该是： (1+((2*3)*4)+(5*6)) 正则表达式能够实现这个吗？

- Mehdi Khademloo

---

一个巧妙的谜题。我的第一次尝试失败了，但如果足够有创意，应该能够让它工作，不是吗？也许你需要一个BNF来让它工作，但无论如何，当解决方案出现时，我会感兴趣看到它的。 - thb

正则语言无法捕获“递归语言”。这是正则表达式的泵引理的结果。例如，平衡括号等问题无法用正则表达式解决。一些语言（如Perl）稍微扩展了正则表达式的表达能力。话虽如此，如果我们知道表达式本身是有效的（因此不会出现非法输入），那么替换确实可以完成。 - Willem Van Onsem

我并不认为我的失败尝试会引起任何人的兴趣，但是为了提供信息，如果有人在意的话，这是一个扩展格式的正则表达式，就像Sed一样：s/((^|[-+*/"])[[:space:]]*)"([^"]*)"([[:space:]]*([-+*/"]|$))/\1\(\3\)\4/。 - thb

@WillemVanOnsem：有趣的观点。我曾想尝试使用外部循环来实现这一点。我没有想到让正则表达式本身递归。听起来很难。 - thb

@DanD。使用堆栈。当然，机器如何知道要推哪个 " 以及哪个要弹出？这不需要语法吗？期待您的解决方案。 - thb

Answer 1

如果输入是有效的，我们可以利用这种语言的一些冗余约束条件来添加适当的括号。但这实际上更多地使用了“技巧”。我真的建议使用更复杂的工具，比如一个下推自动机（所以一个解析器）。

嗯，这里有一些我们可以发现的东西：如果下一个字符是数字，或者是双引号后跟一个数字的序列，那么所有其他双引号都可以被忽略。

因此，我们可以用两个正则表达式来实现：

• 第一个替换所有后面跟着零个或多个双引号和一个数字的双引号；
• 然后替换所有剩余的双引号（这实际上只是字符替换，所以不需要正则表达式）。

但是，这个技巧只有在原始输入是有效的情况下才有效。如果它包含像"+"这样的操作符周围的双引号，那么它可能会产生完全不同的结果。

例如，在Python中，我们可以使用以下代码：

from re import sub

def add_brackets(text):
    return sub(r'["](?=\"*[(\d])', '(', text).replace('"', ')')

这样我们就得到了：

>>> add_brackets('"1+""2*3"*4"+"5*6""')
'(1+((2*3)*4)+(5*6))'

这里的原因是因为我们只考虑数字和运算符。如果我们添加变量，它仍然有效，但是如果添加更复杂的元素（如函数），则问题会变得更难。

然而，“递归语言”（即其中某些元素可以以自身为定义）更适合使用为此构建的工具解析，例如下推自动机。

正则语言泵引理表明像（ⁿ）ⁿ（一个包含一定数量开括号后紧接相同数量闭括号的字符串的语言）这样的语言无法用正则表达式验证。您在此描述的语言就是一个例子。因此，这个正则表达式不能验证它。一些编程语言（如Perl）具有扩展的正则表达式，使其可以验证平衡括号。这些不是正则表达式，至少不是由Stephen Kleene定义的。

- Willem Van Onsem