Упростите выражения с помощью Racket

У меня есть функция, которая различает уравнение и выводит его в виде списка на экран. Сейчас я хочу сделать функцию, которая принимает выражение, возвращаемое следующим образом: '(+ (* 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)
           ((+
               ))

       ))

expression simplify scheme racket
person dukedevil294    schedule 28.03.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Общее решение для такого рода проблем не такое простое. Для начала подумайте об использовании правил перезаписи, взгляните на процедуру simplify, показанную в разделе 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.
person Óscar López    schedule 28.03.2013
comment
Это зависит от контекста. Я процитировал дословно из источника, иногда в качестве имени переменной используют ?s, ?n и т.д., вместо ?x - person Óscar López; 28.03.2013

arrow_upward
3
arrow_downward

Предполагая, что у вас есть только бинарные выражения с '* и '+ в качестве операторов, достаточно легко закодировать основные правила алгебры с рекурсивным спуском выражения, которое нужно упростить. Как так:

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

Это выполняет только один проход по выражению. Как правило, вы хотите выполнять проходы до тех пор, пока результат не изменится.

person GoZoner    schedule 28.03.2013