기본 lisp 만 사용하여 목록에서 패턴을 반복적으로 찾아서 반환합니다.

Question

필자가 작성해야하는 함수는 두 개의 인수 (패턴 (p) 및 목록 (L))를 취합니다. 패턴을 포함하고있는 목록의 일부와 패턴 이후의 모든 것을 찾고 싶습니다. 패턴이 목록에 없으면 nil을 반환합니다.

예 :

입력 (find_pattern '(도움말)'(ineedhelpplease))

출력 'I는 기본적인 LISP 함수를 사용할 수

(helpplease) (COND, 자동차, CDR , 죄수, null, eq,/=). 재귀 적이어야하고 setq와 같은 것을 사용할 수 없습니다.

내 전략 :

나는 될 경우를 추론 :

P = 전무, L = 무기 호 : 패턴이 목록의 끝에있는 경우이 때문에,

nil을 반환 발생

p = nil, L = (none-nil 값) : 패턴이리스트의 중간에있는 경우 발생합니다. 따라서

p = (0이 아닌 값), L = nil : 패턴을 찾을 수 없습니다. NIL 반환

p = (0이 아닌 값), L = (0이 아닌 값) : p와 L의 car가 같으면 p와 L의 cdr을 재귀 적으로 호출합니다. 동일하지 않으면 재귀 적으로 p와 L.의 지휘관과 전화

내 시도 : 나는 부분 패턴 일치를 발견하면

, 나는으로 돌아 결코이를 실행하지 않고

(defun find_pattern (p L) 
    (cond((null p) 
        (cond ((null L) nil) ; p = nil, L = nil 
         (T L)))  ; p = nil, L != nil 
     ((T 
        (cond ((null L) nil) ; p != nil, L = nil 
         ((eq (car p), (car L)) ; p!= nil, L != nil 
         (cons ((car L) (find_pattern (cdr p) (cdr L)))))) 

) 

이미 몇 가지 문제를 참조 전체 패턴. 따라서 '(a b c)'(d a b d a b c)와 같은 입력은 잘못된 결과를 가져옵니다. 또한 부분 결과가 목록에 추가됩니다.

누군가 나를 올바른 방향으로 설정할 수 있습니까? 부분 패턴을 발견했을 때 전체 패턴 검색으로 돌아가려면 어떻게해야합니까?

Answer 1

이 커먼 리스프에서 작동합니다 - 내가 여기에 사용하고 기술은이 라켓에 현재 검색 위치

(defun find-pattern-helper (xs ys src) 
    (cond ((null xs) 
     src) 
     ((null ys) 
     nil) 
     ((eq (car xs) (car ys)) 
     (find-pattern-helper (cdr xs) (cdr ys) src)) 
     (T 
     (find-pattern-helper pat (cdr src) (cdr src))))) 

(defun find-pattern (pat src) 
    (find-pattern-helper pat src src)) 

또는 여기를 추적 도우미에 src의 사본을 함께 전달합니다. .. 내가 좀 리스프에서 빨아 때문에이 (내가 실제로

#lang racket 

(define (find-pattern pat src) 
    (let loop ((xs pat) (ys src) (src src)) 
    (cond ((null? xs) 
      src) 
      ((null? ys) 
      '()) 
      ((eq? (car xs) (car ys)) 
      (loop (cdr xs) (cdr ys) src)) 
      (#t 
      (loop pat (cdr src) (cdr src)))))) 

(find-pattern '(h e l p) '(i n e e d h e l p p l e a s e)) 
;; => '(h e l p p l e a s e) 

(find-pattern '() '(h a y s t a c k)) 
;; => '(h a y s t a c k) 

(find-pattern '(h a y s t a c k) '(h a y)) 
;; => '()