用球拍簡化表達式

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

這僅執行一個傳過來的表達。通常你會想要執行通過，直到結果沒有改變。