Узнайте, где регулярное выражение удовлетворяет предложению

Question

У меня есть предложение и регулярное выражение. Можно ли узнать, где в этом выражении мое предложение удовлетворяет. Например, считаю мое предложение MMMV и регулярное выражение M+V?T*Z+. Теперь регулярное выражение до M+V? удовлетворяет предложениям, а оставшаяся часть регулярного выражения равна T*Z+, что должно быть моим выводом.

Мой подход сейчас состоит в том, чтобы разбить регулярное выражение в отдельных частях и сохранить его в списке, а затем сопоставить путем объединения первых n частей до совпадения предложения. Например, если мое регулярное выражение M+V?T*Z+, то мой список ['M+', 'V?', 'T*', 'Z+']. Затем я сопоставляю свою строку в цикле сначала на M+, затем на M+V? и так далее, пока не будет найдено полное совпадение, а затем беру оставшийся список в качестве вывода. Ниже приведен код

            re_exp = ['M+', 'V?', 'T*', 'Z+']
            for n in range(len(re_exp)):
                re_expression = ''.join(re_exp[:n+1])
                if re.match(r'{0}$'.format(re_expression), sentence_language):
                    return re_exp[n+1:]

Есть ли лучший подход для достижения этого, возможно, с использованием некоторой библиотеки синтаксического анализа и т. Д.

Answer 1

Предполагая, что ваше регулярное выражение довольно простое, без групп, обратных ссылок, подсказок и т. Д., Например, как в вашем случае, следуя шаблону \w[+*?]?, вы можете сначала разбить его на части, как вы уже это делаете.Но затем вместо того, чтобы итеративно объединять части и сопоставлять их со всей строкой, вы можете проверить каждую часть по отдельности, нарезав уже соответствующие части.

def match(pattern, string):
    res = pat = ""
    for p in re.findall(r"\w[+*?]?", pattern):
        m = re.match(p, string)
        if m:
            g = m.group()
            string = string[len(g):]
            res, pat = res + g, pat + p
        else:
            break
    return pat, res

Пример:

>>> for s in "MMMV", "MMVVTTZ", "MTTZZZ", "MVZZZ", "MVTZX":
>>>     print(*match("M+V?T*Z+", s))
...
M+V?T* MMMV
M+V?T* MMV
M+V?T*Z+ MTTZZZ
M+V?T*Z+ MVZZZ
M+V?T*Z+ MVTZ

Тем не менее, обратите внимание, что в худшем случае, если строка длиной n и шаблон из n частей, каждая из которых соответствует только одному символу, это все равно будет иметь значение O (n²) для многократного разрезания строки.

Кроме того, это может завершиться ошибкой, если две последовательные части имеют примерно один и тот же символ, например, a?a+b (который должен быть эквивалентным a+b) не будет соответствовать ab, но только aabпоскольку сингл a уже «потребляется» a?.

Вы можете уменьшить сложность до O (n), написав свой собственный очень простой метод сопоставления регулярных выражений для этого очень сокращенного вида регулярных выражений,но в среднем случае это может не стоить того или даже медленнее.

Answer 2

Вы можете использовать (), чтобы заключить группы в регулярные выражения. Например: M+V?(T*Z+), требуемый вывод сохраняется в первой группе регулярного выражения.

Я знаю, что вопрос говорит о Python, но здесь вы можете увидеть регулярное выражение в действии:

const regex = /M+V?(T*Z+)/;
const str = `MMMVTZ`;
let m = regex.exec(str);

console.log(m[1]);