Comp301 - Project 3 - Solved

In this project, you will implement the most common data structures such as array, stack and queue to EREF. Please, read each part carefully, and pay attention to Assumptions and Constraints section.

Part A. In this part, you will add arrays to EREF. Introduce new operators newarray, updatearray, and read-array with the following definitions: (20 pts)

newarray: Int * Int -> ArrVal update-array: ArrVal * Int * ExpVal -> Unspecified read-array: ArrVal * Int -> ExpVal

This leads us to define value types of EREF as:

ArrVal = (Ref(ExpVal))*

ExpVal = Int + Bool + Proc + ArrVal + Ref(ExpVal) DenVal = ExpVal

Operators of array is defined as follows;

newarray(length, value) initializes an array of size length with the value value. update-array(arr, index, value) updates the value of the array arr at index index by value value. read-array(arr, index) returns the element of the array arr at index index.

Part B. In this part, you will implement Stack with using arrays that you implemented in Part A. (35 pts)

Stack is a data structure that serves as a collection of elements, where the elements are reached in a LIFO (Last In First Out) manner. In other words, when an element is added to the stack, it is added on top of all elements, and when an element is popped from the stack, the topmost element in this data structure will be extracted from the stack. You will implement the following operators of Stack with the given grammar:

newstack() returns an empty stack. stack-push(stk, val) adds the element val to the stack stk.

stack-pop(stk) removes the topmost element of the stack stk and returns its value. stack-size(stk) returns the number of elements in the stack stk. stack-top(stk) returns the value of the topmost element in the stack stk without removal. empty-stack?(stk) returns true if there is no element inside the stack stk and false otherwise. print-stack(stk) prints the elements in the stack stk.

Part C. In this part, you will implement Queue with using arrays that you implemented in Part A. (35 pts)

Queue is a data structure that serves as a collection of elements, where the elements are reached in a FIFO (First In First Out) manner. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. When an element is popped from the queue, the first element that is pushed in this data structure will be extracted from the queue.

You will implement the following operators of Queue with given definitions:

newqueue() returns an empty queue. queue-push(queue, val) adds the element val to the stack queue queue-pop(queue) removes the first element of the queue queue and returns its value. queue-size(queue) returns the number of elements in the queue queue

queue-top(queue) returns the value of the first element in the stack queue without removal empty-queue?(queue) returns true if there is no element inside the queue queue and false otherwise.

print-queue(queue) prints the elements in the queue queue

Report. Your report should include the following: (10 pts)

(1)    Workload distribution of group members.

(2)    Parts that work properly, and that do not work properly.

(3)    Your approach to implementations, how does your stack/queue work?

Include your report as PDF format in your submission folder.

Assumptions and Constraints. Read the following assumptions and constraints carefully. You may not consider the edge cases related to the assumptions.

(1)    Stack and Queue do not have to be new defined data types, you can utilize the array implementation from Part A.

(2)    For stack and queue, you may assume that values are integers.

(3)    For stack and queue, values will be in range [1, 10000].

(4)    The number of push operations will not exceed 1000 for a single stack/queue.

(5)    It is guaranteed that the correct type of parameters will be passed to the operators. For example, in stack-pop(stk), stk always be a stack.

(6)    If stack/queue is empty, pop operation must return -1.

(7)    You CANNOT define global variables to keep track of the size or top element of a stack/queue. The reason is we may create multiple stacks/queues and each of them may have different sizes and top elements.

Sample Programs. Here are some sample programs for you.

let x = newstack() in begin stack-push(x, 20); stack-push(x, 30);

stack-push(x, 40); stack-pop(x); print-stack(x) end

;;; 20 30

let x = newstack() in begin stack-push(x, 20); stack-push(x, 30);

stack-push(x, 40); stack-pop(x); empty-stack?(x) end

;;; (bool-val #f)

let x = newqueue() in begin queue-push(x, 20); queue-push(x, 30);

queue-push(x, 40); queue-pop(x); print-queue(x) end

;;; 30 40

let x = newqueue() in begin queue-push(x, 20); queue-push(x, 30);

queue-push(x, 40); queue-pop(x); queue-size(x) end

;;; (num-val 2)