Slide 8.e: How to write functions
Slide 8.g: Using Lisp
Home

Programming Exercise II: Calculating a String Expression


Absolutely no copying others' work

Due Date
Monday, November 17, 2008 in class. Turn in hard-copy source code of all programs such as Lisp and Perl.



The Objectives
Design and implement a string-expression calculator. This exercise is for students to learn how to write programs by using a functional language, Lisp.



Requirements
The on-line string calculator includes the following features: Other than the above requirements, the instructor has the following requirements:

An Infix-to-Prefix Example
You may use the function inf-to-pre( ), which is to convert an infix expression to a prefix one, in this exercise:


An Infix String Expression:



A Prefix String Expression:



       


      Password:    

The source code of the function inf-to-pre( ) is as follows:

  inf-to-pre.lsp  
(defun  inf-to-pre  (ae)
  (cond  ((atom ae)  ae)
         (T  (inf-aux  ae nil nil))))
(defun  inf-aux  (ae  operators operands)
  (inf-iter  (cdr  ae)
             operators
             (cons  (inf-to-pre  (car ae))  operands)))
(defun  inf-iter  (ae  operators operands)
  (cond  ((and  (null  ae)  (null  operators))
          (car  operands))
         ((and  (not  (null  ae))
                (or   (null operators)
                      (> (weight  (car  ae))
                         (weight  (car  operators)))))
          (inf-aux  (cdr  ae)
                    (cons  (car  ae)  operators)
                    operands))
         (T  (inf-iter  ae
                        (cdr  operators)
                        (cons  (list  (opcode  (car  operators))
                                      (cadr  operands)
                                      (car  operands))
                               (cddr  operands))))))
(defun  weight  (operator)
  (cond  ((equal  operator '=)  0)
         ((equal  operator '+)  1)
         ((equal  operator '-)  1)
         ((equal  operator '*)  2)
         ((equal  operator '/)  2)
         ((equal  operator '\\) 2)
         ((equal  operator '^)  3)
         (T  (print  `(,operator not an operator)) 4)))
(defun  opcode  (operator)
  (cond  ((equal  operator '=)  'setq)
         ((equal  operator '+)  '+)
         ((equal  operator '-)  '-)
         ((equal  operator '*)  '*)
         ((equal  operator '/)  '/)
         ((equal  operator '\\) 'rem)
         ((equal  operator '^)  'expt)
         (T  (print  `(,operator not an operator)) operator)))

For how to write Lisp programs, check Practical Common Lisp.



An Exercise Example
The following is an example of this exercise, which is with less than 20 lines without including the function inf-to-pre( ).


An Infix String Expression:



The Result String:



       


      Password:    




Possible Lisp Instructions Used
The following instructions may be used in this exercise without including the function inf-to-pre( ):

No. Instruction Description
1 atom The predicate atom is true if its argument is not a cons, and otherwise is false.
2 car This returns the car of list, which must be a cons or ( ).
3 cdr This returns the cdr of list, which must be a cons or ( ).
4 char string index The character at position index of the string is returned as a character object.
5 concatenate The result is a new sequence that contains all the elements of all the sequences in order.
6 cond A cond form has a number (possibly zero) of clauses, which are lists of forms. Each clause consists of a test followed by zero or more consequents.
7 defun The usual means of defining named functions
8 equal true if its arguments are structurally similar (isomorphic) objects.
9 null null is true if its argument is ( ), and otherwise is false.
10 open Opens a file.
11 princ princ returns the object as its value.
12 print Evaluates its single argument and prints it on a new line.
13 quote (quote x) simply returns x.
14 read read reads in the printed representation of a Lisp object from input-stream.
15 remove Returns a sequence from which the elements that satisfy the test have been removed.
16 setq A simple variable assignment statement
17 T The value of T is always T.



Evaluation
The following features will be considered when grading:
  1. This exercise will not be graded if the system entry interface can not be found at http://people.cs.und.edu/~userid/532/2/, and redirection (http-equiv="refresh") to the pages not hosted by http://people.cs.und.edu/~userid/ is prohibited.
  2. Before submitting the exercise, test it comprehensively. Absolutely no extra points will be granted after grading.
  3. The exercise must meet the requirements. However, exercises with functions exceeding the requirements will not receive extra credits.
  4. User-friendliness will be heavily considered.
  5. From the source code submitted, the programs will be examined.
  6. Each function will be tested extensively.
  7. Firefox 3.0 browser will be used to grade exercises. Note that Internet Explorer and Firefox are not compatible. That is your exercises may work on the IE but not Firefox.
  8. The hard-copy exercises will be kept until the end of this semester. They will be used to check against others' exercises. The instructor will inform you the exercise evaluations by emails after grading.