Slide 8.f: Programming Exercise II: calculating a string expression

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:

The string expression is enclosed by a pair of parentheses to meet the Lisp syntax.
A string is enclosed by a pair of double quotes.
Two operators are
- +, which is string concatenation. For example,
```
     ("abc" + " cbxa") = "abc cbxa"
```
- /, which is character removal, which removes all occurrences of the character, the second operand (a one-character string), from the first operand, a string. For example,
```
     ("abc cbxa" / "b") = "ac cxa"
```
Both operators are left-associative and ‘/’ has a higher precedence than ‘+’ has. For example,
```
     ("abc" + "ac cxa" / "a") = "abcc cx"
```
Parentheses are allowed to use to override the precedence. For example,
```
     (("abc" + "ac cxa") / "a") = "bcc cx"
```

Other than the above requirements, the instructor has the following requirements:

The Lisp programs should handle all calculations maybe except of input and output operations and user interface construction.
User-friendliness will be heavily considered when grading.
No error checking is required. So you can assume the input string expression is always correct.
Each interface includes a button Display source, which is to list ALL the source code for implementing the functions of this interface.

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:

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( ).

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:

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.
Before submitting the exercise, test it comprehensively. Absolutely no extra points will be granted after grading.
The exercise must meet the requirements. However, exercises with functions exceeding the requirements will not receive extra credits.
User-friendliness will be heavily considered.
From the source code submitted, the programs will be examined.
Each function will be tested extensively.
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.
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.