Subversion Repositories programming

;Written By: Ira Snyder
;Due Date:   02-16-2005
;Homework #: hw08
;License: Public Domain

;ASSUMPTIONS: I chose to use the print format specified in the table
;             on the document that was handed out in class for hw08.
;             The difference is in the spaces between the coefficient
;             and the "x" that is printed. In the table there is a space
;             between the coefficient and the "x", whereas in the example
;             runs on the bottom of the page, there is not a space.
;             The change to make it the same as the example runs is to delete
;             the space between "~A" and "x" in the format statements on
;             lines 111 and 112 (the last two lines in the cond of WRITE-NUM).
;
;             Also, I was forced to assume that the last printed line on the
;             the hw08 handout is incorrect, since the terms are unsorted
;             and have un-combined coefficients with the same exponent.
;             Mine is correct and combines terms with the same exponent
;             and sorts the list from highest to lowest exponent.
;

;;; Given a list in unsorted, unreduced Polynomial
;;; Normal Form, and returns a list in perfect PNF
(defun PNF (L)
  (do ((L L (cdr L))
       (RET nil))
      ((null L) RET)
    (setf RET (INSERT (car L) RET))
    (setf RET (DEL-ZERO-COEF RET))
  )
)

;;; Given a pair of numbers (in a list) and a list of pairs
;;; this inserts the pair into the list in it's correct place
;;; including combining coefficients
(defun INSERT (PAIR LIST)
  (cond
    ((null LIST)                  (cons PAIR LIST))
    ((> (cadr PAIR) (cadar LIST)) (cons PAIR LIST))
    ((= (cadr PAIR) (cadar LIST)) (progn
                                    (setf (caar LIST) (+ (car PAIR) (caar LIST)))
                                    LIST
                                  ))
    (t                            (cons (car LIST ) (INSERT PAIR (cdr LIST))))
  )
)

;;; Deletes all of the pairs that have zero coefficients in
;;; a PNF list
(defun DEL-ZERO-COEF (L)
  (cond
    ((null L) nil)
    ((= 0 (caar L)) (DEL-ZERO-COEF (cdr L)))
    (t              (cons (car L) (DEL-ZERO-COEF (cdr L))))
  )
)

;;; This takes a non-negative integer, and returns a string
;;; containing the number of spaces specified by the integer
(defun SPACES (N)
  (do ((N N (1- N))
       (STR (format nil "")))
      ((zerop N) STR)
    (setf STR (concatenate 'string STR " "))
  )
)

;;; This checks if nil was passed. If it was, print a blank line, then
;;; a "0" line. Else pass the list off to the WRITE-POLY1 function.
(defun WRITE-POLY (L)
  (cond
    ((null L) (format t "~%0~%"))
    (t       (WRITE-POLY1 L))
  )
)

;;; Given a list in Polynomial Normal Form, this will print
;;; the human readable form of the list on two lines.
;;; Example:
;;;   INPUT:  ((1 1) (2 3) (-10 0) (3 2) (2 1))
;;;   OUTPUT:      3      2      
;;;   OUTPUT: + 2 x  + 3 x  + 3 x - 10
(defun WRITE-POLY1 (L)
  (do ((L (PNF L) (cdr L))
       (EXP  (format nil ""))
       (COEF (format nil "")))
      ((null L) (format t "~A~%~A~%" EXP COEF))
    (setf COEF (concatenate 'string COEF (WRITE-NUM (caar L) (cadar L))))
    (MAKE-EQUAL EXP COEF)
    (setf EXP  (concatenate 'string EXP  (WRITE-EXP (caar L) (cadar L))))
    (MAKE-EQUAL EXP COEF)
  )
)

;;; Given a coefficient and an exponent, output the correct expression
;;; to represent it.
;;; Examples:
;;; INPUT:  3 4
;;; OUTPUT: + 3 x
;;;
;;; INPUT:  3 0
;;; OUTPUT: + 3
;;;
;;; INPUT:  -3 0
;;; OUTPUT: - 3
(defun WRITE-NUM (NUM EXP)
  (cond
    ; don't output an x if we have a zero exponent
    ((zerop EXP) (if (plusp NUM) (format nil " + ~A" NUM) 
                                 (format nil " - ~A" (abs NUM))))
    ((plusp NUM) (format nil " + ~A x" NUM))
    (t           (format nil " - ~A x" (abs NUM)))
  )
)

;;; Given a coefficient and an exponent, output the exponent.
;;; NOTE: I chose to have the syntax of WRITE-EXP match the syntax of WRITE-NUM
;;;       even though I do not use the parameter NUM in the code. This was for
;;;       uniformity reasons.
(defun WRITE-EXP (NUM EXP)
  (cond
    ((zerop EXP) nil)
    ((= EXP 1)   nil)
    (t           (format nil "~A" EXP))
  )
)

;;; When called with two strings as arguments, this macro expands to
;;; make them the same length, regardless of which is longer.
(defmacro MAKE-EQUAL (S1 S2)
  `(cond
     ((> (length ,S1) (length ,S2)) (let ((DIFF (- (length ,S1) (length ,S2))))
                                    (setf ,S2 (concatenate 'string ,S2 (SPACES DIFF)))))
     ((< (length ,S1) (length ,S2)) (let ((DIFF (- (length ,S2) (length ,S1))))
                                    (setf ,S1 (concatenate 'string ,S1 (SPACES DIFF)))))
     (t                             nil)
   )
)