String-crunching routine

Question

How can this be optimized?

char *crunch(char *s)
{
  char *temp,buff[MAX];
  int repeat,count,i,j,k;

  if (*s == '\0')
    return NULL;
  temp = (char*)malloc((strlen(s) + 1) * sizeof(char));
  if (isdigit(*s))
    return NULL;
  repeat = 0;
  for (i = 0, j = 0;i < strlen(s);)
  {
    temp[j++] = s[i++];
    count = 1;
    while (s[i] == s[i - 1])
    {
      count++;
      i++;
      repeat = 1;
    }
    if (isdigit(s[i]) && repeat == 1)
      return NULL;
    if (isdigit(s[i]) && count != 1)
      return NULL;
    else if (isalpha(s[i]) && count != 1)
    {
      temp[j++] = count + 48;
    }
    else if (isdigit(s[i]))
    {
      for (k = 1;k < (s[i] - 48);k++)
        temp[j++] = s[i - 1];
      i++;
    }
  }
  temp[j] = '\0';
  return temp;
}

Examples:

Input: "aabbccdef"
Output: "a2b2c2def"

Input: "a4bd2g4"
Output: "aaaabddgggg"

Answer 1

As written by Jonathan and

• Always put a blank line after every }
• Always use { } even for single line if/for/while. There is a class of errors where you add a second line in the if but it isn't "in" the if, it is outside. Something like:

if (1 == 1)
   do something

and then you change it in

if (1 == 1)
    do something
    do something else

the do something else isn't in the if, even if you spaced it like it was :-)

If you don't want to use the {} a good style that solves it is to put the second part of the instruction in the same line

if (1 == 1) do something

I don't like it very much (because it makes the line longer to the right) but it is more difficult you make the "bad" error of missing {}

The strlen can be pre-calculated once.

The if (isdigit(*s)) can be put before the malloc.

If you malloc a block of memory and then return NULL you should free the block of memory, otherwise you cause a memory leak.

Please, don't use the pre-fix/post-fix increment operator in the middle of other instructions, they make the code less readable.

This

temp[j++] = s[i++];

is the same as

temp[j] = s[i];
i++;
j++;

but the second is much more readable, because you don't have to think to the order of the operations.

If you have to decompress the string (from a4bd2g4 to aaaabddgggg) the buffer size is too much small.

Considering the compression and decompression are quite different, I would do it in two passes:

first pass: sum all the digits and count all the characters. If the sum is zero the it's compression, do it in function 1. If sum <> 0 it is decompression. With the sum of the digits and the count of the characters you know the size of the buffer you'll need.

If you want to impress your teacher, you should make it work for aaaaaaaaaa (it is 10x a)... It would compress to a9a and aaaaaaaaaaa (11x a) a9a2.

Answer 2

Algorithm

1. It feels wrong to put both versions of the code in one single function. It would make more sense to have an encode and decode function.
2. Your code doesn't work for a10 or aaaaaaaaaaaaaa.
3. You are lucky your code doesn't segfault. For example, for "a9", temp is only two characters long, and you're writing in nine characters: you're writing outside of the allocated data! You should run throught the string once to see how much memory you're going to need.

Otherwise, it is an intuitive algorithm.

Code

1. Comment your code!
2. You don't use buff, remove it.
3. The second if should be an else if.
4. Use '0' instead of hardcoding 48.
5. Convert s[j] into an int and use for (k = 1; k < n; k++) which is easier to read.

Answer 3

Suggestions for improving this code:

1. Comment the hell out of it. Your teacher/professor needs to be able to understand what you're doing and why you're doing it. Imagine you're working on a real-world project and you fall off a cliff--your teammates need to be able to pick up after you. Comments exist for this purpose.

2. Clean up your whitespace. The statements executed in a branch (e.g. if (foo) { bar; }) should be placed on their own lines. This makes it easier to see at-a-glance what is the consequence of what.

I have not examined the actual logic of the program.

Answer 4

Here are some comments on the code, some of which might be duplicates of what others have noted, so sorry for that.

General points:

• When writing prose, one often starts with a sketch of the text and then sharpens it up, removing redundancies, contradictions, repetition etc. Coding is similar and your function looks like a first sketch. Many programmers stick with the first sketch, but you should aim for better. There are things in the function that make it obvious that you haven't refined the solution - that's ok: you are learning (aren't we all). You took the trouble to submit it for review which bodes well.

• I'm always suspicious of functions with nested loops. Sometimes, rarely, they are necessary, but in your case, as in most, they are undesirable.

• It also catches my attention when the same function is called with the same parameters several times. Again, this can sometimes be worth doing, but calling isdigit(s[i]) three times doesn't qualify.

• Many times people write dumb comments that explain the obvious. You pass this one with flying colours. But a header with some comments describing the interface and the purpose of the function is necessary.

Specific points:

• A function needs to have a well defined job that is explained by its name. If a function is difficult to name it often indicates that it is not really a coherent function at all. Your function implies that the string is reduced in size, whereas in fact it is either reduced or expanded depending upon its contents. Better stated (thanks to @Jonathan Grynspan), it would be runlength_encode_decode; it would be better as two separate functions. Maybe the homework exercise was to write a single function, in which case it was perhaps badly defined. If it must be combined into one function, I would expect it to have two distinct parts, such as

  static char * runlength_encode_decode(const char *s, char *buf, size_t size)
  {
      if (isdigit(*s))
          return NULL;
  
      if (strpbrk(s, "0123456789")) /* inefficient is s is long , but who cares? */
          decode(s, buf, size);
      else
          encode(s, buf, size);
      return buf;
  }
  

• s is not modified so make it const

• variables are best defined one-per-line.

• malloc does not need casting (in C) and needs checking for failure. The buffer is also too small. But arguably, malloc doesn't belong inside the function. It would be better to pass an output buffer and its size into the function. This simplifies recovery on failure as crunch() doesn't have to bother with freeing the buffer (which you don't anyway, although in your case it is an error).

• sizeof(char) is 1 by definition in C. It is just noise, so please don't use it.

• strlen should not be in the loop as it will be executed each time round the loop. The length of the string does not change, so do it just once at the start - if it is necessary at all.

• for-loops are best if the control variable is modified in the 3rd part of the for() statement, not in the body of the loop.

• Your indices are arguably unnecessary. Instead of temp[j++] = s[i++] you can use *temp++ = *s++ to perform the assignment and advance the pointers. Some people may object to this but it is a basic C idiom. You will see it often, so get used to it.

• The while-loop should be extracted to a separate function. It does something very specific - counting the span of the current character - easily defined and easily encapsulated in a function. Ignore anyone who complains about function call overheads (inline such small functions by all means).

  Something like this, for example, called before you increment s:

  static int span(const char *s)
  {
      char str[2] = {0,0};
      str[0] = *s;
      return strspn(s, str);
  }
  

• The three conditional statements would be better with brackets around the second condition - i.e. (repeat == 1) - to avoid depending upon knowing the operator precedence.

• the second isdigit() conditional is already covered by the first - repeat is only even 1 when count > 1

• count + 48 should be count + '0' but fails if count > 9

• The for-loop should be extracted into a separate function. See comments on the while-loop. Note that (s[i] - 48) will be repeated each time around the loop.

  Something like this, for example:

  static char * dupchar(int ch, char * out, int n)
  {
      for ( ; n > 0; --n)
          *out++ = ch;
      return out;
  }