lisp簡化多項式

Question

我正在寫一個簡化多項式的程序，現在只是加法和乘法。

我一直在敲我的頭，鍵盤幾個小時了，現在是時候請求一些幫助。

(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 
        ) 
       ) 
      ) 
     ) 
    ) 
) 

這是應該發生的事情：

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

而是我要麼收到我寄給在相同的多項式，或是完全關閉

編輯： 我需要的簡化是從添加中刪除0，以便：

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

和mul帶零點的剔除被刪除

(* 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並使用它們。

• 使用CASE,COND和其他多路條件表達式，而不是嵌套IF - 在哪裏有用。

• 嘗試從域代碼中提取數據結構的遍歷。使用高階函數而不是遞歸（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。遞歸調用的意圖也更清楚地理解。

它仍然不是最佳的，但它應該讓你去。