Как работает эта программа?

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

def samePattern(main,pattern):
    if pattern=="*" or main==pattern:
        return True
    if main=="":
        return False
    if main[0:1]==pattern[0:1]:
        return samePattern(main[1:],pattern[1:])

    if pattern[0:1]=="*":
        return samePattern(main[1:],pattern) or samePattern(main,pattern[1:])

    return False

Хотя я думаю, что понял базовые случаи, я не понимаю, как линия

if pattern[0:1]=="*":
        return samePattern(main[1:],pattern) or samePattern(main,pattern[1:])

работает.

Может ли кто-нибудь объяснить, как это работает?


python recursion logic wildcard
person Community    schedule 02.10.2015    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Важным битом является то, где находится подстановочный знак:

  • test*
  • te*ing
  • *ing

В первом случае с подстановочным знаком в конце testing and test*:

def samePattern(main,pattern):
    if pattern=="*" or main==pattern:                  #  3.
        return True                                    
    if main=="":                                       #  4.
        return False                                   
   if main[0:1]==pattern[0:1]:                         #  1.
       return samePattern(main[1:],pattern[1:])        #

    if pattern[0:1]=="*":
        return samePattern(main[1:],pattern) or samePattern(main,pattern[1:])
                            ^                       ^
                            | # 2.                  | # 5.

    return False

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

Секция 2. срабатывает и сдвигает только текст на один символ и повторяет попытку.

Раздел 3. попадает, шаблон представляет собой один символ «*» без каких-либо других элементов, и он возвращает True.

Раздел 2. возвращается со значением True, оценка короткого замыкания Python не проверяет другую сторону or, потому что в этом нет необходимости, и все сводится к True успешному совпадению.

Второй случай с подстановочным знаком посередине начинается так же. testing and te*ing:

Раздел 1. проходит как текст, так и шаблон, пока шаблон не дойдет до подстановочного знака.

Теперь текст и шаблон равны sting and *ing, что совпадает с третьим случаем — подстановочный знак впереди.

Третий случай с подстановочным знаком впереди, например. testing and *ing:

Раздел 2. срабатывает, потому что шаблон начинается с *. (Раздел 3 пропущен, потому что это не только звезда). Раздел 2 перемещает один текстовый символ и повторяет попытку с тем же шаблоном.

То же самое происходит снова и снова, пока не сработает раздел 4. и текст не закончится. Теперь это возвращает False.

Теперь первый False вернулся из левой части теста or, правая часть пробуется впервые. Это сдвигает шаблон за подстановочный знак, *ing становится ing.

Но мы все еще глубоко в рекурсии, на последнем символе текста — g and ing, который возвращает False из Раздела 1.

Обе стороны теста or на этой глубине вернули False, так же как и вся строка.

Это возвращается на уровень выше, и проверяется другая сторона теста or этого уровня. ng and ing. Ложь из раздела 1.

Обе стороны теста or на этой глубине вернули False, так же как и вся линия.

Это возвращается на уровень выше, и проверяется другая сторона теста or этого уровня. ing and ing. Правда из раздела 3 и main==pattern.

Это возвращает True, or возвращает True, и все это рушится в кучу Truth.

Все части работают вместе, но, грубо говоря, раздел 1. соответствует тексту, разделы 2 и 3 соответствуют конечным подстановочным знакам, а разделы 4 и 5 соответствуют начальным подстановочным знакам, и они перекрываются, что обеспечивает подстановочные знаки посередине.

Добавление некоторой отладки printf помог мне увидеть, что происходит:

первый

def samePattern(main,pattern):
    print "main", main, "pattern", pattern

[..]

тогда

    if pattern[0:1]=="*":
        x = samePattern(main[1:],pattern)
        print "x", x
        return x or samePattern(main,pattern[1:])
person TessellatingHeckler    schedule 02.10.2015

arrow_upward
1
arrow_downward

если шаблон[0:1]=="*":

Вышеуказанный оператор означает, что когда символ переменной шаблона с индексом 0 равен '*', тогда условие истинно, и после этого он выполняется ниже условного оператора.

возвратить samePattern(main[1:],pattern) или samePattern(main,pattern[1:])

Этот оператор вызывает функцию "samePattern" рекурсивно и передает параметры как (значение основной переменной, начиная с индекса от 1 до n-1 символов, переменная шаблона)

person Community    schedule 02.10.2015

arrow_upward
0
arrow_downward

'*' соответствует 0 или более символов. Последний оператор if говорит: если pattern имеет форму '*' + p, то вернуть True, если:

  • все после первого символа main соответствует шаблону (так что '*' в начале pattern потенциально будет соответствовать большему количеству символов из заголовка main), или
  • p, хвост pattern, соответствует main (мы закончили с '*')
person BrianO    schedule 02.10.2015
comment
[0] не работает с пустой строкой, где срез просто пуст, возможно, поэтому первоначальный автор использовал его. - person jonrsharpe; 02.10.2015
comment
@jonrsharpe Да, ты прав. Я удалил поспешную ложь. Однако похоже, что одно простое изменение позволяет заменить [0:1] на [0]: заменить второе if на if main == '' or pattern == '': return False. Если эта строка достигнута, предыдущая if не удалась, поэтому main не равно pattern; и предположительно мы хотим вернуть False, если main не пусто, а pattern пусто. С этим изменением, если первые два if не работают, то оба main и pattern непусты. - person BrianO; 02.10.2015