Regex中的字符串操作似乎有太多异常

在这篇文章中，我将形式为(x₁，…，x_n)的字符串调用为序列，形式为{y_{1_{，..，y_n}的字符串合。其中，每个x_i和y_i可以是数字[0-9]+、字[a-zA-Z]+、数字/字[a-zA-Z0-9]+、序列或集合。}}

我想知道是否有可能(如果有，请帮助弄清楚如何)使用Regex来处理以下问题：

我想将形式为(x₁，…，x_n、x_n+1)的序列转换为((x_{1)、x_n+1)。}

示例：

(1,2,3,4,5)将变为((1,2,3,4),5)

((1,2,3,4),5)将变为(((1,2,3),4),5)，因为形式(x₁，…，x_n、x_n+1)的唯一字符串是内部的(1,2,3,4)。

(((1,2,3),4),5)将变为((((1,2),3),4),5)，因为形式(x₁，…，x_n、x_n+1)的唯一字符串是内部的(1,2,3)。

(1,(2,3),4)将变为((1,(2,3)),4)

({1},{2},{3})将变为(({1},{2}),{3})

根据请求，更多示例：

((1,2),(3,4),5)将变为(((1,2),(3,4)),5)

((1,2),3,(4,5))将变为(((1,2),3),(4,5))

(1,(2,(3,4),5))将变为(1,((2,(3,4)),5))，因为形式(x₁，…，x_n、x_n+1)的唯一序列是内部的(2,(3,4),5)。

以下是我目前所拥有的：

re.sub(r'([(][{}a-zA-Z0-9,()]+,[{}a-zA-Z0-9,]+),', r'(g<1>),', string)

你可以在这里看到它工作的字符串。

它不适用于(1,(2,3),4)，而且正在处理({{x},{x,y}},z)之类的事情，而不应该这样做。任何帮助都将不胜感激；我觉得在Regex有可能做到这一点，但似乎有很多特殊情况需要Regex非常精确。

对于python中的任何递归，您都必须使用PyPi regex模块(正如anubhava在回答中所提到的)。您可以使用以下模式：

请参阅此处使用的正则表达式

(((({(?:[^{}]+|(?-1))+})|((?:[^(),]+,[^(),]+))|[^(){},]+)(?:,(?2))+),

更换为(1),

工作原理：

(((({(?:[^{}]+|(?-1))+})|((?:[^(),]+,[^(),]+))|[^(){},]+)(?:,(?2))+),将以下内容捕获到捕获组1中，然后匹配,
- (与(完全匹配
- (({(?:[^{}]+|(?-1))+})|((?:[^(),]+,[^(),]+))|[^(){},]+)匹配以下选项之一一次或多次(并将其捕获到捕获组2中)
  - ({(?:[^{}]+|(?-1))+})将以下内容捕获到捕获组3中
  - {(?:[^{}]+|(?-1))+}匹配{，然后以下选项之一匹配一次或多次，然后匹配}
    - [^{}]+与除{或}之外的任何字符匹配一次或多次
    - (?-1)重复上一个捕获组(捕获组3)
  - ((?:[^(),]+,[^(),]+))匹配(，然后匹配以下内容，然后匹配)
  - [^(),]+与除(、)或,之外的任何字符匹配一次或多次
  - ,与逗号,字符完全匹配
  - [^(),]+与除(、)或,之外的任何字符匹配一次或多次
  - [^(){},]+与除(、)、{、}或,之外的任何字符匹配一次或多次
- (?:,(?2))+匹配以下一次或多次
  - ,(?2)匹配,，然后递归捕获组2

简单地说，捕获组2定义了什么是术语。它…：

重新匹配任意集合{y1, ..., yn}+：{{y1, ..., yn},..., xn}
正好匹配两个元素的任何完整序列：(x1, x2)
匹配任何字符串对象(数字、单词等)1、2。。。x、y

然后捕获组1使用捕获组2中定义良好的术语来匹配尽可能多的术语，字符串至少包含两个术语和一个逗号(x,x,和尽可能多x,)。替换获取该捕获组，将其封装在()中，并附加,。所以在(x,x,x,x)的情况下，我们得到了((x,x,x),x)。

编辑

通过使非捕获组拥有(?:[^{}]+|(?-1))++(防止回溯)并改变选项的顺序(首先是最普遍的)，我们可以提高模式的效率(764->662步)：

请参阅此处使用的正则表达式

((([^(){},]+|((?:[^(),]+,[^(),]+))|({(?:[^{}]+|(?-1))++}))(?:,(?2))+),

如果您可以考虑使用支持PCRE功能的Python的PyPi regex模块，那么可以使用以下正则表达式来支持递归匹配：

/
(                                       # start capture group #1
(                                    # match left (
(?<el>                                # start named group el
( { (?: [^{}]*+ | (?-1) )* } ) |    # Match {...} text OR
( ( (?: [^()]*+ | (?-1) )*+ ) ) | # Match (...) text OR
w+                                 # Match 1+ word characters
)                                     # End named group el
(?: , (?&el) )+                       # Match comma followed by recursion of 'el'
# Match this group it 1+ times                                          
) ,                                     # End capture group #1
/ x                                     # Enable extended mode in regex

RegEx演示

这里有一个用ply 构建的简单解析器

它肯定没有regex解决方案那么紧凑，但它有几个相当大的优势：

它更容易写和理解。(事实上，除了其中一个名字的拼写错误外，我的第一次尝试非常成功。)此外，通过检查，可以相当清楚地了解正在解析的语法。(当然，这需要对生成语法有一些最低限度的理解，但概念并不是特别困难，而且有很多可用的学习资源。)
如果你想在未来添加更多功能，可以直接进行修改。如果您不想只是重新格式化文本，而是想真正利用分解的结构，这很容易获得，而无需付出太多努力。

与大多数生成的解析器一样，它有两个组件：一个lexer(或scanner)，它将输入分解为标记并丢弃不重要的文本(如空白)；另一个解析器，它分析标记流以找出其结构。通常，解析器会构造某种表示输入的数据结构，通常是某种树。在这里，我通过将解析后的输入重新组合为转换后的输出来简化这个过程。(回想起来，我忍不住想，像往常一样，生成一个完整的解析树，然后在树上遍历来创建输出会更清楚。也许作为忏悔，我稍后会重做它。)

这是扫描仪。唯一有意义的标记是标点符号和我所说的word，它们是Python认为的任何单词字符的序列(通常是字母和数字字符加下划线)，而不是像你的问题中那样区分纯字母、纯数字和混合标记。

import ply.lex as lex
tokens = [ "WORD" ]
t_WORD = r"w+"
# Punctuation
literals = "{}(),"
# Ignore whitespace
t_ignore = " rnt"
# Anything else is an error
def t_error(t):
print("Illegal character %s" % repr(t.value[0]))
t.lexer.skip(1)
# Build the lexer
lexer = lex.lex()

现在是解析器。序列的语法有点多余，因为它必须对一个项目的序列进行特殊处理：由于语法在解析时也在A,B周围显式插入括号，因此在整个序列周围添加括号是不正确的。但是，如果整个序列是一个项目，则必须重新插入原始的括号。对于布景，情况要清楚得多；根本不修改元素，必须始终将大括号添加回。

以下是整个语法：

# scalar   : WORD | set | sequence
# sequence : '(' scalar ')'
#          | '(' seqlist ')'
# seqlist  : scalar  ',' scalar
#          | seqlist ',' scalar
# set      : '{' setlist '}'
# setlist  : scalar
#          | setlist ',' scalar

下面是实现，语法重复，Ply风格，作为文档字符串：

import ply.yacc as yacc
start = 'scalar'
def p_unit(p):
"""scalar   : WORD
| set
| sequence
setlist  : scalar
"""
p[0] = p[1]
def p_sequence_1(p):
"""sequence : '(' scalar ')'
"""
p[0] = '(%s)' % p[2]
def p_sequence(p):
"""sequence : '(' seqlist ')'
"""
p[0] = p[2]
def p_seqlist(p):
"""seqlist : scalar  ',' scalar
| seqlist ',' scalar
"""
p[0] = "(%s,%s)" % (p[1], p[3])
def p_set(p):
"""set     : '{' setlist '}'
"""
p[0] = '{%s}' % p[2]
def p_setlist(p):
"""setlist : setlist ',' scalar
"""
p[0] = "%s,%s" % (p[1], p[3])

def p_error(p):
if p:
print("Syntax error at token", p.type)
else:
print("Syntax error at EOF")
parser = yacc.yacc()

现在，一个(非常)简单的驱动程序：

import readline
while True:
try:
s = input('> ')
except EOFError:
break
if s:
print(parser.parse(s, lexer=lexer))

编辑

相关内容

最新更新

热门标签：