Primitive String trimmer in C

Question

I just picked up C and am following through The C programming language.

I've previously got experience with a lot of 'higher'-level languages, so when I saw this exercise in the book:

Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.

I thought I'd create a very basic and primitive trim-program that takes an input and removes all superfluous white-spaces (more than 1 in a row) and prints out a 'trimmed' string.

As mentioned I just recently started and we haven't covered dynamic arrays yet, so I'm just using static ones.

But I was hoping to get some feedback on my solution:

#include <stdio.h>

/*
** A primitive trimmer
** to remove any superflous
** whitespaces in a given
** string (input).
*/

int main () {

    /*
    ** Setting up the variables
    **
    ** Working with static
    ** arrays since I haven't
    ** been introduced to dynamic.
    */
    char input [100], output[100];
    fgets(input, 100, stdin);
    int i = 0, k = 0;

    // Looping over input until hitting
    // an item containing a null-char.
    while (input[i] != '\0') {
        if (input[i] == ' ') { // hitting first space.
            int j = i + 1;     // initiating temporary counter.
            if (input[j] != '\0') {
                               // find index of first non-space
                               // character after initial space.
                while (input[j] != '\0' && input[j] == ' ') {
                    if (input[j] == ' ') {
                        i++; // keep indexing input-index
                    }
                    j++; // keep incrementing temporary indexer.
                }
            }
        }
        output[k] = input[i]; // insert non-space item into output.
        i++;                 // increment input-indexer.
        k++;                 // prepare output-indexer for next non-space.
    }
    printf("%s", output);     // print trimmed input.
}

It's not going to be pretty and you might not like it, but please keep in mind that I am new to the language!

I'd like to get feedback on my overall solution, any thoughts on the baseline algorithm and how well I'm following best (syntactical) practices.

Answer 1

int vs size_t

Accordingly to the c language specification, it's highly recommendable to use size_t as the type for index variables. So in your case...

int i = 0, k = 0;

should be:

size_t i = 0, k = 0;

---

if condition repeats while condition

I was a bit confused by this piece of code

while (input[j] != '\0' && input[j] == ' ') {
  if (input[j] == ' ') {
    i++; // keep indexing input-index
  } 
  j++; // keep incrementing temporary indexer.
} 

Specifically the if condition - it will always be true due to the while condition logic. So, as result, variable j just duplicates i with an invariant j = i+1.

---

Lack of null character

If you test your code on any string input, you will notice that the program prints some strange characters after your result. It happens because you didn't copy the \0 character to the output array.

---

Taking all this into an account (as well as @pacmaninbw's and @holroy's recommendations)

#include <stdio.h>
#include <ctype.h>

#define MAX 100

int
main ()
{
  char input [MAX], output[MAX];
  fgets(input, MAX, stdin);
  size_t inputIndex = 0, outputIndex = 0;

  while (input[inputIndex] != '\0')
    {   
      output[outputIndex++] = input[inputIndex];
      if (input[inputIndex] == ' ')
        while(input[++inputIndex] == ' ')
          ;   
      else
        inputIndex++;
    }   
    output[outputIndex] = '\0';
    printf("%s", output);
}

Answer 2

It's a nice beginner effort, keep up the good work.

This program can be and probably should be expanded, it will only process a single line of text. The while loop you have in the program should be moved into a function that processes a single line of text, in the main program you should have a loop that reads lines until there are no more lines. A getchar() version of this program may not have this limitation.

Rather than checking specifically for space, you should include ctype.h

#include <ctype.h>

It has implemented a lot of functions such as isspace(), isdigit(), isalnum(), isupper(), islower(), toupper(), and tolower() as macros. This should be more portable than that the check you have for ' '.

           if (isspace(input[i]) { // hitting first space.

Use Meaningful Variable Names

It's a bad practice to use single character variable names. using i, j, k etc. is a throwback to Fortran that allowed undeclared integer variables starting with those letters. Using meaningful variable names makes the code easier to read, understand and debug. It also reduces the number of comments necessary.

Some examples might be:

int inputIndex = 0;
int outputIndex = 0;

It's a bad habit to declare all of the variables on one line. Each variable should be on it's own line to make it easier to find the declaration.

If you have read the chapter on pointer variables you might want to use

char *inputCharacterP;
char *outputCharacterP;

It is more efficient than using input[inputIndex];

Use Symbolic Constants Rather Than Numbers

In C you can define symbolic constants using the #define pre-processor directive.

#define IO_CHARACTER_ARRAY_SIZE 100
int main() {
    char input[IO_CHARACTER_ARRAY_SIZE];
    char output[IO_CHARACTER_ARRAY_SIZE];

There are multiple benefits to this:

1. First you can easily change the size of the array by changing the code in only one place.
2. It makes the code more readable.
3. If a for loop is used the same constant can be used in the for loop to make sure that arrays aren't indexed past the size of the array.

Given the current code you can't walk off the end of the array because fgets() terminates a line of code with '\0', that may not always be the case. Indexing past the end of the array can produce unknown results. A slightly safer version of the while loop is

    while ((inputindex < IO_CHARACTER_ARRAY_SIZE) && (input[inputIndex] != '\0')) {
    }

It's possible that the magic number (numerical constant rather than symbolic constant) 100 is a bad choice. Memory is allocated by word size which is always going to be a power of 2. Depending on the computer this can be either 4 bytes or 8 bytes (4 chars or 8 chars). It's not critical in this particular instance, but if the array is within a struct it could affect memory allocation.

Answer 3

The answers by pgs and pacmaninbw has their good points regarding code style and issue with your code, so I'm going to follow up on the "possible duplicate issue" and your statement: "any thoughts on the baseline algorithm and how well I'm following best (syntactical) practices."

When reading the exercise goal and your implementation I thought of two common principles applied to programming: the KISS principle, and Occam's Razor. Your code is overcomplicating the exercise goal, and implements stuff which are not required by the goal. In general, this is something one as a programmer should try to avoid. (NB! I do see that it is interesting as a learning experience, but you'd be surprised to see how many overengineered code solutions there exists in the real world)

First of all, your solution adds side effects to the original goal. Your solution reequires a line to be ended, before outputting anything. If you type less than a 100 characters, or don't end it with return/line shift, it won't output anything.

Secondly, although not a lot, your code requires more memory than the goal expresses. As the other (somewhat duplicated question) shows, there is almost no need to store anything besides the current character read, and a flag variable to indicate whether previous character was a space or not. Your code requires two 100 byte arrays and several looping characters. If this had been on a memory restricted device, it would have been catastrophic.

Thirdly, by adding/changing goals, you add/remove features. In your case, you limit the input/output to a 100 characters by not having a while loop around the fgets(), and you introduce a possible case related to flushing of output buffers by using printf().

(And if I remember correctly, if you're really unlucky you could get issues by combining fgets() and printf() which uses different system calls for reading and writing. Most likely not an issue in your case, as you use one for input and one for output... If however, you'd use fputs() and printf(), or fgets() and scanf() at the same time, you could end up on a heap of trouble.)

So to summarize, overengineering a solution or extending it beyond the goal could be a bad thing to do. In your case, for learning purposes, it can learn you something else. I would however then have extended the goal beforehand, and emphasize why you've extended it and what your new goals are. For example, to read line by line stripping away extra spaces for a faster handling of larger input scenarios.

Let me finish off by saying, that in general your code does look good with proper indentation and a good brace style. Maybe a little too much commenting on obvious stuff, but also some good and vital comments to what happens where in your code.

Answer 4

Skip checking if the input character is a space, instead check if it is NOT a space, if so, add it to the output and increment k. This method would also allow you to do this trim in place, allowing you to drop having to use the output buffer (if desired).

Note I do not think this is a true trim, since you will still have at least one space at the start and end, I believe trim would remove all preceding and trailing spaces.

int i=0,k=0;

while (input[i]) 
{
   // Add char if its not a space, or it can be anything if its the first,
   // or if at least one char is in the output and the last is not a space
   if ((input[i]!=' ')||(!k)||(k&&output[k-1]!=' ')) output[k++]=input[i];
   i++;
}
// Dont forget to terminate output
output[k]=0;

Answer 5

Your code as written

• does not break the problem up into functions. That's just bad policy.
• uses, without reason, array-indexing. Array-indexing is fine if you need it, but you don't here. You only need to scan through the input once. Use pointer arithmetic instead. It's faster and more readable.
• embodies a complicated algorithm. It should a simple two-state state machine. At each point, you are either "eating" white-space, or else you're not.

Here is an improved version (without the file I/O):

int isspace(c) {
  return c == ' ';
}

void condense(char *d, const char *s) {
  int eating = 0;
  char c;
  while ((c = *s++)) {
    if (eating) {
      if (!isspace(c)) {
        *d++ = c;
        eating = 0;
      }
    } else {
      *d++ = c;
      eating = isspace(c);
    }
  }
  *d = 0;
}

This certainly could and should be improved, but it's a start.

“There are two ways of constructing a piece of software: One is to make it so simple that there are obviously no errors, and the other is to make it so complicated that there are no obvious errors.”
― Tony Hoare

Answer 6

I'll go over your entire program line by line:

char input [100], output[100];
fgets(input, 100, stdin);
int i = 0, k = 0;

First of all, I don't know if you're aiming for standard conformity, but I must say that mixing declarations and code is illegal in C90 (so called "ANSI C", even though later standards were created by ANSI too). Changing the order of lines like this will make it C90-compliant:

char input [100], output[100];
int i = 0, k = 0;
fgets(input, 100, stdin);

Secondly, right from the beginning I can see that your program can't handle more than one hundred characters. Local arrays (I'd avoid calling them static, you might not know about this yet, but there is a static keyword which can precede a declaration of a variable and changes it's behavior drastically) are actually a good choice for this type of problem, you just have to use a loop to take data in batches. I'd also like to point out that fgets stops when it reads a newline character and I'm guessing this wasn't your intention, because in the description of the problem you never say "line" once, only "input." Defining any constants you use is a good practice and makes it easy to change them later. I replaced printf("%s", output) with fputs(output, stdout), because I think it's slightly more readable. Summing up, I'd structure the code like this:

#define BUF_LEN     100

int main()
{
    int i, k;
    char input[BUF_LEN], output[BUF_LEN];

    while(!feof(stdin)) /* until we reach the end of stdin */
    {
        i = k = 0;
        fgets(input, BUF_LEN, stdin); /* read the next batch of data */

        ...

        fputs(output, stdout); /* print output for the current batch of data */
    }
}

Now as for the actual algorithm:

while (input[i] != '\0') {
    if (input[i] == ' ') { // hitting first space.
        int j = i + 1;     // initiating temporary counter.
        if (input[j] != '\0') {
                           // find index of first non-space
                           // character after initial space.
            while (input[j] != '\0' && input[j] == ' ') {
                if (input[j] == ' ') {
                    i++; // keep indexing input-index
                }
                j++; // keep incrementing temporary indexer.
            }
        }
    }
    output[k] = input[i]; // insert non-space item into output.
    i++;                 // increment input-indexer.
    k++;                 // prepare output-indexer for next non-space.
}

C++ style // comments are also illegal in C90. You often check if the current character is not '\0', and then test if it equals space right afterwards. A character cannot be '\0' and ' ' at the same time, so the first check is unnecessary. I like checking for null character by simply testing the variable itself (you'll see what I mean in the sample below), but that's just a preference. You can replace while loops with a for loop to make it more readable. The last thing is that you often don't need to use variable as an index and increment it separately, because post-increment operator will give you the current value while also incrementing the variable by one. As pointed out by others, you need to terminate output with a null character. The end result is this:

while (input[i]) {
    /* input[i] instead of input[i] != '\0' */
    if (input[i] == ' ')
        for (j = i + 1; input[j] == ' '; j++) /* compressed the next few lines into this for loop */
            i++;
    /* I removed brackets to make the code more compact, 
     * but that's just a matter of preference */
    output[k++] = input[i++];
}
output[k] = '\0';

Regarding the performance, I benchmarked both this version and the simpler one which uses only getchar and putchar with /usr/bin/time. I wrote another program that prints out random data with spacing, connected it to the benchmarked program through a pipe and then redirected entire output to /dev/null. This version was about three times faster, though I used a buffer of 4096 bytes. Since in the end it's hardly more difficult to implement, it seems like a better way to approach this problem.