python - 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的标准regex库或其他一些常见的正则表达式实现来做到这一点？我可以通过蛮力来做到这一点，但是如果要检查很多对的话，它会非常无效。

Answer 1

(为了避免英语完全混淆，我将把你的对应对的元素称为“键”和“值”，尽管重复的键阻止它们组成一个典型的字典.)

我相信有几个原因导致您无法仅使用正则表达式来做到这一点。

问题 1. 正则表达式不是 map

正则表达式无法将由某些键序列组成的字符串与其值的翻译关联起来。对于初学者来说，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循环。