elpanov.com » Обучение » Рекурсии урок 3



Рекурсии в AutoLISP урок 3

В рамках урока 2, мы создали список. Продолжим это занятие, потому, что Лисп умеет работать не только со списками... Рассмотрим мою программу по извлечению из строки данных, разделенных каким либо символом. Например, у нас есть строка:

 
"мы;изучаем;рекурсии"
 

Не сложно заметить, что все слова разделены: ";" И нам необходимо создать список из слов:

 

'("мы" "изучаем" "рекурсии")

 

Напомню работу vl-string-search:

 
(vl-string-search "искомая строка" "строка в которой ищем")

 

возвращаемое значение — число — номер позиции искомого текста во всей строке или NIL. Нумерация начинается с 0.

 
(vl-string-search ";" "мы;изучаем;рекурсии") ; => 2 
(vl-string-search "-" "мы;изучаем;рекурсии") ; => NIL  
 

А вот и сама рекурсия:

 
(defun str-str-lst (str pat / i)
  (cond ((= str "") nil)
        ((setq i (vl-string-search pat str))
         (cons
           (substr str 1 i)
           (str-str-lst (substr str (+ 2 i)) pat)
         ) ;_  cons
        )
        (t (list str))
  ) ;_  cond
) ;_  defun
 

Запускать:

 
(setq str "мы;изучаем;рекурсии" pat ";")
(str-str-lst str pat)

 

Разберем подробнее, как работает данная рекурсия.

 
(setq str "мы;изучаем;рекурсии" pat ";")

 

На этот раз пришлось отказаться от проверки с помощью IF — слишком много нужно делать проверок. Используем COND! Создавать список мы будем методом, разобранном в первом уроке. В первой проверке COND

 
((= str "") nil)

 

Мы проверяем — есть ли в STR какие либо символы, точнее сравниваем содержимое STR с пустой строкой. Если содержимого STR нет — функция вернет NIL Вторая строка кода, начинается с поиска разделителя PAT в STR и присвоение его позиции в переменную I

 
(setq i (vl-string-search pat str))

 

Например:

 
(setq i (vl-string-search ";" "мы;изучаем;рекурсии")) ; i = 2
 

Короче, в этот момент переменная I принимает либо числовое значение, либо NIL если значение NIL — переход на следующую проверку, иначе выполняется:

 
(cons
  (substr str 1 i)
  (str-str-lst (substr str (+ 2 i)) pat)
) ;_  cons
 

Формируем список. Здесь мы добавляем первым элементом результат выражения:

 
(substr str 1 i)
;Это и есть часть строки 'STR,
;с начала и до первого разделителя 'PAT.
;Например:
(substr "мы;изучаем;рекурсии" 1 2) ; => "мы"
 

К результату выражения

 
(str-str-lst (substr str (+ 2 i)) pat)
;Здесь
(substr "мы;изучаем;рекурсии" (+ 2 2)); => "изучаем;рекурсии"
;И все выражение будет выглядеть
(str-str-lst (substr "мы;изучаем;рекурсии" (+ 2 2)) ";")

 

И наконец, в последней проверке, мы видим T

 
(t (list str))

 

Это значит, что ее надо выполнить (если до нее дойдет очередь...) А очередь может дойти, только, если у нас есть, не пустая строка STR и в ней нет разделителей PAT.

 
(list "рекурсии") ; => '("рекурсии")
 

Рассмотрим вычисления для каждого цикла. цикл 1

 
(cond ((= "мы;изучаем;рекурсии" "") nil) ; => nil => переходим дальше
      ((setq i (vl-string-search ";" "мы;изучаем;рекурсии")) ; => 2
       (cons
         (substr "мы;изучаем;рекурсии" 1 2) ; => "мы"
         (str-str-lst
           (substr "мы;изучаем;рекурсии" (+ 2 2)) ; => "изучаем;рекурсии"
           ";"
         ) ; => '("изучаем" "рекурсии")
       ) ;_  cons
      )
      (t (list "мы;изучаем;рекурсии")) ;Не дошли
) ;_  cond
 

результат:

 
'("мы" "изучаем" "рекурсии")

 

цикл 2

 
(cond ((= "изучаем;рекурсии" "") nil) ; => nil => переходим дальше
      ((setq i (vl-string-search ";" "изучаем;рекурсии")) ; => 7
       (cons
         (substr "изучаем;рекурсии" 1 7) ; => "изучаем"
         (str-str-lst
           (substr "изучаем;рекурсии" (+ 2 7)) ; => "рекурсии"
           ";"
           ) ; => '("рекурсии")
       ) ;_  cons
      )
      (t (list "изучаем;рекурсии")) ;Не дошли
) ;_  cond
 

результат:

 
'("изучаем" "рекурсии")

 

цикл 3

 
(cond ((= "рекурсии" "") nil) ; => nil => переходим дальше
      ((setq i (vl-string-search ";" "рекурсии")) ; => nil => переходим дальше
       (cons
         (substr "рекурсии" 1 i)
         (str-str-lst
           (substr "рекурсии" (+ 2 i))
           ";"
         ) ; => '("рекурсии")
       ) ;_  cons
      )
      (t (list "рекурсии")) ; => '("рекурсии")
) ;_  cond
 

результат:

 
'("рекурсии")

 

Само формирование списка получается:

 
(cons
  "мы"
  (cons
    "изучаем"
    '("рекурсии")
  ) ;_  cons
) ;_  cons
 

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

 
(defun str-str-lst (str pat / i)
  (cond ((= str "") nil)
        ((setq i (vl-string-search pat str))
         (cons (substr str 1 i)
               (str-str-lst (substr str (+ (strlen pat) 1 i)) pat)
         ) ;_  cons
        )
        (t (list str))
  ) ;_  cond
) ;_  defun
 

Запускать:

 
(setq str "мы — изучаем — рекурсии" pat " — ")
(str-str-lst str pat)

 

Теперь вы сможете разобраться в ней самостоятельно.

Старая версия сайта, доступна здесь.