lisp 단순화 다항식

Question

나는 polynimials를 단순화하는 프로그램을 작성하고 있으며, 현재는 덧셈과 곱셈 만 사용하고 있습니다.

저는 몇 시간 동안 키보드를 두드리고 키보드를 몇 시간 동안 사용하여 도움을 요청했습니다.

(simplify ‘(+ x (+ 0 3) (* 1 5) (* (* x y z) 0) )) --> (+ x 3 5) 
(simplify ‘(* (+ 6 0) (* 1 6 2))) --------------------------------> (* 6 (* 6 2)) 

대신 내가 하나 같은 난에 전송 다항식, 또는 완전히 꺼 뭔가를 얻을

편집 :

(defun simplify (lis) 
    (if (eq (car lis) '+) 
     (cons '+ (simplify-addition (cdr lis))) 
     (if (eq (car lis) '*) 
      (cons '* (simplify-multiplication (cdr lis))) 
     ) 
    ) 
) 
(defun simplify-addition (lis) 
    (if (not (null lis)) 
     (if (listp (car lis)) 
      (list (simplify (car lis)) (simplify-addition (cdr lis))) 
      (if (numberp (car lis)) 
       (if (eq (car lis) 0) 
        (simplify-addition (cdr lis)) 
        (if (null (cdr lis)) 
         lis 
         (cons (car lis) (simplify-addition (cdr lis))) 
        ) 
       ) 
       (if (eq (car lis) '+) 
        (list (car lis) (simplify-addition (cdr lis))) 
        (if (eq (car lis) '*) 
         (list (car lis) (simplify-addition (cdr lis))) 
         lis 
        ) 
       ) 
      ) 
     ) 
    ) 
) 

(defun simplify-multiplication (lis) 
    (if (not (null lis)) 
     (if (listp (car lis)) 
      (if (find 0 (car lis)) 
       0 
       (list (simplify (car lis)) (simplify-multiplication (cdr lis))) 
      ) 
      (if (numberp (car lis)) 
       (if (null (cdr lis)) 
        lis 
        (cons (car lis) (simplify-multiplication (cdr lis))) 
       ) 
       (if (eq (car lis) '+) 
        (list (car lis) (simplify-multiplication (cdr lis))) 
        (if (eq (car lis) '*) 
         (list (car lis) (simplify-multiplication (cdr lis))) 
         lis 
        ) 
       ) 
      ) 
     ) 
    ) 
) 

이 발생해야하는 것입니다 내가 필요로하는 단순화하는 것입니다 추가에서 0을 제거하면 다음과 같이됩니다.

(+ 3 0) --> 3 
(+ 4 0 6) --> (+ 4 6) 

0으로 tiplication이 제거됩니다.

(* 6 0 7) --> 0 

Answer 1

저는 단지 simplify-multiplication을 보았습니다. 그러나 여기에는 많은 문제점이 있습니다.

일반적으로 처음부터 재귀 적으로 단순화 한 다음 나중에 특정 상수를 확인하려고합니다. (추후 주문 순회, 아마도 그렇습니다.)

두 번째로 1을 확인하는 것은 보이지 않으므로 (* 1 5) ==> 5이 어떻게 작동하는지 보지 못합니다.

셋째, 이제 조금 (simplify '(* (+ 2 0) 3))를 단계별로하자

(defun simplify-multiplication (lis) 
; lis = '((+ 2 0) 3) 
    (if (not (null lis)) 
    ; ==> t 
     (if (listp (car lis)) 
     ; (car lis) = '(+ 2 0), so (listp '(+ 2 0)) ==> t 
      (if (find 0 (car lis)) 
      ; succeeds because '(+ 2 0) contains 0 
      ; this is completely wrong! you're not supposed to check sublists of lis 
       0 
       ; ... yeah, you just returned 0 just because there was a 0 *somewhere* 
       (list (simplify (car lis)) (simplify-multiplication (cdr lis))) 
      ) 
      ... 

또는 (simplify '(* 0 2)) :

(defun simplify-multiplication (lis) 
; lis = '(0 2) 
    (if (not (null lis)) 
    ; ==> t 
     (if (listp (car lis)) 
     ; (car lis) = 0, so (listp 0) ==> nil 
      (if (find 0 (car lis)) 
       0 
       (list (simplify (car lis)) (simplify-multiplication (cdr lis))) 
      ) 
      (if (numberp (car lis)) 
      ; (numberp 0) ==> t 
       (if (null (cdr lis)) 
       ; (cdr lis) = '(2), so (null '(2)) ==> nil 
        lis 
        (cons (car lis) (simplify-multiplication (cdr lis))) 
        ; ... wait, what? 
        ; you're just recursively walking through the list without 
        ; checking what numbers you actually got. this won't simplify 
        ; anything. 
       ) 
       (if (eq (car lis) '+) 
       ; what is this branch for? it can only succeed if you have code of the form 
       ; (* 1 + 2) 
       ; which is a syntax error 
        (list (car lis) (simplify-multiplication (cdr lis))) 
        (if (eq (car lis) '*) 
        ; this branch is for code like (* * *). huh??? 
         (list (car lis) (simplify-multiplication (cdr lis))) 
         lis 
        ) 
       ) 
      ) 
     ) 
    ) 
) 

Answer 2

먼저 당신이 읽을 수 있도록 코딩 스타일을 조금 개선 할 수 있습니다.

• 자신의 줄에 괄호를 넣지 마십시오. 이것은 공간을 낭비하고 전혀 도움이되지 않습니다.

• 도메인 특정 코드에서 CAR 및 CDR을 사용하지 마십시오. 도메인은 수학입니다. 표현식 (operator arg1 arg2)을 사용합니다. 대신 CAR과 CDR을 사용하여 함수 OPERATOR과 ARGUMENTS을 정의하고 사용하십시오.

• IF 중첩 대신에 CASE, COND 및 기타 여러 가지 조건문을 사용할 수 있습니다.

• 도메인 코드에서 데이터 구조의 순회를 추출하려고합니다. 재귀 (MAP, REDUCE, ...) 대신 고차 함수를 사용하십시오.

예 :

몇 가지 기본 도메인 기능 :

이제

(defun operator (expression) 
    (first expression)) 

(defun arguments (expression) 
    (rest expression)) 

(defun make-expression (operator arguments) 
    (if (= (length arguments) 1) 
     (first arguments) 
    (cons operator arguments))) 

(defun is-zero? (expression) 
    (and (numberp expression) 
     (= expression 0))) 

단순화 :

(defun simplify (expression) 
    (if (atom expression) 
     expression 
    (case (operator expression) 
     (+ (make-expression '+ (simplify-addition  (arguments expression)))) 
     (* (make-expression '* (simplify-multiplication (arguments expression))))))) 

(defun simplify-addition (expressions) 
    (remove-if #'is-zero? 
      (mapcar #'simplify 
        (remove-if #'is-zero? expressions)))) 

(defun simplify-multiplication (expressions) 
    (if (member-if #'is-zero? expressions) 
     (list 0) 
    (let ((expressions1 (mapcar #'simplify expressions))) 
     (if (member-if #'is-zero? expressions1) 
      (list 0) 
     expressions1)))) 

참조, 코드가 얼마나 더 읽을 수? 더 이상 CAR, LIS, CDR. 재귀 적 호출의 의도 또한 훨씬 명확하게 이해할 수 있습니다.

여전히 최적은 아니지만 계속해야합니다.