Python模式匹配。匹配'c[任意数量的连续a、b或c，或者b、c或a等]t'

Question

很抱歉标题不太清晰，我无法想到一个简洁的方式来问我的问题。

在Python中，我想匹配一个表达式'c[some stuff]t'，其中[some stuff]可以是任意数量的连续a、b或c，并且可以以任何顺序出现。

例如，这些都可以： 'ct', 'cat', 'cbbt', 'caaabbct', 'cbbccaat'

但这些不行： 'cbcbbaat', 'caaccbabbt'

编辑：a、b和c只是一个示例，但我真的很想能够将其扩展到更多字母。我对正则表达式和非正则表达式解决方案感兴趣。

- Usagi

---

从大多数回复来看，似乎唯一编码的方法是手动设置所有情况。这是真的吗？如果我想再添加两个字母，那将会非常困难。我认为那将会有120种情况。 - Usagi

@Wooble - 不，我只是希望解决方案具有可扩展性。完全手动/直接的方法需要大量打字。 - Usagi

Answer 1

没有经过彻底测试，但我认为这应该可以工作：

import re

words = ['ct', 'cat', 'cbbt', 'caaabbct', 'cbbccaat',  'cbcbbaat', 'caaccbabbt']
pat = re.compile(r'^c(?:([abc])\1*(?!.*\1))*t$')
for w in words:
    print w, "matches" if pat.match(w) else "doesn't match"

#ct matches
#cat matches
#cbbt matches
#caaabbct matches
#cbbccaat matches
#cbcbbaat doesn't match
#caaccbabbt doesn't match

这个匹配项适用于一连串的 a、b 或者 c（即 ([abc])\1* 部分），而负向先行断言 (?!.*\1) 则确保在该串之后不会出现该字符的其他实例。

- mhyfritz

Answer 2

不确定您对正则表达式有多依赖，但是这里提供了一种使用不同方法的解决方案：

from itertools import groupby

words = ['ct', 'cat', 'cbbt', 'caaabbct', 'cbbccaat',  'cbcbbaat', 'caaccbabbt']
for w in words:
    match = False
    if w.startswith('c') and w.endswith('t'):
        temp = w[1:-1]
        s = set(temp)
        match = s <= set('abc') and len(s) == len(list(groupby(temp)))
    print w, "matches" if match else "doesn't match"

如果一组中间字符是 set('abc') 的子集，并且 groupby() 返回的组数与集合中元素的数量相同，则字符串匹配。

- Andrew Clark

---

我对效率比较感兴趣，我不一定依赖于正则表达式。 - Usagi

非常好，而且易于扩展！我自己写了一个非正则表达式的答案，但是你的更好，所以我只是给你点赞，而不是发表我的答案。 - Lauritz V. Thaulow

@Andrew - 我喜欢这个解决方案的易读性。 这个解决方案还吸引了我数学方面，包括集合。看起来很高效，但与正则表达式相比如何？有人知道吗？ - Usagi

@Usagi：它应该是字符串长度的线性，因此在渐近意义下，你无法超越它。 - Neil G

Answer 3

我相信您需要明确编码所有可能的 a、b 和 c 的排列组合：

c(a*b*c*|b*a*c*|b*c*a*|c*b*a*|c*a*b*|a*c*b*)t

请注意，这是一个极其低效的查询，可能会有大量回溯。

- Konrad Rudolph

---

它是这样吗？在失败之前，整个字符串最多只能被分析6次。我没有看到任何典型的有问题的正则表达式的指数爆炸。 - 6502

Answer 4

我不熟悉Python的正则表达式引擎，但是听起来你只是想直接编写出6种不同的可能顺序。

/c(a*b*c*|a*c*b*|b*a*c*|b*c*a*|c*a*b*|c*b*a*)t/

- Lily Ballard

---

有其他的方法吗？例如，如果我想添加d和e，我将不得不手动输入120个案例。 - Usagi

@Usagi 不要使用正则表达式，如果有更复杂的情况，最好手动解析。 - Lily Ballard

@Usagi：你可以很容易地编写一个函数来生成正则表达式字符串，避免手动输入。 - trutheality

@trutheality：当然，但是你会因为所有的回溯而陷入极度低效的状态。 - Lily Ballard

Answer 5

据我所知，没有一种“紧凑”的方法可以做到这一点...

c(a*(b*c*|c*b*)|b*(a*c*|c*a*)|c*(a*b*|b*a*))t

- trutheality