[SOLVED] algorithm Scheme statistic Practice with SCHEME objects

Practice with SCHEME objects
1. Encapsulationprotecting object state data behind an abstraction barrier.
Define a SCHEME object, named makerat, which creates an object representing a rational number. Recall that when we introduced pairs, we discussed a representation of rationals using a SCHEME pair. Here, your rational numbers will be represented with objects. Your rational object should expose the following capa bilities for a rational number: get numerator, get denominator, get reciprocal, add, subtract, and multiply. Thus, your object should expose the following methods in its dispatcher:
define makerat a b

lambda method
cond eq? method numer getnumer
eq? method denom getdenom
eq? method reciprocal reciprocal eq? method add add
eq? method sub sub
eq? method mult mult
Note, your rational number object should represent rationals in reduced form. You may find SCHEME builtin function gcd a b, which computes the greatest common divisor of its two arguments a and b, useful.
2. Define a SCHEME objectcall it basicsetthat maintains an initially empty set of numbers. Your object should have methods that correspond to
empty, which should return t if the set is empty, and f otherwise;insert, which should insert a new element into the set; and
delete, which should delete a particular element from the set; andelement?, which should determine if a given element is in the set.
Implement the set as a standard SCHEME list, and return a dispatcher that provides access to your methods, as we have done in class, via a token.
Thus, your object should behave as follows:
define newset basicsetnewset empty
t
newset insert 2
newset element? 2 t
newset delete 2
newset empty
t
3. Define a SCHEME objectcall it statsetthat maintains an initially empty set of numbers along with several statistics pertaining to the set. Your object should have methods that correspond to
1

empty, which should return t if the set is empty, and f otherwise;insert, which should insert a new element into the set;
element?, which should determine if a given element is in the set;
largest, which should return the largest element in the set;
smallest, which should return the smallest element in the set;
size, which should return the size of the set; and
average, which should return the average of the elements in the set.
Note that your set does not need to implement delete. Implement the set as a standard SCHEME list, and return a dispatcher that provides access to your methods, as we have done in class, via a token.
Important amplification. Your statset methods that implement largest, smallest, size, and average, should use only a constant amount of computation to determine their return value: specifically, the amount of time they take to return should not depend on the size of the set. Thus you cannot scan the list to determine its length, or the maximum element of the list.
How is this possible? One strategy is to set up some private variables in your object called, e.g. currentmax, currentmin, currentlength, etc. These variables should maintain, at all times, the current values of these quantities. When a new number is inserted, you will have to update your list that maintains the set and, in addition, update each of these statistics appropriately.
I think that the easiest way to maintain the current average is to actually maintain the current sum of all the elements in the set, andwhen the user asks for the averagereturn the sum divided by the current size.
Incidentally, why didnt we ask you to implement the delete operation?
4. Using the conventional set notation 1, 2, 2 and 1, 2 denote the same set which contains the numbers 1 and 2 and no others: specifically, as far as a set is concerned, an element either appears or it does notthere is no notion of an object appearing more than once.
A multiset is like a set in which elements can appear more than once. People often use the same set style notation for multisets: e.g., 1, 2, 2 denotes the multiset in which 1 appears once and 2 appears twice. Of course, as multisets 1, 2, 2 and 1, 2 are different.
Notice that to maintain a multiset of numbers, say, one needs to keep track of how many times each number appears in the set which could be zero.
Consider the representation of a multiset as a sorted list of pairs, where the first part of each pair represents an integer, and the second represents the number of times it appears a nonnegative integer. Thus the multiset 1,2,2,3,8,8 would be represented as the list 1 . 1 2 . 2 3 . 1 8 . 2. Note that numbers which do not appear at all in the multiset do not have a pair in the list.
Define a multiset object, which provides the methods:
empty, which should return t if the multiset is empty, and f otherwise;
insert, which should insert a new element into the set; of course, if the element already exists in the multiset, the number of times it appears in the set should increase;
multiplicity?, which should return the number of times a given element appears in the multiset it should return 0 if the element does not appear at all;
delete, which should delete one appearance of a particular element from a multiset; and
deleteall, which remove all appearances of an element in a multiset.

2

Stack Applications
5. In this problem you will define an object that implements the Stack abstract data type using a list to store the elements. When the object is created, it starts as an empty stack.
To implement the stack, the object will initially create an empty list, which it will store the elements of the stack. The stack contents are then maintained with the following convention: to represent the stack containing the elements e1 , e2 , . . . , en where e1 is the top of the stack and en is the bottom of the stack the list will contain the elements as shown in Figure 1, just below. Observe that the bottom element of the stack
e1 e2 e3 ek
Figure 1: Layout of a stack in a list.
is always at the end of the list. The top element of the stack can be accessed at the front of the list. To place a new element on the top of the stack, one needs only add it to the front of the list. Popping an element off the top of the stack is handled by returning the appropriate element take particular care to ensure you are returning the proper value when using destructive assignment and removing that element from the front of the list. Your object should expose methods for
empty? Returns a Boolean valuet or f depending on whether the stack is empty. push Pushes a new element onto the top of the stack.
pop Pops off the top element from the stack and returns it.
top Returns the value of the top of the stack without changing the contents of the stack.
Thus, your object should have the form:

define makestack
let
define empty?
define push x
define pop
define top
define dispatcher ;;the dispatcher
dispatcher
;; internal stack variables
;; stack methods
6. Evaluation of Postfix Expressions Given a list of operands and operators that represent a postfix ex pression, one can use a stack to evaluate the postfix expression. Its true! The algorithm to do this is as follows:
Algorithm 1 Evaluate Postfix Expression repeat
if operand at front of input string then push operand onto stack
else
pop stack to remove operands apply operator to operands push result onto stack
end if
until input string is empty
3

For example, to evaluate the expression 23 15we would:
a Push 23 onto the stack b Push 15 onto the stack cis an operator, so
i. Pop second operand note the operands are popped in reverse order ii. Pop first operand
iii. Apply the operator in this case, addition iv. Push the result back onto the stack
d Once the expression has been evaluated, the result is on the top of the stack.
Define a SCHEME function, named evalpostfix p, that will take a postfix expression stored in a list of integers representing operands and characters representing operators, evaluate that expression, and return the result.
Your function should support the operations of addition , subtraction , multiplication,
division,andexponentiation .
You may want to work incrementally by starting with a function that takes a character representing an operator and can pop two operands off of a stack, evaluate the operator and push the result back on the stack. Next you can add a function that evaluates a postfix expression by pushing operands onto the stack and evaluating operators when encountered. Note, you may want to use the number? function to determine whether an item in the list is an operand or an operator.
4