Function to simplify math expressions

[Liqu1d]

I'm currently trying to write a function to simplify a given expression and the basic simplifcations are working but if there are nested lists i don't get the right result. E.g. if i try to simplify the lisp expression (simplify '(+ 3 (+ (+ 2 2) 2))) i get the result (+ 3 2) but the result should be (+ 3 (+ 4 2)). The function should only simplify a given expression by one step, so if there are nested lists, the function should simplify the innerst one. Another simplify call should then give (+ 3 6).
Here is what i've got so far and all the test i've written, including the one above.

Code: Select all

(defun elementp(e l)
    "Check if an element e is in the given set l."
    (if (null l)
        nil
        (if (equal e (car l))
            t
            (elementp e (cdr l))
        )
    )
)

(defun simplify(expr)
    "Simplify the given expression expr by one step."
    (cond ((atom expr) expr)
        ((and (elementp (car expr) '(+ - * /)) (numberp (cadr expr)) (numberp (caddr expr))) (eval expr))
        ((and (listp (caddr expr)) (elementp (car (caddr expr)) '(+ - * /))) 
            (list (car expr) (simplify (cadr expr)) (simplify (caddr expr)))
        )
        ;;;(+ 0 x)
        ((and (equal (car expr) '+)) (equal (cadr expr) '0) (caddr expr))
        ;;;(+ x 0)
        ((and (equal (car expr) '+) (equal (cadr expr) '0)) (caddr expr))
        ;;;(- x 0)
        ((and (equal (car expr) '-) (equal (caddr expr) '0)) (caddr expr))
        ;;;(- 0 x)
        ((and (equal (car expr) '-) (equal (cadr expr) '0)) (list '- (caddr expr)))
        ;;;(* 0 x) or (* x 0)
        ((and (equal (car expr) '*) (or (equal (cadr expr) '0) (equal (caddr expr) '0))) '0)
        ;;;(exp(t) x 0) or (^ x 0)
        ((and (or (equal (car expr) 'exp) (equal (car expr) 'expt) (equal (car expr) '^)) (equal (caddr expr) '0)) '1)
        ;;;(exp(t) x 1) or (^ x 1)
        ((and (or (equal (car expr) 'exp) (equal (car expr) 'expt) (equal (car expr) '^)) (equal (caddr expr) '1)) (caddr expr))
        ;;;(/ 0 x)
        ((and (equal (car expr) '/) (equal (cadr expr) '0)) '0)
        ;;;(* 1 x)
        ((and (equal (car expr) '*) (equal (cadr expr) '1)) (caddr expr))
        ;;;(* x 1) or (/ x 1)
        ((and (or (equal (car expr) '*) (equal (car expr) '/)) (equal (caddr expr) '1)) (cadr expr))
        ;;;(- x x)
        ((and (equal (car expr) '-) (equal (cadr expr) (caddr expr))) '0)
        ;;;(/ x x)
        ((and (equal (car expr) '/) (equal (cadr expr) (caddr expr))) '1)
    	;;;(sin 0)
    	((and (equal (car expr) 'sin) (equal (cadr expr) '0)) '0)
    	;;;(-sin 0)
    	((and (equal (car expr) '-) (equal (car (cadr expr)) 'sin) (equal (car (cdr (cadr expr))) '0)) '0)
    	;;;(cos 0)
    	((and (equal (car expr) 'cos) (equal (cadr expr) '0)) '1)
    	;;;(-cos 0)
    	((and (equal (car expr) '-) (equal (car (cadr expr)) 'cos) (equal (car (cdr (cadr expr))) '0)) '-1)
    	;;;(tan 0)
    	((and (equal (car expr) 'tan) (equal (cadr expr) '0)) '0)
        ;;;(exp 0)
    	((and (or (equal (car expr) '^) (equal (car expr) 'exp) (equal (car expr) 'expt)) (equal (cadr expr) '0)) '1)
    	;;;(log 1)
    	((and (equal (car expr) 'log) (equal (cadr expr) '1)) '0)
        ;;;Expression could not be simplified.
        (t expr)
    )
)

(format t "~%Simplify Tests")
(print (simplify '(+ 3 (+ (+ 2 2) 2))))
(print (simplify (simplify '(+ 3 (+ 2 (+ 2 2))))))
(print (simplify '(+ 3 (+ 2 (+ 2 2)))))
(print (simplify (simplify (simplify '(+ 3 (+ 2 (+ 2 2)))))))
(print (simplify 'x))
(print (simplify '(- x 0)))
(print (simplify '(+ 3 (+ 2 2))))
(print (simplify '(* 3 (+ 2 3))))
(print (simplify '(2 * 3)))

(format t "~%Basic Tests")
(print (simplify '(+ 2 3)))
(print (simplify '(- 2 3)))
(print (simplify '(* 2 3)))
(print (simplify '(/ 2 3)))
(print (simplify '(+ 0 x)))
(print (simplify '(+ x 0)))
(print (simplify '(- 0 x)))
(print (simplify '(- x 0)))
(print (simplify '(* 0 x)))
(print (simplify '(* x 0)))
(print (simplify '(* 1 x)))
(print (simplify '(* x 1)))
(print (simplify '(/ x 1)))
(print (simplify '(/ x x)))
(print (simplify '(sin 0)))
(print (simplify '(cos 0)))
(print (simplify '(exp 0)))
(print (simplify '(log 1)))
(print (simplify '(expt 2 0)))
(print (simplify '(^ 2 0)))
(print (simplify '(expt 2 1)))
(print (simplify '(^ 2 1)))

I know that the problem is the third cond statement

Code: Select all

((and (listp (caddr expr)) (elementp (car (caddr expr)) '(+ - * /)))
	(list (car expr) (simplify (cadr expr)) (simplify (caddr expr)))
)

but how do i ensure that only the innerst list is simplified, without forgetting the remaining expression?

[pjstirling]

It seems to me that you want to do this in two steps, first walk the tree to figure out the how deep the tree goes, and then walk the tree again simplifying all nodes at that depth