Regex可以处理嵌套操作吗？

Question

我有一些字符串:

"1+""2*3"*4"+"5*6""

和一些正则表达式,答案应该是:

(1+((2*3)*4)+(5*6))

可以正则表达式吗？

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所定义的那样.