Subversion Repositories programming

Rev

Rev 66 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
65 irasnyd 1 
;Written By: Ira Snyder
2 
;Due Date:   02-11-2005
3 
;Homework #: hw07
4 
 
5 
;;; The next two functions define a special insertion sort
6 
;;; that will sort a Polynomial-Normal-Form list
7 
(defun ISORT (L)
8 
  (cond
9 
    ((null L) nil)
10 
    (t        (ISORT1 (car L) (ISORT (cdr L))))
11 
  )
12 
)
13 
 
14 
;;; Helper for ISORT
15 
(defun ISORT1 (N L)
16 
  (cond
17 
    ((null L)       (list N))
18 
    ((>= (cadr N) (cadar L)) (cons N L))
19 
    (t              (cons (car L) (ISORT1 N (cdr L))))
20 
  )
21 
)
22 
 
23 
;;; Combines the coefficients of a two part list, L1,
24 
;;; and a list comprised of two part lists, L2
25 
;;; Example: L1 <- (1 1)
26 
;;;          L2 <- ((2 2) (3 3) (4 4) (1 1))
27 
;;; Returns: (2 1)
28 
;;;
29 
;;; It is good for combining the parts of a PNF expression
30 
(defun COMBINE (L1 L2)
31 
  (cond
32 
    ((null L2)                L1)
33 
    ((= (cadr L1) (cadar L2)) (COMBINE (list (+ (car L1) (caar L2)) (cadr L1))
34 
                                       (cdr L2)))
35 
    (t                        (COMBINE L1 (cdr L2)))
36 
  )
37 
)
38 
 
39 
;;; Deletes any two part list contained within the
40 
;;; list L with the exponent given as an argument
41 
;;; Example: EXP <- 1
42 
;;;          L <- ((1 2) (1 1) (3 1) (1 4))
43 
;;; Returns: ((1 2) (1 4))
44 
(defun DEL-EXP (EXP L)
45 
  (cond
46 
    ((null L)          nil)
47 
    ((= EXP (cadar L)) (DEL-EXP EXP (cdr L))) ;remove an element
48 
    (t                 (cons (car L) (DEL-EXP EXP (cdr L))))
49 
  )
50 
)
51 
 
52 
;;; Combines all like terms in a PNF expression, reducing it
53 
;;; completely. It does NOT sort the resulting list however.
54 
(defun MY-REDUCE (L)
55 
  (cond
56 
    ((null L) nil)
57 
    (t        (cons (COMBINE (car L) (cdr L))
58 
                    (MY-REDUCE (DEL-EXP (cadr (COMBINE (car L) (cdr L))) L))))
59 
  )
60 
)
61 
 
66 irasnyd 62 
(defun DEL-ZERO (L)
63 
  (cond
64 
    ((null L) nil)
65 
    ((= 0 (caar L)) (DEL-ZERO (cdr L)))
66 
    (t              (cons (car L) (DEL-ZERO (cdr L))))
67 
  )
68 
)
69 
 
65 irasnyd 70 
;;; This takes a non-reduced, unsorted list representing a
71 
;;; PNF expression, and reduces and sorts it into correct
72 
;;; Polynomial-Normal-Form.
66 irasnyd 73 
(defun PNF (L) (ISORT (DEL-ZERO (MY-REDUCE L))))
65 irasnyd 74