Subversion Repositories programming

irasnyd@duallie lisp $ cat hw07.lisp

;Written By: Ira Snyder

;Due Date:   02-11-2005

;Homework #: hw07

;;; The next two functions define a special insertion sort

;;; that will sort a Polynomial-Normal-Form list

(defun ISORT (L)

  (cond

    ((null L) nil)

    (t        (ISORT1 (car L) (ISORT (cdr L))))

  )

)

;;; Helper for ISORT

(defun ISORT1 (N L)

  (cond

    ((null L)       (list N))

    ((>= (cadr N) (cadar L)) (cons N L))

    (t              (cons (car L) (ISORT1 N (cdr L))))

  )

)

;;; Combines the coefficients of a two part list, L1, 

;;; and a list comprised of two part lists, L2

;;; Example: L1 <- (1 1)

;;;          L2 <- ((2 2) (3 3) (4 4) (1 1))

;;; Returns: (2 1)

;;;

;;; It is good for combining the parts of a PNF expression

(defun COMBINE (L1 L2)

  (cond

    ((null L2)                L1)

    ((= (cadr L1) (cadar L2)) (COMBINE (list (+ (car L1) (caar L2)) (cadr L1))

                                       (cdr L2)))

    (t                        (COMBINE L1 (cdr L2)))

  )

)

;;; Deletes any two part list contained within the

;;; list L with the exponent given as an argument

;;; Example: EXP <- 1

;;;          L <- ((1 2) (1 1) (3 1) (1 4))

;;; Returns: ((1 2) (1 4))

(defun DEL-EXP (EXP L)

  (cond

    ((null L)          nil)

    ((= EXP (cadar L)) (DEL-EXP EXP (cdr L))) ;remove an element

    (t                 (cons (car L) (DEL-EXP EXP (cdr L))))

  )

)

;;; Combines all like terms in a PNF expression, reducing it

;;; completely. It does NOT sort the resulting list however.

(defun MY-REDUCE (L)

  (cond

    ((null L) nil)

    (t        (cons (COMBINE (car L) (cdr L)) 

                    (MY-REDUCE (DEL-EXP (cadr (COMBINE (car L) (cdr L))) L))))

  )

)

(defun DEL-ZERO (L)

  (cond

    ((null L) nil)

    ((= 0 (caar L)) (DEL-ZERO (cdr L)))

    (t              (cons (car L) (DEL-ZERO (cdr L))))

  )

)

;;; This takes a non-reduced, unsorted list representing a

;;; PNF expression, and reduces and sorts it into correct

;;; Polynomial-Normal-Form.

(defun PNF (L) (ISORT (DEL-ZERO (MY-REDUCE L))))

irasnyd@duallie lisp $ cat hw07test.lisp

; Test cases for CS 352, Winter 2005, Homework 7.

(defun TEST nil

  (TEST1 nil)

  (TEST1 '((1 1)))

  (TEST1 '((0 1)))

  (TEST1 '((1 1)(1 1)))

  (TEST1 '((1 1)(-1 1)))

  (TEST1 '((2 0)(3 1)(4 2)))

  (TEST1 '((4 2)(3 1)(2 0)))

  (TEST1 '((4 2)(3 1)(2 0)(-3 1)))

  (TEST1 '((3 1)(2 1)(-4 1)))

  (TEST1 '((1 2)(-5 0)(2 2)(-3 1)(5 0)(-3 2)(3 1)))

  (TEST1 '((1 2)(2 0)(2 1)(2 3)(3 1)(7 0)))

)

(defun TEST1 (TERMS)

  (format t "~%in  ~s~%" TERMS)

  (format t "out ~s~%" (PNF TERMS))

)

irasnyd@duallie lisp $ clisp -q

[1]> (load 'hw07.lisp)

;; Loading file hw07.lisp ...

;; Loaded file hw07.lisp

T

[2]> (load 'hw07test.lisp)

;; Loading file hw07test.lisp ...

;; Loaded file hw07test.lisp

T

[3]> (test)

in  NIL

out NIL

in  ((1 1))

out ((1 1))

in  ((0 1))

out NIL

in  ((1 1) (1 1))

out ((2 1))

in  ((1 1) (-1 1))

out NIL

in  ((2 0) (3 1) (4 2))

out ((4 2) (3 1) (2 0))

in  ((4 2) (3 1) (2 0))

out ((4 2) (3 1) (2 0))

in  ((4 2) (3 1) (2 0) (-3 1))

out ((4 2) (2 0))

in  ((3 1) (2 1) (-4 1))

out ((1 1))

in  ((1 2) (-5 0) (2 2) (-3 1) (5 0) (-3 2) (3 1))

out NIL

in  ((1 2) (2 0) (2 1) (2 3) (3 1) (7 0))

out ((2 3) (1 2) (5 1) (9 0))

NIL

[4]> (bye)

irasnyd@duallie lisp $