1

我正在编写一个简化多项式的程序，现在只有加法和乘法。

我已经把头撞在键盘上几个小时了，我想是时候寻求帮助了。

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

2 回答 2

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递归调用的意图也更容易理解。

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

于 2012-12-01T08:08:39.700 回答
1

I've only looked at simplify-multiplication but there are a number of issues here.

On a general note, you want to recursively simplify first, then check for specific constants afterwards. (A post-order traversal, I guess.)

Second, I don't see you checking for 1 anywhere so I don't see how (* 1 5) ==> 5 is supposed to work.

Third, let's step through (simplify '(* (+ 2 0) 3)) for a bit:

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

Or (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
                    )
                )
            )
        )
    )
)
于 2012-12-01T01:38:27.337 回答