Lisp 算术简化

Question

我是 lisp 编程的新手，老实说递归不是我的强项，我的任务是编写一个函数来简化算术方程但不求解它们。这是指南，顺便说一下，这是一个学校项目。

*编写函数 simplify 接受上述任何算术表达式(不仅仅是所示示例)并返回一个新函数，其中进行了以下改进(如果可能的话):

1. 乘法子表达式 A。以 0 作为参数，子表达式被 0 替换:(* 3 5 0) -> 0 b.使用 1 作为参数，删除 1:(* 1 2 6) -> (* 2 6)。如果只剩下一个参数，则子表达式将替换为该参数:(* 1 6) -> 6

2. 加法子表达式 A。消除任何出现的 0:(+ 0 2 7 7) -> (+ 2 7 7)。如果只剩下一个参数，则删除子表达式:(+ 0 7) -> 7

到目前为止，我和我的小组成员已经写了这篇文章:

(defun simplify (lis)
  (cond
   ((null lis) '())
   ((eq (car lis) '*)
    (cond
     ((not(null (member '0 lis))) 0)
     ((not(null (member '1 lis))) (simplify (remove '1 lis)))
     (t (simplify (cdr lis)))
     )
    )

   ((eq (car lis) '+)
    (cond
     (t 0)
     )
    )
   ((listp (car lis)) (cons (simplify (car lis))(simplify (cdr lis))))
   (t (cons (simplify (car lis)) (simplify (cdr lis))))

   )
  )

如果您有任何建议，我们无法让它正常工作!也谢谢你，你可以忽略我们未完成的 + 功能。

Answer 1

尝试使函数尽可能简单和简短总是好的。因此，让我们将此任务分解为多个步骤:

对于 + 和 * 都有一个标识元素，您应该将其从操作中删除(因为它不会影响结果)。

(defun remove-identity-elements (operands identity)
  (flet ((is-identity (element)
           (equal element identity)))
    (let ((filtered-operands (remove-if #'is-identity operands)))
      (or filtered-operands (list identity)))))

此函数返回删除了标识元素的操作数列表。请注意，我添加了一个检查以避免返回空列表，因此如果 filtered-operands 是一个空列表 (())，则 或 将计算它的第二个参数，返回一个以标识元素作为单个成员的列表。

对于一个操作，如果它只用一个操作数调用，你应该将它简化为只有一个操作数。该任务很适合另一个功能:

(defun compact-single-operand-operation (expression)
  (let ((operands (rest expression)))
    (if (rest operands)
      expression
      (first operands))))

然后可以通过首先从操作数中删除任何标识元素然后最终一起删除操作来处理操作:

(defun simplify-operation (operator operands identity)
  (compact-single-operand-operation
   (cons operator (remove-identity-elements operands identity))))

准备好这些函数后，我们就可以使用simplify 函数了。首先，我们需要覆盖它的递归性质:

为了简化操作，您需要首先简化它的每个操作数，因为它们也可能是复杂的(可简化的)操作。

(defun simplify (expression)
  (if (listp expression)
      (let ((operator (first expression))
            (operands (mapcar #'simplify (rest expression))))
        ;; handle operations
        )
      expression))

我正在使用 mapcar 和当前定义的函数 simplify 来获得已经简化的操作数。为了停止这种递归，我们需要一个基本情况:如果要简化的表达式不是列表，那么我们将其视为“ self 评估”并原封不动地返回它(这是 if< 的“else”部分)。

使用上面的函数 simplify-operation 来处理操作，尽管我们需要添加一个特殊的检查来处理乘法操作数中可能的 0 :

(cond ((eq operator '+) (simplify-operation '+ operands 0))
      ((eq operator '*)
       (if (find 0 operands)
           0
           (simplify-operation '* operands 1)))
      (t (error "Unsupported operation")))

我也整理了a live example一起玩。