This assignment will force you to reckon with pointers. Fun! Specifically, you will be designing and implementing some functions operating on char pointers so you can treat them as "C-style strings".
Your solutions may not include any external packages other than < iostream >, < fstream >, < stdlib.h >, and < cctype >.
The purpose of this homework is to:
In C++, we've mainly been using the string type to store and manipulate more than one character at a time. But theres another way to represent strings, which is used in the original C language: as an array of characters! However, the designers of C decided to add a clever twist to make a plain old array of characters distinct from a string. A "C-style string" is specifically defined as an array of characters that, at some index in the array, contains the special character '\0, which we call the NULL character.
Although other characters may exist in the array after the NULL character, it denotes the logical end of the string, i.e., all of C's string functions treat the first NULL character as the end of the string. For example, to represent the C-style string "hello", we could declare and initialize a char array with either of the following lines of code:
char str1[6] = {'h', 'e', 'l', 'l', 'o', '\0'};
char str2[6] = "hello";
We need to reserve a slot for the NULL character at the end, as otherwise C's string functions dont know where the string ends! When we use a string literal to initialize a char array, the NULL character is inserted automatically at the end. However, this NULL business means we can also change a C-style string just by inserting a new NULL character or removing one. For example, the code
char str1[6] = {'h', 'e', 'l', 'l', 'o', '\0'};
str[2] = '\0';
cout << str << endl;
would print out he to the screen, because the first NULL character in the array comes after the 'e' character.
Your task is to implement a program that reads in lines from a file, and for each line, determines if any word in the line is a proper substring of any other word in the line. If so, you will print out a message about this substring relation. To understand this problem, we need some definitions. For this assignment, a word is any sequence of one or more alphabetical characters. A string word1 is a proper substring of a string word2 if word1 occurs in word2 AND word1 is not equal to word2. For example, if your input file contained the single line
It is not very very hard to find every substring of any stringy string!
then your program might output
very is a substring of every
very is a substring of every
string is a substring of substring
string is a substring of stringy
because "very" is found in the word every (and occurs twice in the line), while string is found in the words substring and stringy. While very is a substring of itself, it is not a proper substring. You may ignore whitespace and punctuation, and your program should be case-sensitive (so I would not be a substring of find).
To help solve this problem, you must implement three C-style string processing functions. One of them tests if a C-style string word2 is a prefix of another C-style string word1; word2 is a prefix of word1 if word2 is found at the start of word1 (e.g., "string" is a prefix of both stringy and string). The three functions have the following function declarations:
/* is_equal
* Arguments: two pointers to C-style strings
* Description: determines if two C-style strings are equivalent
* Return value: true if strings are equivalent, false otherwise
*/
bool is_equal(char *word1, char *word2);
/* is_prefix
* Arguments: two pointers to C-style strings
* Description: determines if string word2 is a prefix of string word1
* Return value: true if word2 is a prefix of word1, false otherwise
*/
bool is_prefix(char *word1, char *word2);
/* find_substring
* Arguments: two pointers to C-style strings
* Description: determines whether string 'needle' is a proper substring of
*
string 'haystack'.
* Return value: if 'needle' isn't a proper substring of 'haystack', return
*
nullptr. Otherwise, return a pointer to the beginning of the
*
first occurrence of 'needle' within 'haystack'.
*/
char *find_substring(char *haystack, char *needle);
You should figure out how the first two functions can help you implement the third. For all three functions, consider looping over every element of one or both of the two C-style string arguments and testing whether you've hit the NULL character on each iteration.
We have provided you with starter code for cstrings.cpp, along with three input files (input1.in, alice.in, and pangram.in).
cstrings.cpp
#include < iostream >
#include < fstream >
#include < stdlib.h >
#include < cctype > //Lets us use the isalpha function
using namespace std;
const int SIZE = 50;
int read_line(ifstream &infile, char words[SIZE][SIZE]);
bool is_equal(char *word1, char *word2);
bool is_prefix(char *word1, char *word2);
char *find_substring(char *haystack, char *needle);
int main(int argc, char *argv[]) {
if (argc < 2) {
cerr << "ERROR: A filename must be specified as the first argument.\n";
exit(EXIT_FAILURE);
}
/* Open the file */
ifstream infile;
infile.open(argv[1]);
/* Error check */
if (infile.fail()) {
cerr << "ERROR: Error opening file - ";
cerr << "please check that you specified the correct file name\n";
exit(EXIT_FAILURE);
}
int total_words = 0;
char words[SIZE][SIZE];
total_words = read_line(infile, words); //Read the first line from the file
while (!infile.eof()) {
/* DO NOT MODIFY THE CODE IN main() ABOVE OR BELOW THIS COMMENT BLOCK */
/* DO NOT MODIFY THE CODE IN main() ABOVE OR BELOW THIS COMMENT BLOCK */
total_words = read_line(infile, words); //Read the next line from the file
}
/* Close the file */
infile.close();
return 0;
}
/* is_equal
* Arguments: two pointers to C-style strings
* Description: determines if two C-style strings are equivalent
* Return value: true if strings are equivalent, false otherwise
*/
bool is_equal(char *word1, char *word2) {
bool equal = true;
int i = 0;
while (word1[i] != '\0' || word2[i] != '\0') {
if (word1[i] != word2[i]) {
equal = false;
}
i++;
}
return equal;
}
/* is_prefix
* Arguments: two pointers to C-style strings
* Description: determines if string word2 is a prefix of string word1
* Return value: true if word2 is a prefix of word1, false otherwise
*/
bool is_prefix(char *word1, char *word2) {
/* YOUR CODE GOES HERE. DELETE THE RETURN STATEMENT BELOW WHEN YOU'RE WORKING
* ON THIS FUNCTION. */
return false;
}
/* find_substring
* Arguments: two pointers to C-style strings
* Description: determines whether string 'needle' is a proper substring of
* string 'haystack'.
* Return value: if 'needle' isn't a proper substring of 'haystack', return
* nullptr. Otherwise, return a pointer to the beginning of the
* first occurrence of 'needle' within 'haystack'.
*/
char *find_substring(char *haystack, char *needle) {
/* YOUR CODE GOES HERE. DELETE THE RETURN STATEMENT BELOW WHEN YOU'RE WORKING
* ON THIS FUNCTION. */
return nullptr;
}
/* Retrieve a line of input from a file, parse it into individual words, and
* store those words in the "words_in_sentence" 2D-array. Each "row" of
* words_in_sentence is another word. Return the total number of words read in.
*
* For example, if we read in the sentence "Here I am!", then the
* first 3 rows (R) and first 5 columns (C) of the words_in_sentence array
* will look like the picture belwo (the empty cells hold garbage values):
*
* C0 C1 C2 C3 C4
* R0: | H | e | r | e | \0 |
* R1: | I | \0 | | | |
* R2: | a | m | \0 | | |
*
* NOTE: We have to write "ifstream &infile" as a parameter to pass an input
* file stream correctly to a function (without needing even more pointers). If
* you need to write a function that takes a file stream as an argument, always
* put the '&' in front of the name of your file stream parameter.
*/
int read_line(ifstream &infile, char words_in_sentence[SIZE][SIZE]) {
int spot = 0;
int word_index = 0;
char *next_word;
char next_char;
infile.get(next_char);
while (!infile.eof() && next_char != '\n') {
next_word = words_in_sentence[word_index];
//Written question 1 asks about this loop
while (!infile.eof() && isalpha(next_char)) {
next_word[spot] = next_char; //Written question 2 asks about this line
++spot;
infile.get(next_char);
}
if (spot > 0) {
next_word[spot] = '\0';
++word_index;
spot = 0;
} else {
infile.get(next_char);
}
}
return word_index;
}
alice.in
CHAPTER II. The Pool of Tears
'Curiouser and curiouser!' cried Alice (she was so much surprised, that
for the moment she quite forgot how to speak good English); 'now I am
opening out like the largest telescope that ever was! Good-bye, feet!'
(for when she looked down at her feet, they seemed to be almost out of
sight, they were getting so far off). 'Oh, my poor little feet, I wonder
who will put on your shoes and stockings for you now, dears? I am sure
_I_ shall not be able! I shall be a great deal too far off to trouble
myself about you: you must manage the best way you can;--but I must be
kind to them,' thought Alice, 'or perhaps they will not walk the way I want
to go! Let me see: I will give them a new pair of boots every Christmas.'
pangram.in
The quick brown fox jumps over the lazy dog.
input1.in
It is not very very hard to find every substring of any stringy string!