CSE 341 -- Assignment 3 -- Lisp programming project

October 9, 1995
Due in quiz sections October 24, 1995

Write and test a Lisp function print-polynomial that accepts a Lisp s-expression representing a polynomial in a single variable as input, and prints it out in normal form.

The input should be any legal Lisp expression built up from a single symbol, numbers, and the functions +, -, *, and expt. (The power in the expt function is restricted to non-negative integers.) There should also be a second argument to print-polynomial, namely the symbol that is the single variable. If the input doesn't conform to this definition, print an error message.

The function should print an equivalent expression for in polnomial normal form for a language such as Algol, Pascal, or Ada: that is, an expression using infix notation with standard operator precedence. The polynomial normal form should consist of a sum of terms, where each term is a constant times the variable raised to a power. The terms should be printed with the highest power first. If the coefficient is 1, the coefficient is omitted. If the coefficient is 0, the entire term is omitted. If the power is 0, then the variable is omitted (since x**0 is equal to 1).

Examples:

(print-polynomial '(expt (+ x 1) 2) 'x) prints x**2 + 2*x + 1 (print-polynomial '(* (+ x 1 3) (* 3 x x)) 'x) prints 3*x**3 + 12*x**2 (print-polynomial '(* (+ x 1) (- x 1)) 'x) prints x**2 - 1 (print-polynomial '(+ (* (+ x x) 0) 4) 'x) prints 4 (print-polynomial 0 'x) prints 0 (print-polynomial '(+ x 3 -3) 'x) prints x (print-polynomial '(+ x y) 'x) prints BAD-INPUT (print-polynomial '(/ x 3) 'x) prints BAD-INPUT (print-polynomial '(expt x 0.5) 'x) prints BAD-INPUT

Test your function on a number of examples to demonstrate that it is working correctly, including those given above. Also test it on:

(print-polynomial '(expt (+ x 1) 10) 'x)

The only side effects in your code should be the statements that print the output. Otherwise your solution should be written completely in a functional style -- you may not use other functions with side effects, such as setf, setq, nconc, and so forth. Your code should be well-commented.

Hints

You may find it convenient to use an intermediate normal form for polynomials, for example a list of pairs of coefficients and exponents: ( (coef exp) (coef exp) (coef exp) (coef exp) ... ) For example x**12 - x**7 - x**5 + x + 3 would be represented as ( (1 12) (-1 7) (-1 5) (1 1) (3 0) )

Write a recursive function normalize that takes a Lisp s-expression and returns the intermediate normal form for that expression, and another function print-normalized that takes the normalized form as input and prints out the polynomial. Write other helper functions as needed. If you do this, your print-polynomial function will just be:

(defun print-polynomial (expr var) (print-normalized (normalize expr var))) For more ideas, look at the symbolic differentiation program in the lecture notes, and also Assignment 3 from the Winter 1995 offering of the course (which was also a symbolic algebra assignment).