Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Assignments

Assignment #2

Blank, Fall 2014

Due: Please bring two hardcopies to class Thursday, Sept 18, 2014

In the following problems, please define the function, and test it to make sure it works. I have provided a few examples, but you should test your function thoroughly to make sure that it works.

If it doesn't work in some instances, you should demonstrate where it fails. Otherwise, I will assume that you don't know that it fails.

1. Problem: remove-first

remove-first takes an item and a list, and removes the first occurence of item in the list.

In [52]:
(define remove-first
  (lambda (item lyst)
In [53]:
(remove-first 'a '())
Out[53]:
()
In [54]:
(remove-first 'a '(a))
Out[54]:
()
In [55]:
(remove-first 'a '(a a a))
Out[55]:
(a a)
In [56]:
(remove-first 'a '(b c a))
Out[56]:
(b c)
In [57]:
(remove-first 'a '(a a b c a))
Out[57]:
(a b c a)
In [58]:
(remove-first 'a '(b c d))
Out[58]:
(b c d)

2. Problem: remove-all

remove-all takes an item and a list and removes all occurences of item from the list.

In [59]:
(define remove-all
  (lambda (item lyst)
In [60]:
(remove-all 'a '())
Out[60]:
()
In [61]:
(remove-all 'a '(a))
Out[61]:
()
In [62]:
(remove-all 'a '(a a a))
Out[62]:
()
In [63]:
(remove-all 'a '(b a c a d a))
Out[63]:
(b c d)

3. Problem: remove-nth

remove-nth takes a number (1-based indexing), an item, and a list. It removes the nth instance of item in the list.

In [64]:
(define remove-nth
  (lambda (n item lyst)
In [65]:
(remove-nth 1 'a '(a b a c a d))
Out[65]:
(b a c a d)
In [66]:
(remove-nth 2 'a '(a b a c a d))
Out[66]:
(a b c a d)
In [67]:
(remove-nth 3 'a '(a b a c a d))
Out[67]:
(a b a c d)

4. Problem: substitute

substitute takes an item to search for, an item to replace it, and a list. The function will find all instances of the old item and replace it with the new item.

In [68]:
(define substitute
  (lambda (old new lyst)
In [69]:
(substitute 'old 'new '())
Out[69]:
()
In [70]:
(substitute 'old 'new '(old))
Out[70]:
(new)
In [71]:
(substitute 'old 'new '(old old a b c old))
Out[71]:
(new new a b c new)

5. Problem: substitute*

substitute* works just like substitute but will find all instances no matter how deeply hidden they are inside sublists of the given list.

In [98]:
(define substitute*
  (lambda (old new lyst)
In [99]:
(substitute* 'old 'new '((old)((((old apple bannan)) (a b c old d e))) old test ((word)) (old) old))
Out[99]:
((new) ((((new apple bannan)) (a b c new d e))) new test ((word)) (new) new)

6. Problem: infix->prefix

infix->prefix will convert expressions given in infix notation to prefix notation. It gives an error if you attempt to operate on an empty list.

In [78]:
(define infix->prefix
  (lambda (expr)
    (cond
     ((null? expr) (error 'infix->prefix "Cannot process an empty expression"))
In [79]:
(infix->prefix 1)
Out[79]:
1
In [80]:
(infix->prefix '(1 + 2))
Out[80]:
(+ 1 2)
In [81]:
(infix->prefix '((1 + 2) * (8 / 9)))
Out[81]:
(* (+ 1 2) (/ 8 9))
In [82]:
(infix->prefix '())

Traceback (most recent call last):
  File "stdin", line 1, col 1, in 'infix->prefix'
  File "stdin", line 4, col 20, in 'error'
  File "stdin", line 4, col 20
RunTimeError: Error in 'infix->prefix': Cannot process an empty expression

7. Problem: eval-infix

eval-infix will evaluate infix expressions. It should handle +, *, /, and -. It should give an error otherwise.

In [92]:
(define eval-infix
  (lambda (e)
In [95]:
(eval-infix 42)
Out[95]:
42
In [93]:
(eval-infix '(1 + 1))
Out[93]:
2
In [96]:
(eval-infix '(2 * (3 + 7)))
Out[96]:
20
In [97]:
(eval-infix '((8 / 9) * (3 + 7)))
Out[97]:
80/9
In [94]:
(eval-infix '(1 ^ 1))

Traceback (most recent call last):
  File "stdin", line 1, col 1, in 'eval-infix'
  File "stdin", line 10, col 15, in 'error'
  File "stdin", line 10, col 15
RunTimeError: Error in 'eval-infix': Unknown operator ^