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 ^