Question

Let’s build a dynamic string tokenizer!

Start with the existing template and work on the areas marked with TODO in the comments: Homework 8 Template.c

Note: If you turn the template back into me without adding any original work you will receive a 0.

By itself the template does nothing. You need to fill in the code to dynamically allocate an array of strings that are returned to the user.

Remember: A string is an array. A tokenizer goes through this array looking for special characters called delimiters . The result is a series of strings (tokens) that were taken out of the original array.

Example: Assume the input array is "1.1, 2.2, 3.3". The tokens would be "1.1" then "2.2" then "3.3".

Your objective: Finish up the template. We will use the old tokenizer system (strtok) to parse the string for comma characters ',' and space characters ' '.

1. In the BetterTokenizer() function you will dynamically allocate the array of strings.
   • The BetterTokenizer() function calls GetDelimiterCnt which returns an estimate on the number of tokens that will be found.
   • Use this estimate to dynamically allocate an array of strings and set the address of tokenizedArray that is within the BetterStrTok structure.
2. Once you know the number of tokens to expect, and have allocated for them (step 1), begin extracting each token.
   • The function GetNextToken() will handle the strtok calls for you.
     • It returns the next token string and sets the newStringLength variable to, you guessed it, the string's length.
   • Use the newStringLength variable to dynamically allocate the next string to be copied into strtok.tokenizedArray.
3. You want to dynamically allocate, and copy to, the arrayIndex of strtok.tokenizedArray[].
   • You may use strcpy (which is one line). Similarly memcpy.
   • Or use a for loop and assign the values if you are uncomfortable with the other options.
4. Fill out the PrintTokens function which goes through the array of tokens (strTok.tokenizedArray[]) and prints them to the screen using printf.
5. Fill out the CleanUpTokens function. You need to free any memory that was dynamically allocated.
   • Set up a loop to go through the array (strTok.tokenizedArray[]).
   • Free each string as you go.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <string.h>

#define MAX_INPUT_SIZE 10000

/* I used typedef to create a "string" data type. All strings are just

arrays of characters. I really did this to get rid of the scary

double pointers. */

typedef char* string;

/*This is the primary structure

It contains an array of strings (tokens) in tokenizedArray

And a count of how many tokens were found in tokenCnt.*/

typedef struct

{

string* tokenizedArray;

int tokenCnt;

} BetterStrTok;

//Declare all functions up front

string GetNextToken(string sStr, string delimiter, bool* pTokenizedOnce, int*

pLength);

BetterStrTok BetterTokenize(string sInput, string delimiter, int maxStringLength);

void PrintTokens(const BetterStrTok* pInput);

void CleanUpTokens(BetterStrTok* pInput);

int GetDelimiterCnt(string sStr, int maxStringLength, string delimiter);

void main()

{

/*Don't worry about this. The main function has an array of characters

(which is the same as the string data type). It uses gets() to read the

string in.*/

char sInput[MAX_INPUT_SIZE];

BetterStrTok tokens;

printf("Enter a series of numbers (or words) separated by commas: ");

gets(sInput);

/* BetterTokenize parses out the tokens in between the ',' and ' '

characters.

It will return a data structure that contains an array of strings

(dynamically allocated).

We are mimicing the Java string.Split() function. It breaks a string apart

into its

component parts.

*/

tokens = BetterTokenize(sInput, ", ", MAX_INPUT_SIZE);

/* Once the tokens have been made, we print each one and finally clean up the

dynamically allocated memory. Ultimately this is just a test.

We read in a string, break it apart, print out each piece, then clean up.

In the final homework we will do more with this.

*/

PrintTokens(&tokens);

CleanUpTokens(&tokens);

}

/*HOMEWORK 8:

Find the TODO comments and fill them in with the appropriate lines of code.

This function takes the original input string and fills out a BetterStrTok

structure.

This structure will contain a count of tokens and a dynamically allocated

array

of strings (tokens) that were extracted from the original string.

*/

BetterStrTok BetterTokenize(string sInput, string delimiter, int maxStringLength)

{

int i;

bool tokenizedOnce = false;

int newStringLength = 0;

int expectedCnt = 0;

BetterStrTok strTokStruct;

memset(&strTokStruct, 0, sizeof(BetterStrTok));

expectedCnt = GetDelimiterCnt(sInput, maxStringLength,delimiter);

/*TODO 1:

Use calloc or malloc to dynamically create the array of strings

This is an array of size expectedCnt times sizeof(string).

strTokStruct.tokenizedArray will be set to the pointer returned by

the calloc (or malloc) call.

Explanation: We are constructing an array of strings dynamically.

GetDelimiterCnt returned a total number of tokens. We cannot know

this at compile time, so an array of strings is dynamically

allocated.

*/

strTokStruct.tokenCnt = 0;

//This loop goes through every token that is expected

//The tokens are extracted, and then copied into dynamic memory.

for (i = 0; i < expectedCnt; i++)

{

/*Don't worry about this GetNextToken function, it returns the next

token string.

and sets newStringLength to the length of that string.

Explanation: This extracts the next token from the original string.

A token is every character between the space characters and ,

characters.

So given the string "1.1, 2.2, 3.3" the first token would be

1.1,

the next token would be 2.2, and the final token would be 3.3.

*/

string token = GetNextToken(sInput, delimiter, &tokenizedOnce,

&newStringLength);

if (newStringLength != 0)

{

int arrayIndex = strTokStruct.tokenCnt++;

/*TODO 2:

Use malloc or calloc to create a string of size

newStringLength times

the sizeof char. This pointer would be set to next index of

the array:

strTokStruct.tokenizedArray[arrayIndex]

Explanation: Remember that the string data type is an array

of chars.

We do not know, in advance (at compile-time), the length

of the token.

So a new array of chars is allocated. Keep in mind that

strTokStruct.tokenizedArray is an array of strings. That

is, it is an

array of array of chars.

*/

/*TODO 3:

Copy the string, token, to the newly allocated string which

is pointed at

by strTokStruct.tokenizedArray[arrayIndex] (assuming you

did the above step

correctly). You may use a for loop, the strcpy function or

the memcpy function.

Explanation: The token was found and is in the token

string, but that will be

overwritten. Before that occurs, we want to copy it to

the newly

allocated string (In the TODO 2 step).

*/

}

}

return strTokStruct;

}

/*HOMEWORK 8:

Assuming the above function works, this one will print every token in the

array.

*/

void PrintTokens(const BetterStrTok* pInput)

{

/* TODO 4:

Create a loop that goes from 0 to pInput->tokenCount.

Inside the loop print the token. If you want output like mine:

printf "%d: %s\n"

where the %d variable is the counter variable for the loop

and %s is the string in pInput's tokenizedArray array at

index i (or whatever you call your counter variable).

*/

}

/*HOMEWORK 8:

You always have to clean up dynamic memory, otherwise the system does not

know

that you are done with it. This function goes through the array of strings

and

releases each one. Then it releases the array itself.

*/

void CleanUpTokens(BetterStrTok* pInput)

{

/* TODO 5:

Create a loop that goes from 0 to pInput->tokenCount.

Inside the loop call the free function on pInput->tokenizedArray[]

at index i, or whatever you call your counter variable.

Explanation: pInput->tokenizedArray is an array of dynamically

allocated

strings. At the next line we will free the array itself, but first

you want

to go through the loop and free the dynamic memory one string at a

time.

Failure to do this create a memory leak.

Always remember, for every malloc or calloc you need a corresponding

free

somewhere in your code.

Similarly in C++ for every new call you would want a corresponding

delete,

but that isn't a part of this homework assignment.

*/

/*After freeing every string inside pInput->tokenizedArray the array itself

must be freed.*/

if(pInput->tokenizedArray != NULL)

free(pInput->tokenizedArray);

}

/*You don't have to worry about this function. It walks through the original string

And compares each character with the list of delimiters. It returns an accurate

Count of how many tokens exist in the original string.*/

int GetDelimiterCnt(string sStr, int maxStringLength, string delimiter)

{

int i;

int j;

int cnt = 0;

for (i = 0; i < maxStringLength || sStr[i] != '\0'; i++)

{

for (j = 0; j < strlen(delimiter); j++)

{

if (sStr[i] == delimiter[j])

cnt++;

}

}

//There will also be a concluding string

return cnt + 1;

}

/*You don't have to worry about this function. It uses the original strtok

functions to

extract the next token. strtok is not thread safe, so as good practice I actually

use strtok_s or strtok_r depending on if you are using OSX or Windows.

If you want to know what thread safe means, please feel free to ask.*/

string gContext;

string GetNextToken(string sStr, string delimiter, bool* pTokenizedOnce, int*

pLength)

{

string rv = NULL;

if (*pTokenizedOnce == false)

{

*pTokenizedOnce = true;

#ifdef _WIN32

rv = strtok_s(sStr, delimiter, &gContext);

#else

rv = strtok_r(sStr, delimiter, &gContext);

#endif

}

else

{

#ifdef _WIN32

rv = strtok_s(NULL, delimiter, &gContext);

#else

rv = strtok_r(NULL, delimiter, &gContext);

#endif

}

if (rv != NULL)

*pLength = strlen(rv)+1;

else

*pLength = 0;

return rv;

}

Annotations

Answer 1

Summary :

Pasted below the c code and output towards the end .

I have to modify the getTokenziecount logic as it was not behavior properly with original code .

Added few print statements to show the input and Number of tokens received .

Output shown for varied lenght of tokens .

######################## C Code ########################################

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_INPUT_SIZE 10000

/* I used typedef to create a "string" data type. All strings are just

arrays of characters. I really did this to get rid of the scary

double pointers. */

typedef char* string;

/*This is the primary structure

It contains an array of strings (tokens) in tokenizedArray

And a count of how many tokens were found in tokenCnt.*/

typedef struct
{
   string* tokenizedArray;
   int tokenCnt;
} BetterStrTok;

//Declare all functions up front

string GetNextToken(string sStr, string delimiter, bool* pTokenizedOnce, int* pLength);
BetterStrTok BetterTokenize(string sInput, string delimiter, int maxStringLength);
void PrintTokens(const BetterStrTok* pInput);
void CleanUpTokens(BetterStrTok* pInput);
int GetDelimiterCnt(string sStr, int maxStringLength, string delimiter);

void main()
{

/*Don't worry about this. The main function has an array of characters

(which is the same as the string data type). It uses gets() to read the

string in.*/

   char sInput[MAX_INPUT_SIZE];

   BetterStrTok tokens;

   printf("Enter a series of numbers (or words) separated by commas: ");

   gets(sInput);
   //strcpy(sInput ,"1.2, 1.3, 1.43456, 01.5, 13.456, 12.7, 1");
   printf(" Given Str : %s \n" , sInput);

/* BetterTokenize parses out the tokens in between the ',' and ' '
characters.
It will return a data structure that contains an array of strings
(dynamically allocated).
We are mimicing the Java string.Split() function. It breaks a string apart
into its
component parts.
*/

   tokens = BetterTokenize(sInput, ", ", MAX_INPUT_SIZE);

/* Once the tokens have been made, we print each one and finally clean up the
dynamically allocated memory. Ultimately this is just a test.
We read in a string, break it apart, print out each piece, then clean up.
In the final homework we will do more with this.
*/

   PrintTokens(&tokens);
   CleanUpTokens(&tokens);

}

/*HOMEWORK 8:

Find the TODO comments and fill them in with the appropriate lines of code.

This function takes the original input string and fills out a BetterStrTok

structure.

This structure will contain a count of tokens and a dynamically allocated

array

of strings (tokens) that were extracted from the original string.

*/
BetterStrTok BetterTokenize(string sInput, string delimiter, int maxStringLength)
{

   int i;
   bool tokenizedOnce = false;
   int newStringLength = 0;
   int expectedCnt = 0;
   BetterStrTok strTokStruct;
   memset(&strTokStruct, 0, sizeof(BetterStrTok));
   expectedCnt = GetDelimiterCnt(sInput, maxStringLength,delimiter);
  
   printf(" Num of Tokens % d \n " , expectedCnt );
/*TODO 1:
Use calloc or malloc to dynamically create the array of strings
This is an array of size expectedCnt times sizeof(string).
strTokStruct.tokenizedArray will be set to the pointer returned by
the calloc (or malloc) call.
Explanation: We are constructing an array of strings dynamically.
GetDelimiterCnt returned a total number of tokens. We cannot know
this at compile time, so an array of strings is dynamically
allocated.
*/
   strTokStruct.tokenizedArray = malloc( sizeof(char *) * (expectedCnt + 1));

   strTokStruct.tokenCnt = 0;

//This loop goes through every token that is expected
//The tokens are extracted, and then copied into dynamic memory.

   for (i = 0; i < expectedCnt; i++)
   {
/*Don't worry about this GetNextToken function, it returns the next
token string.
and sets newStringLength to the length of that string.
Explanation: This extracts the next token from the original string.
A token is every character between the space characters and ,
characters.
So given the string "1.1, 2.2, 3.3" the first token would be
1.1,
the next token would be 2.2, and the final token would be 3.3.
*/

       string token = GetNextToken(sInput, delimiter, &tokenizedOnce, &newStringLength);

       if (newStringLength != 0)
       {
           int arrayIndex = strTokStruct.tokenCnt++;
          
           //printf(" Got token %s , of length %zu , arrayIndx : %d , tokenCnt : %d \n" , token , strlen(token), arrayIndex, strTokStruct.tokenCnt);
          
/*TODO 2:
Use malloc or calloc to create a string of size
newStringLength times
the sizeof char. This pointer would be set to next index of
the array:
strTokStruct.tokenizedArray[arrayIndex]
Explanation: Remember that the string data type is an array
of chars.
We do not know, in advance (at compile-time), the length
of the token.
So a new array of chars is allocated. Keep in mind that
strTokStruct.tokenizedArray is an array of strings. That
is, it is an
array of array of chars.
*/
           strTokStruct.tokenizedArray[arrayIndex] = malloc(sizeof( char) * (strlen(token) + 1));
          
/*TODO 3:
Copy the string, token, to the newly allocated string which
is pointed at
by strTokStruct.tokenizedArray[arrayIndex] (assuming you
did the above step
correctly). You may use a for loop, the strcpy function or
the memcpy function.
Explanation: The token was found and is in the token
string, but that will be
overwritten. Before that occurs, we want to copy it to
the newly
allocated string (In the TODO 2 step).
*/
           strcpy(strTokStruct.tokenizedArray[arrayIndex], token);
       }

   }

   return strTokStruct;

}

/*HOMEWORK 8:

Assuming the above function works, this one will print every token in the

array.

*/

void PrintTokens(const BetterStrTok* pInput)

{

/* TODO 4:

Create a loop that goes from 0 to pInput->tokenCount.

Inside the loop print the token. If you want output like mine:

printf "%d: %s\n"

where the %d variable is the counter variable for the loop

and %s is the string in pInput's tokenizedArray array at

index i (or whatever you call your counter variable).

*/
   for(int i = 0 ; i < pInput->tokenCnt ; i++ ) {
       printf(" Token num : %d is -> %s \n" , i , pInput->tokenizedArray[i]);
   }

}

/*HOMEWORK 8:

You always have to clean up dynamic memory, otherwise the system does not

know

that you are done with it. This function goes through the array of strings

and

releases each one. Then it releases the array itself.

*/

void CleanUpTokens(BetterStrTok* pInput)

{

/* TODO 5:

Create a loop that goes from 0 to pInput->tokenCount.

Inside the loop call the free function on pInput->tokenizedArray[]

at index i, or whatever you call your counter variable.

Explanation: pInput->tokenizedArray is an array of dynamically

allocated

strings. At the next line we will free the array itself, but first

you want

to go through the loop and free the dynamic memory one string at a

time.

Failure to do this create a memory leak.

Always remember, for every malloc or calloc you need a corresponding

free

somewhere in your code.

Similarly in C++ for every new call you would want a corresponding

delete,

but that isn't a part of this homework assignment.

*/

/*After freeing every string inside pInput->tokenizedArray the array itself

must be freed.*/

if(pInput->tokenizedArray != NULL)
{
   for(int i = 0 ; i < pInput->tokenCnt ; i++ ) {
       free(pInput->tokenizedArray[i]);
   }

free(pInput->tokenizedArray);
}

}

/*You don't have to worry about this function. It walks through the original string

And compares each character with the list of delimiters. It returns an accurate

Count of how many tokens exist in the original string.*/

int GetDelimiterCnt(string sStr, int maxStringLength, string delimiter)
{
       int i;
       int j;
       int cnt = 0;
       int cnt0 = 0;

       for (i = 0; i < maxStringLength || sStr[i] != '\0'; i++)
       {
           if ( sStr[i] == delimiter[0] ) {
               cnt0 = 1;
               for (j = 1; j < strlen(delimiter); j++)
               {
                   if (sStr[i+j] == delimiter[j])
                       cnt0++;
               }
              
               if( cnt0 == strlen(delimiter) ) {
                   cnt = cnt + 1;
               }
              
           }
       }
       //There will also be a concluding string
       return cnt + 1;

}

/*You don't have to worry about this function. It uses the original strtok
functions to
extract the next token. strtok is not thread safe, so as good practice I actually
use strtok_s or strtok_r depending on if you are using OSX or Windows.
If you want to know what thread safe means, please feel free to ask.*/

string gContext;

string GetNextToken(string sStr, string delimiter, bool* pTokenizedOnce, int* pLength)
{
       string rv = NULL;
       if (*pTokenizedOnce == false)
       {
           *pTokenizedOnce = true;
           #ifdef _WIN32
               rv = strtok_s(sStr, delimiter, &gContext);
           #else
               rv = strtok_r(sStr, delimiter, &gContext);
           #endif
       }
       else
       {
           #ifdef _WIN32
               rv = strtok_s(NULL, delimiter, &gContext);
           #else
               rv = strtok_r(NULL, delimiter, &gContext);
           #endif
       }

       if (rv != NULL)
           *pLength = strlen(rv)+1;
       else
           *pLength = 0;
       return rv;
}

########################## End Code ######################################

############################# Output ###################################

########################################################################