通讯在Python

Question

用正则表达式字符串之间我需要一个功能的Python采用两个字符串(a, b)和对应规则的列表，即串(a[i], b[i])的对，并检查是否有可能在部分a拆分，更换每部分按照通信规则得到b。问题是，这些规则可能会有点纠结：

1. 像(a, b)有可能是规则和(a, c)

2. 像(aa, b)和(a, c)

3. 像(ab, d)和(bc, e)

4. 它是通信，不是替换（a不能被留下a或首先转换为b，然后转换成c）。

例如，如果对应规则(aa, x)，(ab, y)，(ab, z)，然后(aab, anything)，(a, anything)不被接受，但(aa, x)，(abab, yz)，(abab, yy)，(abab, zz)，(abab, zy)，（AAAB，XY）`是。

是否有使用Python的或其他一些常见的正则表达式执行非标准正则表达式库做到这一点的方法吗？我可以通过蛮力来做到这一点，但对于许多对来说，它是非常无效的。

Answer 1

（要得到完全糊涂了，我将其称为“钥匙”和“价值观”您的信件对的元素，即使重复键防止它们构成一个典型的dict保留英文。）

我相信有几个原因，你不能单独使用正则表达式来做到这一点。

问题1.正则表达式是不是地图

正则表达式没有做出与它的翻译（S）到值的键的一些序列的字符串相关联的方式。对于初学者来说，re函数需要访问您的键值对列表，如果只是这样它可以告诉您哪些键出现在匹配中。

问题2：不明确的匹配

有几个方面的正则表达式可以处理模棱两可的比赛中交替，如：

re.findall(r'(a|aa|aaa)*', 'aaaa') 

的问题是，你只能得到挑一个其中任何给定的正则表达式。你的问题需要跟踪其中其中哪些替代方案匹配，按什么顺序，以及各自的次数。

更糟糕的是，您的问题需要了解这些替代品的所有可能组合。但一旦正则表达式确定'aaaa'匹配任何重复，就像'a' + 'a' + 'a' + 'a'，它的完成 ---找到匹配。

但是你尚未完成。您仍然需要测试所有其他匹配项，例如'a' + 'a' + 'aa','a' + 'aa' + 'a'和'aaa' + 'a'，并且...测试这些将导致很多值的不同组合粘在一起并与第二个参数进行比较。你不能跳过它们。

一个勇敢的，但悲剧命运尝试

我做了一个正则表达式建设的功能，能有效识别输入和输出的字符串，一组键 - 值对。不幸的是，这并没有说明给定的输入字符串是否可以真正产生特定的输出。

import re 

def is_valid_word(word, alphabet): 
    ''' 
    Returns True if the given word can be assembled from zero or 
    more of the strings in the given alphabet. If word is an 
    empty string (''), this is True regardless of strings in the 
    alphabet. 
    ''' 
    regex_letters = (re.escape(letter) for letter in alphabet) 
    regex_alternatives = '|'.join(regex_letters) 
    regex = r'(?:' + regex_alternatives + r')' + r'*' + r'$' 
    # regex looks like: r'(?:a|b|aa|ab|abc)*$' 
    pattern = re.compile(regex) 
    match = pattern.match(word) 
    return match is not None 

def is_valid_key_word(word, pairs): 
    keys = set(pair[0] for pair in pairs) 
    return is_valid_word(word, alphabet=keys) 

def is_valid_value_word(word, pairs): 
    values = set(pair[1] for pair in pairs) 
    return is_valid_word(word, alphabet=values) 

这可以快速（？）排除不可能输入或输出字符串，但它不能真正解决你的问题，如果有足够的回溯，它甚至不会快。

坚持与for循环。