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)

并删除与零的乘法。

(* 6 0 7) --> 0 

Answer 1

首先，您可能希望稍微改进一下您的编码风格，使其具有可读性。

• 不会将括号放在自己的行上。这只会浪费空间，而且没有任何帮助。
• 不会在领域特定的代码中使用CAR和CDR。这个领域是数学。您可以使用expressions (operator arg1 arg2)。相反，使用CAR和CDR定义函数OPERATOR和ARGUMENTS并使用它们。
• 使用CASE、COND和其他多路条件表达式，而不是嵌套的IF - where有用。< code >H214
• 尝试从域代码中提取数据结构的遍历。使用高阶函数而不是递归(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。递归调用的意图也更容易理解。

它仍然不是最优的，但它应该会让你继续前进。

Answer 2

我只看过simplify-multiplication，但这里有很多问题。

一般来说，您希望首先以递归方式简化，然后检查特定的常量。(我猜是后序遍历。)

其次，我没有看到你检查1 anywhere，所以我不知道(* 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
                    )
                )
            )
        )
    )
)