How do I complete K&R Exercise 2-4?

Question

I'm learning how to write programs in C using the k&r book (The C Programming Language) and I have a problem with one of the exercises. It's asking me to detect and remove a character in string s1, which matches any characters in the string s2.

So, say s1 = "A";

And s2 = "AABAACAADAAE"

I want it to return "BCDE"

I know I'm on the right path towards it, i just don't know how to design programs very well, could you give me any additional tips. I tried to read about the binary search tree algorithm, but felt it was a little too advanced for this mundane task.

Thanks everyone!

/* An alternate version of squeeze(s1, s2) that deletes each character in
 * s1 that matches any character in the string s2
 *
 * Angie@odfx.org
 */

#include <stdio.h>
#include <string.h>

void squeeze(char s[], char t[]);

char string[] = "BAD";
char sstring[] = "ABC";

int
main(void)
{
    squeeze(string, sstring);
    return 0;
}

void
squeeze(char s[], char t[])
{
    int i, j, d;

    d = 0;
    if(strstr(s, t) == NULL)
        printf("%c", s[i]);
    s[j] = '\0';
}

Answer 1

Great book. If I were you, I would proceed exactly as for the squeeze() in section 2.8, but instead of a direct comparison (s[i] != c) I would write and exploit a function

 int contains(char s[], int c)

which returns 1 if the string s contains c, 0 otherwise. Start with the simple approach; when it works you may improve performance with more complex solutions (binary search, but note that the problem doesn't require the characters in s2 to be in a particular order).

Answer 2

A binary search is way overkill for this. You need three indices. One index (i) to walk through s, one index (k) to walk through t, and one index (j) to keep track of where you are in s for the characters that you need to keep because they are not in t. So, for each character in s, check and see if it is in t. If it is not, keep it in s.

void squeeze(char *s, char *t) {
    int i, j, k;
    int found = 0;

    for(i = j = 0; s[i] != '\0'; i++) {
        found = 0;
        for(k = 0; t[k] != '\0' && (found == 0); k++) {
            if(t[k] == s[i]) {
                found = 1;
            }
        }

        if(found == 0) {
            s[j++] = s[i];
        }

    }

    s[j] = '\0';
}

Answer 3

Here is my very clear and simple answer with some logical explanation.

#include<stdio.h>
void squeeze();

Inside main we type our tested string and wantbedelete string that has the chars that we want to delete from yourstring.

int main() 
{

    char yourstring[] = "AABAACAADAAE";
    char wantbedelete[] = "A";

    squeeze(yourstring, wantbedelete);
    printf("%s", yourstring);

    return 0;
}

The logic inside the squeeze function is as follows,

• loop inside the wantbedelete char by char
• then, for any char found in wantbedelete we loop through the whole yourstring
• then, we compare if the two founded char does not match, we update (save) that char from yourstring to yourstring so basically here just we define a new index(k) to keep track and update the only wanted characters
• now the trick here is that we want to reset our index each time we go back again to the outer loop that is looping through each char we intend to delete so that we end up with the only wanted string.

I highly recommend using the debugger and following each line inside the squeeze function so that you would be able to understand the logic more clearly.

void squeeze(char s1[], char s2[]) 
{
    int i, j, k;

    k = 0;
    for (i = 0 ; s2[i] != '\0' ; i++) /* loop for each char we want to delete with index i */
    {
        for (j = 0 ; s1[j] != '\0'; j++) /* loop for each char we want to keep with index j */
        {
            if (s2[i] != s1[j]) /* if the two chars do not match */
            {
                s1[k++] = s1[j]; /* update s1 with the char that we want to keep using index k */
            }
        }
        s1[k] = '\0'; /* since we update all char that we want to keep, the last char of index k must be empty */
        k = 0; /* reset index k so we will be ready for the next char that we want to delete from s1 */
    }
}

Answer 4

void squeeze(char s1[], char s2[])
{
    int i,j,k;
    char c;
    for(i=0;s2[i]!='\0';i++)
    {
        c=s2[i];
        for(j=k=0;s1[j]!='\0';j++)
            if(s1[j]!=c)
                s1[k++]=s1[j];
            s1[k]='\0';
    }
}

Answer 5

You don't need a fancy binary search to do the job. What you need is a double for loop that check for occurrence of each char in one string in another, and copy the non-occurring chars into a third char array (which is your result).

Code can be something like the following (not tested!):

char *s1, *s2, *result; /* original strings and the result string */
int len1, len2; /* lengths of the strings */
for (i = 0; i < len1; i++) {
   for (j = 0; j < len2; j++) {
     if (s1[i] == s2[j]) {
       break;
     }
   }
   if (j == len2) {  /* s1[i] is not found in s2 */
     *result = s1[i]; 
     result++; /* assuming your result array is long enough */
   }
}

Answer 6

this is my function:

void squeeze(char s1[],char s2[])
{
int i,j,p;
int found;

p=0;
for(i=0;s1[i]!='\0';i++)
{
    for(j=0;s2[j]!='\0';j++)
        if(s1[i]==s2[j])
            found=YES;
        else
            found=NO;
    if(found==NO)
        s1[p++]=s1[i];
     }
    s1[p]='\0';
}