用球拍简化表达式

Question

我有一个区分方程式并将其作为列表打印到屏幕的功能。我现在想做的是一个函数，它返回如下形式的表达式： '（+（* x 0）（* 2 1）） 并简化了答案。获取摆脱x * 0，因为它总是计算为零并用2代替2 * 1，因为2 + 0是2，所以最终只返回2。 这就是我迄今为止的情况，显然它非常缺乏，这开始将不胜感激。

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

     )) 

Answer 1

对于这类问题的一般解决方法是不是简单。为了让您一开始，考虑使用重写规则，您可以在文章A Hacker's Introduction to Partial Evaluation第4所示看看simplify过程：

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. 

Answer 2

假设你刚刚有二元表达式“*和” +为运营商来说，很容易编码代数的基本规则，并简化表达式的递归下降。像这样：

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

这仅执行一个传过来的表达。通常你会想要执行通过，直到结果没有改变。