Write a function - Practice #1

◀ Steps to Write a Function ▶ Write a function - Practice #2

Amazon Let’s write a function that parses a string. Let’s say the string contains data items that are separated by ‘#’s and the last item also has a ‘#’ appended to it. For example, “finite#programming#is#a#great#book#” is a valid string. Here are the function’s specifications:

The function takes as argument a string to be parsed and an int specifying which substring to return, starting at 1.
The function returns a string which is either the target or an empty string if the target is not found.
A for loop and several if-else statements should suffice.

For example, if the string to be parsed is “i#love#you#dad#and#mom#haha#” and the string we want is the 5th one, then the function should return “and”.

Again, try to write the program by yourself. Don’t be frustrated if you meet obstacles; try to leap over them. Practice makes perfect.

Step 1
Let’s first determine the preconditions and postconditions of the function. The first argument is a string, and the second one is an integer. If the first argument is not a valid string, the function may not return the correct result. If the second argument is negative or is too big, the function should return an empty string.

Keep in mind that segmentation fault is not an option.

Let’s write down the preconditions and postconditions in a more formal way:

Precondition: The first argument is a string; the second argument is an int.

Postcondition: If the first argument is not a valid string, the function may not return the correct result. If the second argument is negative or is too big, the function should return an empty string.

Now let’s draft a skeleton of the function. What the function does is straightforward and should not confuse you. Here is a skeleton I came up with:

/*
precondition: s contains data, delimited by ‘#’; n is the position of the data desired
postcondition: returns the desired data; if error occurs, return an empty string
*/
string parse(string s, int i) {
- use a for loop to scan every single character in s
- do the following inside the for loop
do nothing until the (i-1)’th # is reached, which signals the start of the 	target
start collecting the characters until the next # or the end of string is reached
- return the string just collected
- if no string is collected, return an empty string
}

Step 2
As you can see, we need a string to keep track of the target we need to return; we need a counter that counts the number of #’s so that we know when we need to start collecting data; we also need as many indices as the number of for loops. Here is the modified skeleton:

/*
precondition: s contains data, delimited by ‘#’; n is the position of the data desired
postcondition: returns the desired data; if error occurs, return an empty string
*/
string parse(string s, int i) {
	int i, j;
	string t="";
	int counter=0;

- use a for loop to scan every single character in s
- do the following inside the for loop
do nothing until the (i-1)th # is reached, which signals the start of the target
use a for loop to collect the characters until the next # or the end of string is reached
- return the string just collected
- if no string is collected, return an empty string
}

As you can see, I modified the skeleton slightly and now I need to use two for loops.

Step 3
Interrelation: If s uses index i or j to access a character of the string, the index cannot be outside its bounds.

State: i and j are indices for the two for loops, and you should use one in the first for loop and the other in the other for loop. This is also a common source of bugs—reusing a variable when you are not supposed to.

Beginner programmers may use the same variable for indexing both for loops and the program produces mysterious results.

On the other hand, t should contain the target string right before its content is returned, and counter should point to the correct data item before t can start collecting.

Step 4
Now let’s code it. After you write your own version, compare it with mine, which looks like:

#include<iostream>
#include<string> 	/* or <string.h> */
using namespace std;
/*
precondition: s contains data, delimited by ‘#’; n is the position of the data desired
postcondition: returns the desired data; if error occurs, return an empty string
*/
string parse(string s, int n) {
	int counter=0;

/* use a for loop to scan every single character in s */
	for(int i=0;i<s.length();i++) { 	
		if(s[i]=='#') 		/* do nothing until the (i-1)th # is reached */
			counter++;
		if(counter==n-1) {
/* collect the characters until the next # or the end of string is reached */
			string t="";
			for(int j=i+1;j<s.length();j++) {
				if(s[j]=='#')
					return t;	/* return the string just collected */
				t+=s[j];
			}
		}
	}
	return ""; /* if no string is collected, return an empty string */
}

Everything looks good. If you run this function to test it, however, you will realize that there is a tiny bug in it. This function works with n bigger than or equal to two; it misses the first character of the target when n is one.

Debugging is part of step 4, so let’s focus on why the function does not work properly when n is one. After carefully inspecting the code, you should realize that the second for loop starts at index i+1, and when n is one, it skips the first character; when n is two or bigger, it skips ‘#’. Now that we’ve identified the bug let’s get rid of it.

One solution is to treat it as a special case: test to see if n is 1 before program enters the first for loop; if so, start collecting data and return it; if not, enter the for loop.

Treating exceptions as special cases is often practiced, but it requires more code, making the function inelegant. Let’s try to come up with a cleaner way to fix this bug.
What about switching the two if blocks inside the first for loop? That way we just start collecting characters once we are at the right place! A slight modification to the function yields the following:

#include<iostream>
#include<string> 	/* or <string.h> */
using namespace std;
/*
precondition: s contains data, delimited by ‘#’; n is the position of the data desired
postcondition: returns the desired data; if error occurs, return an empty string
*/
string parse(string s, int n) {
	int counter=0;

/* use a for loop to scan every single character in s */
	for(int i=0;i<s.length();i++) {	
		if(counter==n-1) {	
/* collect the characters until the next # or the end of string is reached */
			string t="";
			for(int j=i;j<s.length();j++) {
				if(s[j]=='#')
					return t;	/* return the string just collected */
				t+=s[j];
			}
		}
		if(s[i]=='#') /* do nothing until the (i-1)th # is reached */
			counter++;
	}
	return "";	/* if no string is collected, return an empty string */
}

After examining the code mentally, you shouldn’t have any problem seeing how the bug is removed. This version works perfectly and always preserves preconditions. In addition, it never gives a segmentation fault no matter what the arguments are.

Let’s do another practice next! I know you have a hankering for more don’t you?

◀ Steps to Write a Function ▶ Write a function - Practice #2

fShare

Questions? Let me know!

Chapter 12.9

Write a function - Practice #1