Lisp Арифметическое упрощение

Question

Я новичок, когда дело доходит до программирования в lisp и плохой честной рекурсии, не является моей сильной стороной, мне было поручено написать функцию, которая упростила бы арифметические уравнения, но не решила бы их. Вот рекомендации, кстати, это школьный проект.

* Запись функции упрощения, что принимает любое арифметическое выражение, как описано выше (а не только примеры показаны), и возвращает новую функцию, в которой сделаны следующие улучшения, если они возможны:

1. Умножение суб -выражение a. С аргументом 0 в качестве аргумента подвыражение заменяется на 0: (* 3 5 0) -> 0 b. С 1 в качестве аргумента 1 удаляется: (* 1 2 6) -> (* 2 6). Если остается только один аргумент, то подвыражение заменяется на этот аргумент: (* 1 6) -> 6

2. Подвыражение дополнительного a. Любое возникновение 0 исключается: (+ 0 2 7 7) -> (+ 2 7 7). Если только один аргумент остается, то Подвыражение устраняется: (+ 0 7) -> 7

Мои одногруппники, и я написал это до сих пор:

(defun simplify (lis) 
    (cond 
    ((null lis) '()) 
    ((eq (car lis) '*) 
    (cond 
    ((not(null (member '0 lis))) 0) 
    ((not(null (member '1 lis))) (simplify (remove '1 lis))) 
    (t (simplify (cdr lis))) 
    ) 
    ) 

    ((eq (car lis) '+) 
    (cond 
    (t 0) 
    ) 
    ) 
    ((listp (car lis)) (cons (simplify (car lis))(simplify (cdr lis)))) 
    (t (cons (simplify (car lis)) (simplify (cdr lis)))) 

    ) 
) 

Мы не можем заставить его работать правильно, если у вас есть предложения! Вы также можете игнорировать нашу + функцию, которая еще не закончена.

Answer 1

Всегда полезно стараться, чтобы функции были максимально простыми и короткими. Итак, давайте разбейте эту задачу на несколько этапов:

Для обоих + и * существует идентификационный элемент, который вы должны удалить из операции (так как это не влияет на результат).

(defun remove-identity-elements (operands identity) 
    (flet ((is-identity (element) 
      (equal element identity))) 
    (let ((filtered-operands (remove-if #'is-identity operands))) 
     (or filtered-operands (list identity))))) 

Эта функция возвращает список операндов с удаленными элементами идентификации. Обратите внимание, что я добавил чек, чтобы избежать возврата пустого списка, поэтому, если filtered-operands - пустой список (()), то or будет оценивать свой второй аргумент, возвращая список с элементом идентификации как один член.

Для операции, если она вызывается только с одним операндом, вы должны упростить это только для одного операнда. Эта задача является хорошим кандидатом для другой функции:

(defun compact-single-operand-operation (expression) 
    (let ((operands (rest expression))) 
    (if (rest operands) 
     expression 
     (first operands)))) 

Обработка операции может быть сделано первое удаление любых элементов удостоверений из операндов, а затем в конечном итоге удаление операции все вместе:

(defun simplify-operation (operator operands identity) 
    (compact-single-operand-operation 
    (cons operator (remove-identity-elements operands identity)))) 

С эти функции готовы подходить к функции simplify. Прежде всего, нам необходимо покрыть его рекурсивный характер:

Для упрощения операции вам необходимо сначала упростить каждый из своих операндов, так как они могут быть сложными (упрощенными) операциями.

(defun simplify (expression) 
    (if (listp expression) 
     (let ((operator (first expression)) 
      (operands (mapcar #'simplify (rest expression)))) 
     ;; handle operations 
     ) 
     expression)) 

Я использую mapcar с задаваемыми в данный момент функциями simplify получить уже упрощенные операнды. Чтобы остановить эту рекурсию, нам нужен базовый случай: если выражение для упрощения не является списком, мы считаем его «самооценкой» и просто возвращаем его без изменений (это «еще» часть if).

Обработка операций осуществляется с помощью описанной выше функции simplify-operation, хотя нам нужно добавить специальную проверку, чтобы справиться с в операнды умножения возможной 0:

(cond ((eq operator '+) (simplify-operation '+ operands 0)) 
     ((eq operator '*) 
     (if (find 0 operands) 
      0 
      (simplify-operation '* operands 1))) 
     (t (error "Unsupported operation"))) 

Я также положить вместе a live example играть с.