This assignment is comprised of 3 parts: All files needed are located at the end
ID: 3855720 • Letter: T
Question
This assignment is comprised of 3 parts:
All files needed are located at the end of the directions.
Part 1: Implementation of Dynamic Array, Stack, and Bag
First, complete the Worksheets 14 (Dynamic Array), 15 (Dynamic Array Amortized Execution Time Analysis), 16 (Dynamic Array Stack), and 21 (Dynamic Array Bag). These worksheets will get you started on the implementations, but you will NOT turn them in. Do Not Worry about these, they are completed.
Next, complete the dynamic array and the dynamic array-based implementation of a stack and a bag in dynamicArray.c. The comments for each function will help you understand what each function should do.
We have provided the header file for this assignment, DO NOT change the provided header file (dynArray.h).
You can test your implementation by using the code in testDynArray.c. This file contains several test cases for the functions in dynamicArray.c. Try to get all the test cases to pass. You should also write more test cases on your own, but do not submit testDynArray.c.
Part 2: Amortized Analysis of the Dynamic Array (written)
Consider the push() operation for a Dynamic Array Stack. In the best case, the operation is O(1). This corresponds to the case where there was room in the space we have already allocated for the array. However, in the worst case, this operation slows down to O(n). This corresponds to the case where the allocated space was full and we must copy each element of the array into a new (larger) array. This problem is designed to discover runtime bounds on the average case when various array expansion strategies are used, but first some information on how to perform an amortized analysis is necessary.
1. Each time an item is added to the array without requiring reallocation, count 1 unit of cost. This cost will cover the assignment which actually puts the item in the array.
2. Each time an item is added and requires reallocation, count X + 1 units of cost, where X is the number of items currently in the array. This cost will cover the X assignments which are necessary to copy the contents of the full array into a new (larger) array, and the additional assignment to put the item which did not fit originally.
To make this more concrete, if the array has 8 spaces and is holding 5 items, adding the sixth will cost 1. However, if the array has 8 spaces and is holding 8 items, adding the ninth will cost 9 (8 to move the existing items + 1 to assign the ninth item once space is available).
When we can bound an average cost of an operation in this fashion, but not bound the worst case execution time, we call it amortized constant execution time, or average execution time. Amortized constant execution time is often written as O(1)+, the plus sign indicating it is not a guaranteed execution time bound.
In a file called amortizedAnalysis.txt, please provide answers to the following questions:
1. How many cost units are spent in the entire process of performing 32 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for a push?
2. How many cost units are spent in the entire process of performing 32 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for a push?
Part 3: Application of the Stack -
Note - For this exercise you need to first make the following change in dynArray.h: Change #define TYPE int to #define TYPE char
As discussed in the lecture notes, stacks are a very commonly used abstract data type. Applications of stacks include implementation of reverse Polish notation expression evaluation and undo buffers. Stacks can also be used to check whether an expression has balanced paretheses, braces, and brackets (,{,[ or not. For example, expressions with balanced parentheses are (x + y), (x + (y + z)) and with unbalanced are (x+y, (x + (y+ z).
For this part of the assignment, you are to write a function that solves this problem using a stack (no counter integers or string functions are allowed). If you use a counter or string operation of any kind, you will not receive credit for completing this part of the assignment.
The file stackapp.c contains two functions -
char nextChar(char* s) – returns the next character or ‘’ if at the end of the string. int isBalanced(char* s) – returns 1 if the string is balanced and 0 if it is not balanced.
You have to implement int isBalanced(char* s) – which should read through the string using ‘nextChar’ and use a stack to do the test. It should return either 1(True) or 0(False).
dynArray.h
/* dynamicArray_a1.h : Dynamic Array implementation. */
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
#ifndef __TYPE
#define __TYPE
# define TYPE char
# define TYPE_SIZE sizeof(int)
# endif
# ifndef LT
# define LT(A, B) ((A) < (B))
# endif
# ifndef EQ
# define EQ(A, B) ((A) == (B))
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
void initDynArr(DynArr *v, int capacity);
DynArr *newDynArr(int cap);
void freeDynArr(DynArr *v);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
/* Note addDynArr is already declared above*/
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
dynamicArray.c
/* dynamicArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
struct DynArr
{
TYPE *data; /* pointer to the data array */
int size; /* Number of elements in the array */
int capacity; /* capacity ofthe array */
};
/* ************************************************************************
Dynamic Array Functions
************************************************************************ */
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap */
v->data = 0; /* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
/* FIXME: You will write this function */
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Get an element from the dynamic array from a specified position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
/* FIXME: You will write this function */
/* FIXME: you must change this return value */
return 1;
}
/* Put an item into the dynamic array at the specified location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
/* FIXME: You will write this function */
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
/* FIXME: You will write this function */
}
/* Remove the element at the specified location from the array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
/* FIXME: You will write this function */
}
/* ************************************************************************
Stack Interface Functions
************************************************************************ */
/* Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.
param: v pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Push an element onto the top of the stack
param: v pointer to the dynamic array
param: val the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached capacity, capacity is doubled
val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Returns the element at the top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Removes the element on top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been removed
*/
void popDynArr(DynArr *v)
{
/* FIXME: You will write this function */
}
/* ************************************************************************
Bag Interface Functions
************************************************************************ */
/* Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0
param: v pointer to the dynamic array
param: val the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value */
return 1;
}
/* Removes the first occurrence of the specified value from the collection
if it occurs
param: v pointer to the dynamic array
param: val the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by 1
*/
void removeDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
testDynArray.c
/* testDynArray.c
* This file is used for testing the dynamicArray.c file.
* This test suite is by no means complete or thorough.
* More testing is needed on your own.
*/
#include <stdio.h>
#include <stdlib.h>
#include "dynArray.h"
void assertTrue(int predicate, char *message)
{
printf("%s: ", message);
if (predicate)
printf("PASSED ");
else
printf("FAILED ");
}
// this main function contains some
int main(int argc, char* argv[]){
DynArr *dyn;
dyn = newDynArr(2);
int i;
printf(" Testing addDynArr... ");
addDynArr(dyn, 3);
addDynArr(dyn, 4);
addDynArr(dyn, 10);
addDynArr(dyn, 5);
addDynArr(dyn, 6);
printf("The array's content: [3,4,10,5,6] ");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element == 3");
assertTrue(EQ(getDynArr(dyn, 1), 4), "Test 2nd element == 4");
assertTrue(EQ(getDynArr(dyn, 2), 10), "Test 3rd element == 10");
assertTrue(EQ(getDynArr(dyn, 3), 5), "Test 4th element == 5");
assertTrue(EQ(getDynArr(dyn, 4), 6), "Test 5th element == 6");
assertTrue(sizeDynArr(dyn) == 5, "Test size = 5");
printf(" Testing putDynArr... Calling putDynArr(dyn, 2, 7) ");
putDynArr(dyn, 2, 7);
printf("The array's content: [3,4,7,5,6] ");
assertTrue(EQ(getDynArr(dyn, 2), 7), "Test 3rd element == 7");
assertTrue(sizeDynArr(dyn) == 5, "Test size = 5");
printf(" Testing swapDynArr... Calling swapDynArr(dyn, 2, 4) ");
swapDynArr(dyn, 2, 4);
printf("The array's content: [3,4,6,5,7] ");
assertTrue(EQ(getDynArr(dyn, 2), 6), "Test 3rd element == 6");
assertTrue(EQ(getDynArr(dyn, 4), 7), "Test 5th element == 7");
printf(" Testing removeAtDynArr... Calling removeAtDynArr(dyn, 1) ");
removeAtDynArr(dyn, 1);
printf("The array's content: [3,6,5,7] ");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element == 3");
assertTrue(EQ(getDynArr(dyn, 3), 7), "Test 4th element == 7");
assertTrue(sizeDynArr(dyn) == 4, "Test size = 4");
printf(" Testing stack interface... ");
printf("The stack's content: [3,6,5,7] <- top ");
assertTrue(!isEmptyDynArr(dyn), "Testing isEmptyDynArr");
assertTrue(EQ(topDynArr(dyn), 7), "Test topDynArr == 7");
popDynArr(dyn);
printf("Poping... The stack's content: [3,6,5] <- top ");
assertTrue(EQ(topDynArr(dyn), 5), "Test topDynArr == 5");
pushDynArr(dyn, 9);
printf("Pushing 9... The stack's content: [3,6,5,9] <- top ");
assertTrue(EQ(topDynArr(dyn), 9), "Test topDynArr == 9");
printf(" Testing bag interface... ");
printf("The bag's content: [3,6,5,9] ");
assertTrue(containsDynArr(dyn, 3), "Test containing 3");
assertTrue(containsDynArr(dyn, 6), "Test containing 6");
assertTrue(containsDynArr(dyn, 5), "Test containing 5");
assertTrue(containsDynArr(dyn, 9), "Test containing 9");
assertTrue(!containsDynArr(dyn, 7), "Test not containing 7");
removeDynArr(dyn, 3);
printf("Removing 3... The stack's content: [6,5,9] ");
assertTrue(!containsDynArr(dyn, 3), "Test not containing 3");
return 0;
}
stackapp.c
/* stack.c: Stack application. */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dynArray.h"
/* ***************************************************************
Using stack to check for unbalanced parentheses.
***************************************************************** */
/* Returns the next character of the string, once reaches end return '0' (zero)
param: s pointer to a string
pre: s is not null
*/
char nextChar(char* s)
{
static int i = -1;
char c;
++i;
c = *(s+i);
if ( c == '' )
return '';
else
return c;
}
/* Checks whether the (), {}, and [] are balanced or not
param: s pointer to a string
pre: s is not null
post:
*/
int isBalanced(char* s)
{
/* FIXME: You will write this function */
return 0;
}
int main(int argc, char* argv[]){
char* s=argv[1];
int res;
printf("Assignment 2 ");
res = isBalanced(s);
if (res)
printf("The string %s is balanced ",s);
else
printf("The string %s is not balanced ",s);
return 0;
}
Explanation / Answer
Below is given the code for Part 1 and Part 3. Please note that for Part 3, we will be modifying dynArray.h , to set TYPE to char and TYPE_SIZE to sizeof(char) instead of using int. So you will use 2 versions of dynArray.h. Keep a copy of it separately in a folder with int and another with char in a different folder like shown below
1. Folder Part1 containing - dynArray.h (int version), dynArray.c and testDynArray.c .
compile gcc dynArray.c testDynArray.c
2. Folder Part2 containing - dynArray.h (char version), dynArray.c and stackapp.c
compile gcc dynArray.c stackapp.c
I am giving the modified files separately for each part.
- dynArray.c has been implemented and is common for both parts. There is no change in it for both parts, so use the same copy for both tests
- stackapp.c to be used for part2 has been implemented
- take testDynArray.c from your question itself. It is not modified.
In case of any issues, please post a comment. If happy with the answer , please rate it. Thank you.
common file dynArray.c
/* dynamicArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
struct DynArr
{
TYPE *data; /* pointer to the data array */
int size; /* Number of elements in the array */
int capacity; /* capacity ofthe array */
};
/* ************************************************************************
Dynamic Array Functions
************************************************************************ */
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap */
v->data = 0; /* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
TYPE *temp = malloc(TYPE_SIZE * newCap);
int i;
/* FIXME: You will write this function */
assert(v != 0);
//copy the values into new array
for(i = 0; i < sizeDynArr(v); i++)
temp[i] = v->data[i];
free(v->data); // free old memory
v->data = temp; //update the array to point to new allocated memory
v->capacity = newCap; //update capacity
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
assert(v != 0);
if(sizeDynArr(v) == v->capacity) //if no more space, increase capacity to double of its value
{
_dynArrSetCapacity(v, 2 * v->capacity);
}
v->data[v->size] = val;
v->size++;
}
/* Get an element from the dynamic array from a specified position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
/* FIXME: You will write this function */
/* FIXME: you must change this return value */
assert(v != 0 && !isEmptyDynArr(v));
assert(pos >= 0 && pos < sizeDynArr(v));
return v->data[pos];
}
/* Put an item into the dynamic array at the specified location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
assert(pos >= 0 && pos < sizeDynArr(v));
v->data[pos] = val; //put the val in pos overwriting old value
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
assert(i>=0 && j >= 0 && i < sizeDynArr(v) && j < sizeDynArr(v));
TYPE temp = v->data[i];
v->data[i] = v->data[j];
v->data[j] = temp;
}
/* Remove the element at the specified location from the array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
int i;
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
assert(idx >= 0 && idx < sizeDynArr(v));
//more all elements back by 1 position starting from idx
for(i = idx; i < sizeDynArr(v) - 1; i++)
v->data[i] = v->data[i+1];
//reduce the size
v->size--;
}
/* ************************************************************************
Stack Interface Functions
************************************************************************ */
/* Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.
param: v pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
/* FIXME: You will write this function */
assert(v != 0);
/* FIXME: You will change this return value*/
if(sizeDynArr(v) == 0)
return 1;
else
return 0;
}
/* Push an element onto the top of the stack
param: v pointer to the dynamic array
param: val the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached capacity, capacity is doubled
val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
assert(v != 0);
addDynArr(v, val);
}
/* Returns the element at the top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
/* FIXME: You will change this return value*/
return v->data[sizeDynArr(v) - 1];
}
/* Removes the element on top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been removed
*/
void popDynArr(DynArr *v)
{
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
removeAtDynArr(v, sizeDynArr(v) - 1);
}
/* ************************************************************************
Bag Interface Functions
************************************************************************ */
/* Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0
param: v pointer to the dynamic array
param: val the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
int i;
/* FIXME: You will write this function */
assert(v != 0 && !isEmptyDynArr(v));
/* FIXME: You will change this return value */
for( i = 0; i < sizeDynArr(v); i++)
{
if(EQ(val, v->data[i])) //found the val
return 1;
}
return 0;//did not find
}
/* Removes the first occurrence of the specified value from the collection
if it occurs
param: v pointer to the dynamic array
param: val the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by 1
*/
void removeDynArr(DynArr *v, TYPE val)
{
int i;
assert(v != 0 && !isEmptyDynArr(v));
/* FIXME: You will write this function */
for(i = 0; i < sizeDynArr(v); i++)
{
if(EQ(val, v->data[i]))
{
removeAtDynArr(v, i); // remove the element at index i
break;
}
}
}
PART 1
dynArray.h
/* dynamicArray_a1.h : Dynamic Array implementation. */
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
#ifndef __TYPE
#define __TYPE
# define TYPE int
# define TYPE_SIZE sizeof(int)
# endif
# ifndef LT
# define LT(A, B) ((A) < (B))
# endif
# ifndef EQ
# define EQ(A, B) ((A) == (B))
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
void initDynArr(DynArr *v, int capacity);
DynArr *newDynArr(int cap);
void freeDynArr(DynArr *v);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
/* Note addDynArr is already declared above*/
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
Use dynArray.c given by me above and testDynArray.c from question.
output
Testing addDynArr...
The array's content: [3,4,10,5,6]
Test 1st element == 3: PASSED
Test 2nd element == 4: PASSED
Test 3rd element == 10: PASSED
Test 4th element == 5: PASSED
Test 5th element == 6: PASSED
Test size = 5: PASSED
Testing putDynArr...
Calling putDynArr(dyn, 2, 7)
The array's content: [3,4,7,5,6]
Test 3rd element == 7: PASSED
Test size = 5: PASSED
Testing swapDynArr...
Calling swapDynArr(dyn, 2, 4)
The array's content: [3,4,6,5,7]
Test 3rd element == 6: PASSED
Test 5th element == 7: PASSED
Testing removeAtDynArr...
Calling removeAtDynArr(dyn, 1)
The array's content: [3,6,5,7]
Test 1st element == 3: PASSED
Test 4th element == 7: PASSED
Test size = 4: PASSED
Testing stack interface...
The stack's content: [3,6,5,7] <- top
Testing isEmptyDynArr: PASSED
Test topDynArr == 7: PASSED
Poping...
The stack's content: [3,6,5] <- top
Test topDynArr == 5: PASSED
Pushing 9...
The stack's content: [3,6,5,9] <- top
Test topDynArr == 9: PASSED
Testing bag interface...
The bag's content: [3,6,5,9]
Test containing 3: PASSED
Test containing 6: PASSED
Test containing 5: PASSED
Test containing 9: PASSED
Test not containing 7: PASSED
Removing 3...
The stack's content: [6,5,9]
Test not containing 3: PASSED
PART 2:
Note: You have to pass a command line argument to the program ... a string of parenthesis to test. Otherwise it will crash.
example: ./a.out []{}{
dynArray.h
/* dynamicArray_a1.h : Dynamic Array implementation. */
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
#ifndef __TYPE
#define __TYPE
# define TYPE char
# define TYPE_SIZE sizeof(char)
# endif
# ifndef LT
# define LT(A, B) ((A) < (B))
# endif
# ifndef EQ
# define EQ(A, B) ((A) == (B))
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
void initDynArr(DynArr *v, int capacity);
DynArr *newDynArr(int cap);
void freeDynArr(DynArr *v);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
/* Note addDynArr is already declared above*/
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
stackapp.c
/* stack.c: Stack application. */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dynArray.h"
/* ***************************************************************
Using stack to check for unbalanced parentheses.
***************************************************************** */
/* Returns the next character of the string, once reaches end return '0' (zero)
param: s pointer to a string
pre: s is not null
*/
char nextChar(char* s)
{
static int i = -1;
char c;
++i;
c = *(s+i);
if ( c == '' )
return '';
else
return c;
}
/* Checks whether the (), {}, and [] are balanced or not
param: s pointer to a string
pre: s is not null
post:
*/
int isBalanced(char* s)
{
DynArr *stack = newDynArr(10);
char ch, top ;
char to_match = ' ';
int balanced = 1;
/* FIXME: You will write this function */
while(balanced && (ch = nextChar(s)) != '' )
{
/*push any opening parenthesis*/
switch(ch)
{
case '(':
case '{':
case '[':
pushDynArr(stack, ch);
continue; //continue into the loop to get next char
case '}':
to_match = '{';
break;
case ']':
to_match = '[';
break;
case ')':
to_match = '(';
break;
default:
continue;
}
/*if the top of stack is not matching opening parenthesis*/
if(isEmptyDynArr(stack) || topDynArr(stack) != to_match)
balanced = 0;
else
popDynArr(stack);
}
/*stack should be empty when finished*/
if(isEmptyDynArr(stack))
return 1;
else
return 0;
}
int main(int argc, char* argv[]){
char* s=argv[1];
int res;
printf("Assignment 2 ");
res = isBalanced(s);
if (res)
printf("The string %s is balanced ",s);
else
printf("The string %s is not balanced ",s);
return 0;
}
User the dynArray.c given by me above
output
Assignment 2
The string {[()]} is balanced
Assignment 2
The string ()( is not balanced
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.