C code programming practice:

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 allowed). If you use a counter or a string opertation of any kind, you will not recieve credit for completing this part of the assignment.

The file stackapp.c contains two functions -

char nextChar(char*s) - returns the next character or '\0' 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)

Grading Compile without warnings = 15 Implementation of the Dynamic Array, Stack, and Bag: void _dynArrSetCapacity(DynArr *v, int newCap) = 10 void addDynArr(DynArr *v, TYPE val) = 5 TYPE getDynArr(DynArr *v, int pos) = 5 void putDynArr(DynArr *v, int pos, TYPE val) = 5 void swapDynArr(DynArr *v, int i, int j) = 2 void removeAtDynArr(DynArr *v, int idx) = 5 int isEmptyDynArr(DynArr *v) = 2 void pushDynArr(DynArr *v, TYPE val) = 2 TYPE topDynArr(DynArr *v)= 2 void popDynArr(DynArr *v)= 2 int containsDynArr(DynArr *v, TYPE val) = 5 void removeDynArr(DynArr *v, TYPE val) = 5 Amortized Analysis = 20 Stack application int isBalanced(char*s)= 15

Below is code given to help with the program. The areas in bold are what needs to be added per guidelines above.

/* 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: Dynamic Array implementation. */ #include #include #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 */ }

/* stack.c: Stack application. */ #include #include #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 == '\0' ) return '\0'; 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; }

/* 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 #include #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");

//Add more functions here to test. return 0; }