Упрощенный сопоставитель регулярных выражений

Question 1

Я работаю над решением некоторых проблем с кодом — отчасти для того, чтобы улучшить решение своих проблем, но также для улучшения качества кода.

Я думаю, что мое текущее (полнофункциональное) решение проблемы довольно надежное и довольно понятное. Однако я хотел бы знать, есть ли в моем стиле что-нибудь, что можно улучшить.

Читателям рекомендуется быть самоуверенными, но при этом четко отделять чисто личные предпочтения от предпочтений, но также настоятельно рекомендуется.

Доброе утро! Вот твоя задача на собеседовании по кодированию на сегодня.
Эту проблему задал Facebook.
Реализуйте сопоставление регулярных выражений со следующими специальными символами:
. (период), который соответствует любому одиночному символу
* (звездочка), который соответствует нулю или более предыдущих элементов
То есть реализовать функцию, которая принимает строку и допустимое регулярное выражение и возвращает, соответствует ли строка регулярному выражению.
Например, учитывая регулярное выражение "ra." и строка "ray", ваша функция должна вернуть истину. То же регулярное выражение в строке "Raymond" должен вернуть false.
Учитывая регулярное выражение ".*at" и строка "chat", ваша функция должна вернуть истину. То же регулярное выражение в строке "chats" должен вернуть false.

# solution.py

from collections import deque
import logging
from typing import Deque, NamedTuple, Optional, Union

logging.basicConfig(level=logging.INFO,format="%(asctime)s - %(levelname)s - %(name)s - %(funcName)s - %(lineno)d : %(message)s")

class Attempt(NamedTuple):
    matched_string : str
    remaining_string : str
    remaining_pattern : str

class DecisionPoint(NamedTuple):
    greedy : Attempt
    non_greedy : Attempt

def advance_attempt(attempt: Attempt, greedy = False) -> Attempt:
        char = attempt.remaining_pattern[0]

        if greedy and char!= '*':
            raise RuntimeError("Can't perform a greedy advancement on a non wildcard char.")

        new_matched_string = attempt.matched_string + char
        if greedy:
            new_remaining_pattern = attempt.remaining_pattern
        else:
            new_remaining_pattern = attempt.remaining_pattern[1:]
        new_remaining_string = attempt.remaining_string[1:]

        return Attempt(matched_string=new_matched_string,
                        remaining_pattern=new_remaining_pattern,
                        remaining_string=new_remaining_string)

def next_char_is_match(next_char : str, string : str) -> bool:
    """Returns true if the supplied next_char in the pattern matches the 
    head of the string. Next char is expected to be a single char or an 
    empty string."""

    if next_char == '':
        return False
    if next_char == '*':
        return True
    if next_char == '.' and len(string) != 0:
        return True
    return next_char == string[0]
    

def take_next_greedy(attempt: Attempt) -> Attempt:
    return advance_attempt(attempt=attempt,greedy=True)

def take_next_non_greedy(attempt : Attempt) -> Attempt:
    return advance_attempt(attempt)

def take_next(attempt : Attempt) -> Optional[Union[DecisionPoint,Attempt]]:
    """Returns None if no next match is possible; otherwise, returns either 
    a single progression of the attempt — i.e., a single character moved into
    the matched field from the remaining field — or, in the case of a wildcard,
    both the greedy and non-greedy next possibilities."""


    if (len(attempt.remaining_string) == 0 
        or len(attempt.remaining_pattern) == 0):
        return None
    next_char_to_match_in_pattern = attempt.remaining_pattern[0]
    next_char_to_match_in_string = attempt.remaining_string[0]
    
    if next_char_to_match_in_pattern == '*':
        return DecisionPoint(greedy=take_next_greedy(attempt),
                             non_greedy=take_next_non_greedy(attempt))

    if (next_char_to_match_in_pattern == next_char_to_match_in_string
        or next_char_to_match_in_pattern == '.'):
        return advance_attempt(attempt)
    
    
    
def main_loop(queue : Deque[Attempt]) -> bool:
        logging.debug(queue)
        logging.info(len(queue))

        attempt = queue.popleft()
        logging.info(attempt)

        if attempt.remaining_pattern == ''
            and attempt.remaining_string == '':
            return True

        next_step = take_next(attempt)

        if next_step is None:
            return False
        elif isinstance(next_step,DecisionPoint):
            queue.appendleft(next_step.non_greedy)
            queue.appendleft(next_step.greedy)
            return False
        else:
            queue.appendleft(next_step)
            return False

def main(pattern : str, string : str) -> bool:
    q = deque()
    q.append(Attempt(matched_string='',
                     remaining_string=string,
                     remaining_pattern=pattern))
    match_found = False
    while len(q) != 0 and not match_found:
        match_found = main_loop(q)
        
    logging.info(match_found) 
    return match_found

if __name__ == '__main__':
    main('.*at*.rq','chatsdafrzafafrq')


# tests.py

import unittest

from .solution import main


class BasicTests(unittest.TestCase):
    def test_given_which_is_expected_to_match_matches(self):
        computed_result = main('ra.','ray')
        self.assertTrue(computed_result)

    def test_given_which_is_expected_to_not_match_does_not_match(self):
        computed_result = main('ra.','raymond')
        self.assertFalse(computed_result)

    def test_other_given_which_is_expected_to_match_matches(self):
        computed_result = main('.*at','chat')
        self.assertTrue(computed_result)
    
    def test_complex_which_is_expected_to_match_matches(self):
        computed_result = main('.*jk*.wee*.weq','jkhkh;llkjkljklkjljl;weeklsfdjdsfj;weq')
        self.assertTrue(computed_result)

    def test_complex_which_is_expected_not_to_match_does_not_match(self):
        computed_result = main('.*jk*.wee*.weqr','jkhkh;llkjkljklkjljl;weeklsfdjdsfj;weqtjhuafjs')
        self.assertFalse(computed_result)

if __name__ == '__main__':
    unittest.main()

Question 2

PEP 8

В Руководство по стилю кода Python перечисляет несколько соглашений для программ Python

Импорт

Все import ... заявления должны предшествовать from ... import ...

Читая документацию PEP 8, я этого не вижу, но мой pylinter жалуется, если этот порядок не соблюдается.

Отступ

Используйте 4 пробела на каждый уровень отступа.

Функции вроде advance_attempt имеют слишком большой отступ.

Организация кода

Импорт
Классы и определения функций
Код

Ваш logging.basicConfig(level=logging.INFO, ...) Оператор подпадает под категорию «Код» и должен стоять после определений класса / функции.

Более того, это ВЫПОЛНЕНО когда модуль импортирован. Он должен находиться внутри основной защиты, чтобы предотвратить непредвиденные побочные эффекты.

Пространства

Запятая

logging.basicConfig(level=logging.INFO,format="...

После каждой запятой должен быть пробел.

Бинарные операторы

if greedy and char!= '*':

С обеих сторон бинарного оператора должны быть пробелы !=.

Типовые подсказки

def take_next_non_greedy(attempt : Attempt) -> Attempt:

Перед :

Ненужные продолжения линии

    if (len(attempt.remaining_string) == 0 
        or len(attempt.remaining_pattern) == 0):
        return None

Нет необходимости в , поскольку выражение заключено в круглые скобки.

Сломанная реализация

Почему '.*jk*.wee*.weq' ожидается соответствие 'jkhkh;llkjkljklkjljl;weeklsfdjdsfj;weq'?

Этот шаблон:

.* любое количество любого символа
j одиночный j
k* 0 или более k
. любой персонаж
we два явных символа
e* любое количество е
. любой персонаж
weq три явных персонажа

Данная строка делает не соответствовать этому шаблону. Тест утверждает, что он должен совпадать. Если образец был написан с .* вместо того *. шаблоны, я действительно мог видеть совпадение успешным. Но это было не так. Предполагая, что совпадение объявлено (я не запускал код), реализация должна быть нарушена.

Question 3

Для полноты, вот обновленный ответ, который включает отзывы:

# solution.py
from __future__ import annotations

import logging
from collections import deque
from typing import Deque, List,NamedTuple, Optional, Union


class Attempt(NamedTuple):
    matched_string : str
    remaining_string : str
    remaining_tokens : List[Token]

class DecisionPoint(NamedTuple):
    greedy : Attempt
    non_greedy : Attempt

class Token(NamedTuple):
    character : str
    is_wildcarded : bool = False

def tokenize(pattern: str) -> List[Token]:
    tokens = []
    while pattern:
        if len(pattern) == 1:
            tokens.append(Token(character=pattern))
            pattern = ''
        else:
            head = pattern[0]
            pattern = pattern[1:]
            if pattern[0] == '*':
                pattern = pattern[1:]
                tokens.append(Token(character=head,
                                    is_wildcarded=True))
            else:
                tokens.append(Token(character=head))
    return tokens

def advance_attempt(attempt: Attempt, greedy: bool = False) -> Attempt:
        next_token = attempt.remaining_tokens[0]
        char = next_token.character

        new_matched_string = attempt.matched_string + char
        if greedy:
            new_remaining_tokens = attempt.remaining_tokens
        else:
            new_remaining_tokens = attempt.remaining_tokens[1:]
        new_remaining_string = attempt.remaining_string[1:]

        return Attempt(matched_string=new_matched_string,
                        remaining_tokens=new_remaining_tokens,
                        remaining_string=new_remaining_string)

def next_token_is_match(next_token: Token, string: str) -> bool:
    """Returns true if the supplied next_char in the pattern matches the 
    head of the string. Next char is expected to be a single char or an 
    empty string."""

    if next_token.character == '.':
        return True
    return next_token.character == string[0]
    

def take_next_greedy(attempt: Attempt) -> Attempt:
    return advance_attempt(attempt=attempt,greedy=True)

def take_next_non_greedy(attempt: Attempt) -> Attempt:
    return advance_attempt(attempt)

def take_next(attempt : Attempt) -> Optional[Union[DecisionPoint,Attempt]]:
    """Returns None if no next match is possible; otherwise, returns either 
    a single progression of the attempt — i.e., a single character moved into
    the matched field from the remaining field — or, in the case of a wildcard,
    both the greedy and non-greedy next possibilities."""


    if (len(attempt.remaining_string) == 0 
        or len(attempt.remaining_tokens) == 0):
        return None
    next_token_to_match_in_pattern = attempt.remaining_tokens[0]
    next_char_to_match_in_string = attempt.remaining_string[0]
    
    if next_token_to_match_in_pattern.is_wildcarded:
        return DecisionPoint(greedy=take_next_greedy(attempt),
                             non_greedy=take_next_non_greedy(attempt))

    if (next_token_to_match_in_pattern.character == next_char_to_match_in_string
        or next_token_to_match_in_pattern.character == '.'):
        return advance_attempt(attempt)
    
    
    
def main_loop(queue: Deque[Attempt]) -> bool:
        logging.debug(queue)
        logging.info(len(queue))

        attempt = queue.popleft()
        logging.info(attempt)

        if (attempt.remaining_tokens == []
            and attempt.remaining_string == ''):
            return True

        next_step = take_next(attempt)

        if next_step is None:
            return False
        elif isinstance(next_step,DecisionPoint):
            queue.appendleft(next_step.non_greedy)
            queue.appendleft(next_step.greedy)
            return False
        else:
            queue.appendleft(next_step)
            return False

def main(pattern: str, string : str) -> bool:
    q = deque()
    q.append(Attempt(matched_string='',
                     remaining_string=string,
                     remaining_tokens=tokenize(pattern)))
    match_found = False
    while len(q) != 0 and not match_found:
        match_found = main_loop(q)
        
    logging.info(match_found) 
    return match_found

logging.basicConfig(level=logging.INFO,
                    format="%(asctime)s - %(levelname)s - %(name)s - %(funcName)s
                        - %(lineno)d : %(message)s")

if __name__ == '__main__':
    main('.*at.*rq','chatsdatfrzafafrq')

# tests.py

import unittest

from .solution import main, tokenize, Token


class TestTokenize(unittest.TestCase):
    def test_basic(self):
        test_pattern = 'a*.d.*'
        expected_result = [Token('a',True),
                           Token('.'),
                           Token('d'),
                           Token('.',True)
                          ]

        computed_result = tokenize(test_pattern)

        self.assertEqual(expected_result,computed_result)
class TestSolution(unittest.TestCase):
    def test_given_which_is_expected_to_match_matches(self):
        computed_result = main('ra.','ray')
        self.assertTrue(computed_result)

    def test_given_which_is_expected_to_not_match_does_not_match(self):
        computed_result = main('ra.','raymond')
        self.assertFalse(computed_result)

    def test_other_given_which_is_expected_to_match_matches(self):
        computed_result = main('.*at','chat')
        self.assertTrue(computed_result)
    
    def test_complex_which_is_expected_to_match_matches(self):
        computed_result = main('.*jk.*wee*.*weq','jkhkh;llkjkljklkjljl;weeklsfdjdsfj;weq')
        self.assertTrue(computed_result)

    def test_complex_which_is_expected_not_to_match_does_not_match(self):
        computed_result = main('.*jk*.wee.*weqr','jkhkh;llkjkljklkjljl;weeklsfdjdsfj;weqtjhuafjs')
        self.assertFalse(computed_result)


if __name__ == '__main__':
    unittest.main()

Упрощенный сопоставитель регулярных выражений

2 ответа
2

PEP 8

Импорт

Отступ

Организация кода

Пространства

Запятая

Бинарные операторы

Типовые подсказки

Ненужные продолжения линии

Сломанная реализация

Добавить комментарий Отменить ответ

2 ответа 2

PEP 8

Импорт

Отступ

Организация кода

Пространства

Запятая

Бинарные операторы

Типовые подсказки

Ненужные продолжения линии

Сломанная реализация

Похожие записи:

Добавить комментарий Отменить ответ

2 ответа
2