10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you need to read whole line into the memory? Why not to use just getchar and putchar? \$\endgroup\$ – pgs Apr 21 '17 at 12:54
  • 3
    \$\begingroup\$ There is no reason as to why I need to read a whole line of code. I simply thought it would be an interesting spin on the exercise instead of just reading a single character per iteration. If I'm not completely off-base here getchar and putchar only works on characters. \$\endgroup\$ – geostocker Apr 21 '17 at 12:56
9
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ is correct, you actually have a bug in your code because of the lack of NULL termination on output. \$\endgroup\$ – pacmaninbw Apr 21 '17 at 14:21
  • 4
    \$\begingroup\$ I just saw one really bad smell of C-programming: The while (something);. That is really bad coding advice for new beginners, to have empty loops like that. \$\endgroup\$ – holroy Apr 21 '17 at 14:49
  • 1
    \$\begingroup\$ @pgs, Both having the semicolon on a new line, or adding an empty brace set to indicate the empty loop would be better, in my opinion, rather than almost hiding the semicolon at the end of line. As it stands, it seems like wrong indentation on the else statement, and that the else statement is what happens during the while loop. Which really doesn't make any sense. You cold possibly also either have an empty comment in the while block, or move out the ++inputIndex into the while block to indicate the action of the while loop. \$\endgroup\$ – holroy Apr 21 '17 at 15:05
  • 3
    \$\begingroup\$ In the NetBSD project, the convention for this kind of loops is to write while (condition) continue; — written in two separate lines, of course. \$\endgroup\$ – Roland Illig Apr 21 '17 at 19:14
  • 2
    \$\begingroup\$ Re: "you didn't copy the NULL symbol". NULL is the null pointer constant, best used in context with pointers. The null character or '\0' is the symbol at the end of a string. \$\endgroup\$ – chux - Reinstate Monica Apr 22 '17 at 5:13
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @geostocker Not at the level of C programming you're currently at. The biggest problem I see is the readability. \$\endgroup\$ – pacmaninbw Apr 21 '17 at 14:25
  • 4
    \$\begingroup\$ isspace returns "true" on all kinds of white-space, not just ' '. \$\endgroup\$ – Andrew Apr 21 '17 at 14:34
  • 4
    \$\begingroup\$ Lots of wrong things here. For one, using single letters i,j,k &c for simple array indicies is absolutely the most meaningful and (for an experienced programmer) easiest to comprehend. Excessively verbose and not meaningful names like "inputCharacterP" hinder comprehension. Likewise, it's no more difficult to find the variable names if they're on the same line, and easier to read and see that they're related. \$\endgroup\$ – jamesqf Apr 21 '17 at 19:09
  • 3
    \$\begingroup\$ isspace invokes undefined behavior when invoked with a negative char value other than EOF, and that can happen quickly with UTF-8 encoded text on x86 machines. \$\endgroup\$ – Roland Illig Apr 21 '17 at 19:17
  • 1
    \$\begingroup\$ Using the single letters i, j, and k when iterating through arrays is very much idiomatic C. It's only when you're getting into fancier operations (eg. a circular buffer) that you should name your indices. \$\endgroup\$ – Mark Apr 22 '17 at 3:46
6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ you could get issues by combining fgets() and printf() - not so. You may get issues by combining stdio with direct system calls (as in printf and write(0, ...), because write bypasses the stdio buffering. Consistent use of stdio is alright. \$\endgroup\$ – vnp Apr 21 '17 at 19:09
  • \$\begingroup\$ I'd also add that for the algorithm in general, it might be a good idea to look beyond simple C, and consider a bit of (f)lex code. It's probably a bit beyond the OP's level, but I've seen a lot of complicated string-handling code in C that could be implemented far more simply (and efficiently!) with flex. \$\endgroup\$ – jamesqf Apr 21 '17 at 19:13
  • \$\begingroup\$ @vnp, I do remember having some issues related to this way back a few decades ago, so I think I'm going to let the statement stand even though consistent use of stdiois better nowadays. But the case you're mentioning is indeed a dangerous area to venture into it, and should be avoided at all costs. \$\endgroup\$ – holroy Apr 21 '17 at 19:14
3
\$\begingroup\$

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;
\$\endgroup\$
  • 2
    \$\begingroup\$ Talking about removing space here—you should leave some space around binary operators, to support human readers of the code. \$\endgroup\$ – Roland Illig Apr 21 '17 at 19:23
  • \$\begingroup\$ Perhaps this is easier to read: for (int i=0,k=0;i<=strlen(input);k+=((input[i]!=' ')||(!k)||(k&&output[k-1]!=' '))?1:0,i++) output[k]=input[i]; Just messing with you, yes I know, I like it compact. \$\endgroup\$ – sthede Apr 21 '17 at 19:44
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ isspace is also found in ctype.h. DRY \$\endgroup\$ – smac89 Apr 22 '17 at 1:26
  • 1
    \$\begingroup\$ @smac89, isspace in ctype.h returns true for any of the current locale's whitespace characters. The problem specification doesn't say what, if anything, should be done with consecutive sequences of horizontal tabs, or alternating newlines and form feeds, or most of the other things the standard library's isspace will trigger on. \$\endgroup\$ – Mark Apr 22 '17 at 3:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Never use feof, and forget about C90. Its successor C99 has been available for 18 years now. \$\endgroup\$ – Roland Illig Apr 21 '17 at 19:25
  • \$\begingroup\$ fgets(input, BUF_LEN, stdin); ... fputs(output, stdout); without checking the return value of fgets() leads to UB. Recommending !feof(stdin) instead is bad advice. \$\endgroup\$ – chux - Reinstate Monica Apr 22 '17 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.