scheme - 表达式简化

Question

我有这段代码来计算导数:

(define (diff x expr)
  (if  (not (list? expr))
    (if  (equal? x expr) 1 0)
    (let ((u (cadr expr)) (v (caddr expr)))
     (case (car expr)
       ((+) (list '+ (diff x u) (diff x v)))
       ((-) (list '- (diff x u) (diff x v)))
       ((*) (list '+
                   (list  '* u (diff x v))
                   (list  '* v (diff x u))))
        ((/) (list ‘div (list '-
                  (list  '* v (diff x u))
                  (list  '* u (diff x v)))
                  (list  '* u v)))
))))

如何简化代数表达式？

代替 x + x 显示 2x

和

代替 x * x 显示 x^2

Answer 1

代数表达式的简化非常困难，尤其是与导数的计算相比。应该递归地进行简化。您首先简化最内层的表达式。一次不要尝试太多。我将从最基本的简化开始，例如:

 0 + x -> x
 0 * x -> 0
 1 * x -> x
 x ^ 0 -> 1
 x ^ 1 -> x

用加法代替减法，用乘法代替除法

 x - y -> x + (-1)*x
 x / y -> x ^ (-1)

这可能看起来不像是一种简化，但它会简化您的代码。您始终可以在最后撤消此步骤。

然后使用结合律和交换律对术语进行排序。将数值移到左侧，按一些预定义的顺序对变量进行排序(不必按字母顺序排列，但应该始终相同)

 (x * y) * z -> x * (y * z)
 x * 2 -> 2 * x
 2 * (x * 3) -> 2 * (3 * x)

化简指数

  (x ^ y) ^ z -> x^(y * z)

简化数字部分。

 2 * (3 * x) -> 6 * x
 2 + (3 + x) -> 5 + x

完成此操作后，您可以考虑收集常用表达式。