1

我有一个函数可以区分方程并将其作为列表打印到屏幕上。我现在要做的是一个函数，它接受像这样返回的表达式：'(+ (* x 0) (* 2 1)) 并简化答案。摆脱 x*0，因为它总是计算为零并将 2*1 替换为 2，最终只返回 2，因为 2 + 0 是 2。这是我到目前为止所拥有的，显然它非常缺乏，任何帮助获得这个开始将不胜感激。

(define (simplify expr)
  (if (not (list? expr))
      expr
      (if (null? (cdr expr)) 
          (car expr)
          (case (car expr)
           ((+
               ))

       ))
4

2 回答 2

3

假设您只有带有 '* 和 '+ 作为运算符的二进制表达式，那么使用要简化的表达式的递归下降来编码代数的基本规则就很容易了。如此：

(define (simplify exp)
 (cond ((number? exp) exp)
       ((symbol? exp) exp)
       ((list?   exp)
        (assert (= 3 (length exp)))
        (let ((operator  (list-ref exp 0))
              (operand-1 (simplify (list-ref exp 1)))   ; recurse
              (operand-2 (simplify (list-ref exp 2))))  ; recurse
          (case operator
            ((+)
             (cond ((and (number? operand-1) (= 0 operand-1)) operand-2)
                   ((and (number? operand-2) (= 0 operand-2)) operand-1)
                   ((and (number? operand-1) (number? operand-2)) 
                    (+ operand-1 operand-2))
                   (else `(,operator ,operand-1 ,operand-2))))

            ((*)
             (cond ((and (number? operand-1) (= 0 operand-1)) 0)
                   ((and (number? operand-2) (= 0 operand-2)) 0)
                   ((and (number? operand-1) (= 1 operand-1)) operand-2)
                   ((and (number? operand-2) (= 1 operand-2)) operand-1)
                   ((and (number? operand-1) (number? operand-2)) 
                    (* operand-1 operand-2))
                   (else `(,operator ,operand-1 ,operand-2))))
            (else 'unknown-operator))))
       (else 'unknown-expression)))

这仅对表达式执行一次传递。通常，您希望执行通行证，直到结果不变。

于 2013-03-28T14:31:05.037 回答
3

这类问题的一般解决方案并不是那么简单。为了让你开始，考虑使用重写规则，看看simplify文章A Hacker's Introduction to Partial Evaluation 的第 4 节中显示的过程：

We can use rewrite rules to simplify algebraic expressions. For example,

> (simplify '(+ (* 3 x) (* x 3)))
; (* 6 x)

This works by applying a list of rules to all parts of the subject expression
repeatedly until no more simplifications are possible:

(define *simplification-rules*
  '(((+ ?x ?x)          (* 2 ?x))
    ((* ?s ?n)          (* ?n ?s))
    ((* ?n (* ?m ?x))   (* (* ?n ?m) ?x))
    ((* ?x (* ?n ?y))   (* ?n (* ?x ?y)))
    ((* (* ?n ?x) ?y)   (* ?n (* ?x ?y)))))

The left hand column has patterns to match, while the right hand holds responses. 
The first rule says, if you see (+ foo foo), rewrite it into (* 2 foo). Variables 
like ?x can match anything, while ?m and ?n can only match numbers.
于 2013-03-28T13:39:13.350 回答