CS2123 Data Structures Summer 2017 Assignment 2: Stacks and Recursive Programs D
ID: 3852109 • Letter: C
Question
CS2123 Data Structures Summer 2017 Assignment 2: Stacks and Recursive Programs Due 6/26/17 by 11:59pm 1. Stacks in C (15 points) Implement a stack to store and remove strings that will be read from a file. The data file contains a series of strings, one per line. Each string will contain 255 or fewer characters Whenever you read the string "pop", this is a signal to pop your stack. Any other string should be pushed onto your stack The format of the data file is pop pop To create the initial stack, use malloc to allocate enough space to store 10 strings. Keep track of how many elements are in your stack. When you stack reaches capacity, your push method needs to allocate more space to your stack before pushing the next element add space for another 10 strings). You can use realloc, or something else like malloc/copy/swap You do not ever need to shrink your stacks capacity You are required to implement the following stack functions: push, pop, empty, and full. create returns a new empty stack push takes a string parameter which is the value it pushes onto the stack. It may also need to call realloc to expand the size of the stack before complet ing the push pop returns the string that was removed from the stack empty returns TRUE if the stack has no elements, otherwise FALSE. full returns TRUE if the stack does not have any room left, otherwise FALSE. Your program must print the assignment 2 and your name. Additionally, each time you read "pop" (i.e., each time you receive a signal to pop the stack) you should print the # of elements in the stack after popping and also print the string that is popped off the stack You should also print a message every time your stack grows. For example, the program might print the following Assignment 2 Problem 1 by # elements after popping: 2 # elements after popping: 1 # elernents after popping: 0 Stack capacity has groum from 10 elements to 20 elements string popped: Be string popped: su string popped: to re Continued on the backExplanation / Answer
Stacks.c
---------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT_ARR_SIZE 10
#define MAX_LEN 255
typedef struct stack {
int currsize;
int maxsize;
char **strings;
} stack;
stack *create();
void push(stack *stk, const char *str);
char *pop(stack *stk);
void freestack(stack *stk);
int empty(stack *stk);
int full(stack *stk);
int main(int argc, char *argv[]) {
/* Check for correct number of command-line arguments */
if (argc != 2) {
fprintf(stderr, "Usage: %s FILENAME ", argv[0]);
exit(-1);
}
/* Print header */
printf("Assignment 2 Problem 1 ");
printf("--------------------------------------- ");
/* Open filename provided, check for error */
FILE *infile = fopen(argv[1], "r");
if (infile == NULL) {
fprintf(stderr, "Error opening %s ", argv[1]);
exit(-1);
}
/* Create stack and temp char buffer used for reading strings from file */
stack *stk = create();
char temp[MAX_LEN];
while (fscanf(infile, "%254s", temp) != EOF) {
/* If string from file is pop, pop stack then print size and string */
if (strncmp(temp, "pop", 3) == 0) {
char *popped = pop(stk);
/* Make sure popped is not NULL */
if (popped != NULL) {
printf("# elements after popping: %d ", stk->currsize);
printf("string popped: %s ", popped);
free(popped);
} else {
printf("Cannot pop an empty stack! ");
}
/* Any other string from file will be pushed onto stack */
} else {
push(stk, temp);
}
}
/* Close file and free everything allocated */
fclose(infile);
freestack(stk);
return 0;
}
stack *create() {
stack *newstack = (stack *)malloc(sizeof(stack));
/* Initialize array of strings with all pointers to NULL */
newstack->strings = (char **)malloc(sizeof(char *) * INIT_ARR_SIZE);
for (int i = 0; i < INIT_ARR_SIZE; i++)
newstack->strings[i] = NULL;
/* Initialize current size to 0 and max capacity to INIT_ARR_SIZE */
newstack->currsize = 0;
newstack->maxsize = INIT_ARR_SIZE;
return newstack;
}
void push(stack *stk, const char *str) {
/* Increment current size and check to make sure there is space, if not realloc */
stk->currsize++;
if (full(stk)) {
stk->maxsize *= 2;
stk->strings = (char **)realloc(stk->strings, sizeof(char *) * stk->maxsize);
printf("Stack capacity has grown from %d elements to %d elements ", stk->maxsize / 2, stk->maxsize);
}
/* Allocate memory equal to string length + 1 for null-byte */
int len = strlen(str);
stk->strings[stk->currsize - 1] = (char *)calloc(len + 1, sizeof(char));
/* Copy string into string array */
strncpy(stk->strings[stk->currsize - 1], str, len);
}
char *pop(stack *stk) {
/* Check if stack is empty */
if (empty(stk))
return NULL;
/* Decrement current size */
stk->currsize--;
/* Allocate new string equal to top element length + 1 */
int len = strlen(stk->strings[stk->currsize]);
char *popped = (char *)calloc(len + 1, sizeof(char));
/* Copy top element string into newly allocated string */
strncpy(popped, stk->strings[stk->currsize], len);
/* Free the previously allocated top element */
free(stk->strings[stk->currsize]);
return popped;
}
void freestack(stack *stk) {
/* Free any strings that have not been freed from pop */
for (int i = 0; i < stk->currsize; i++)
free(stk->strings[i]);
/* Free the strings array and then the stack itself */
free(stk->strings);
free(stk);
}
int empty(stack *stk) {
/* Empty when current size is 0 */
return (stk->currsize == 0);
}
int full(stack *stk) {
/* Full when current size is greater than or equal to max capacity */
return (stk->currsize >= stk->maxsize);
}