# 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 :
(define remove-first
(lambda (item lyst)

In :
(remove-first 'a '())

Out:
()
In :
(remove-first 'a '(a))

Out:
()
In :
(remove-first 'a '(a a a))

Out:
(a a)
In :
(remove-first 'a '(b c a))

Out:
(b c)
In :
(remove-first 'a '(a a b c a))

Out:
(a b c a)
In :
(remove-first 'a '(b c d))

Out:
(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 :
(define remove-all
(lambda (item lyst)

In :
(remove-all 'a '())

Out:
()
In :
(remove-all 'a '(a))

Out:
()
In :
(remove-all 'a '(a a a))

Out:
()
In :
(remove-all 'a '(b a c a d a))

Out:
(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 :
(define remove-nth
(lambda (n item lyst)

In :
(remove-nth 1 'a '(a b a c a d))

Out:
(b a c a d)
In :
(remove-nth 2 'a '(a b a c a d))

Out:
(a b c a d)
In :
(remove-nth 3 'a '(a b a c a d))

Out:
(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 :
(define substitute
(lambda (old new lyst)

In :
(substitute 'old 'new '())

Out:
()
In :
(substitute 'old 'new '(old))

Out:
(new)
In :
(substitute 'old 'new '(old old a b c old))

Out:
(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 :
(define substitute*
(lambda (old new lyst)

In :
(substitute* 'old 'new '((old)((((old apple bannan)) (a b c old d e))) old test ((word)) (old) old))

Out:
((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 :
(define infix->prefix
(lambda (expr)
(cond
((null? expr) (error 'infix->prefix "Cannot process an empty expression"))

In :
(infix->prefix 1)

Out:
1
In :
(infix->prefix '(1 + 2))

Out:
(+ 1 2)
In :
(infix->prefix '((1 + 2) * (8 / 9)))

Out:
(* (+ 1 2) (/ 8 9))
In :
(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 :
(define eval-infix
(lambda (e)

In :
(eval-infix 42)

Out:
42
In :
(eval-infix '(1 + 1))

Out:
2
In :
(eval-infix '(2 * (3 + 7)))

Out:
20
In :
(eval-infix '((8 / 9) * (3 + 7)))

Out:
80/9
In :
(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 ^