4
\$\begingroup\$

The code below capitalized the first letter of every word in a sentence. It handles an arbitrary number of spaces in any part of string. It works. Can it be optimized further?

void capitalize_string(char *s) {
  while(*s) {
    while (*s && *s == ' ')
      s++;
    *s = toupper(*s);
    s++;
    while (*s && *s != ' ')
      s++;
  }
}
\$\endgroup\$
1
  • \$\begingroup\$ In *s && *s == ' ' the left condition is excessive since it is always true whenever the right one holds. After the first non-space lookup is done you should check that you haven't found the string's end, otherwise with a string ending in spaces your program crashes. \$\endgroup\$ – bipll Feb 16 '18 at 16:06
7
\$\begingroup\$

Declare the toupper function

The easiest way to provide a prototype is

#include <ctype.h>

Consider matching all whitespace

At present, we don't capitalize a word at the beginning of a line. We could deal with this by using isspace() instead of testing for equality with ' '. Also, we might want to consider a word to start when a letter immediately follows punctuation (such as ", / or -).

Bug: if the string ends with a space

Consider the string " " and walk through.

We loop while (*s && *s == ' ') until s points at the terminating NUL character. Now we upcase that NUL (which is harmless), and increment s again. That's not good.

We need

 if (!*s) { break; }

before line 6.

An alternative approach

Instead of changing between two different loops for whitespace and non-whitespace runs, we can write a single loop if we use a variable to remember what we've most recently seen; I'll call it prev. Start off with it set to a space, so that we'll capitalise the first letter of the string. The code then looks like this:

#include <ctype.h>

void capitalize_string(char *s)
{
    for (int prev = ' ';  *s;  ++s) {
        int current = (unsigned char)*s;
        if (!isalnum(prev) && isalpha(current)) {
            *s = (char)toupper(current);
        }
        prev = current;
    }
}

Note that the <ctype.h> functions all accept (and return) an int that represents an unsigned char version of a character - on platforms where plain char is signed, passing one directly can be undefined behaviour.

Here's a short test program so we can give command-line arguments to try out:

#include <stdio.h>
int main(int argc, char **argv)
{
    for (int i = 1;  i < argc;  ++i) {
        capitalize_string(argv[i]);
        printf("%s\n", argv[i]);
    }
}

A more sophisticated test allows us to check a suite of examples every time we make a change to the code, and allows us to be explicit about our expectations:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int check(const char *input, const char *expected)
{
    char *s = malloc(strlen(input)+1);
    if (!s) {
        perror("malloc");
        return 1;
    }
    strcpy(s, input);

    int err_count = 0;
    capitalize_string(s);
    if (strcmp(s, expected)) {
        fprintf(stderr, "*** Input \"%s\"; expected \"%s\"; got \"%s\"\n",
                input, expected, s);
        ++err_count;
    }

    free(s);
    return err_count;
}

int main()
{
    return check("", "")
        +  check("123", "123")
        +  check("ab", "Ab")
        +  check("AB", "AB")
        +  check("ab cd", "Ab Cd")
        +  /* add more tests here */
        +  check("harley-davidson", "Harley-Davidson")
        ;
}
\$\endgroup\$
2
  • \$\begingroup\$ Some good stuff here, but the question is "Can it be optimized further?" Checking the character class of each character twice is likely to be less optimal. Of course, correct, understandable, and simple are all at least as important as fast. \$\endgroup\$ – Adrian McCarthy Feb 15 '18 at 23:43
  • 1
    \$\begingroup\$ @Adrian - since the kind of optimization wasn't mentioned, I fell back to my default: optimize for maintainability. Well, that's my excuse for not addressing performance, and I'll stick to it! \$\endgroup\$ – Toby Speight Feb 16 '18 at 8:51
3
\$\begingroup\$
void capitalize_string(char *s) {
  char prev_char = ' ';

  while(*s) {
    if (isspace((unsigned char)prev_char) && islower((unsigned char)*s)) {
      *s = (char)toupper((unsigned char)*s);
    }
    prev_char = *s;
    s++;
  }
}

Improvements -

  • Testing characters using ctype.h functions is the safest way to ensure that such programs work irrespective of locale.

  • The cyclomatic complexity of the original function was higher than it needed to be; the inner while loops weren't necessary.

  • The original function had many bugs. After the first inner while loop you should have checked if the character wasn't a '\0' (to break), and if it were a lowercase alphabet, before applying the toupper().

\$\endgroup\$
5
  • 1
    \$\begingroup\$ isspace(c) and islower(c) are UB when c < 0. Suggest islower((unsigned char) c) \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 0:21
  • \$\begingroup\$ Nice tight alternative code. \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 0:26
  • \$\begingroup\$ @chux - How does that typecast help when the char value is (say) -1? Wouldn't it be better to add an assert to verify that the value of the char is not less than 0? \$\endgroup\$ – work.bin Feb 16 '18 at 12:45
  • 2
    \$\begingroup\$ When a char is signed and has a value in the range [CHAR_MIN...-1], it certainly originated as an unsigned char from some function like fgetc(), etc. Casting it back to unsigned char is sensible. The assert() is an OK alternative. It really all depends on coding goals for values outside [0...CHAR_MAX]. The cast is a minimal defined solution. \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 15:04
  • \$\begingroup\$ The cast is to avoid UB: With <ctype.h>, "In all cases the argument is an int, the value of which shall be representable as an unsigned char or shall equal the value of the macro EOF. If the argument has any other value, the behavior is undefined." C11 7.4 1 \$\endgroup\$ – chux - Reinstate Monica Feb 16 '18 at 15:06
2
\$\begingroup\$

Make the problem statement more specific and explicit. Since the question title doesn't match description in the post, I'm wondering if you've got a clear enough idea of what you want.

Do you care about ASCII or some other subset of Unicode? Which encoding(s) do you want to support? Do you want the same behavior regardless of locale?

What about punctuation that separates words? (e.g., should the h in i said, "hello." be capitalized because it's the first letter of a word even though it's not preceded by a space?)

Create a set of test cases so you can quickly check if a change you make causes a regression.

int main() {
    assert(strcmp("", capitalize("")) == 0);
    assert(strcmp("Abc", capitalize("abc")) == 0);
    assert(strcmp("Hello World", capitalize("hello world")) == 0);
    assert(strcmp("  Go  For  It  ", capitalize("  go  for  it  ")) == 0);
    assert(strcmp("(Be Mine)", capitalize("(be mine)")) == 0);
    // etc.
    return 0;
}

Now you can experiment to find the clearest, fastest way to implement what you want.

\$\endgroup\$
4
  • \$\begingroup\$ Yes, it's a great idea to have a test suite. My preference is slightly more work - a test function that allows main() to keep going after a failure, and shows all the failing tests - that way, I can quickly undo a change that causes 50% of them to fail. That looks like int main() { return check("", "") + check("abc", "Abc") + ... ; }. \$\endgroup\$ – Toby Speight Feb 16 '18 at 8:07
  • 1
    \$\begingroup\$ There is a problem here - capitalize() requires a modifiable string, so you can't pass a string literal like that. \$\endgroup\$ – Toby Speight Feb 16 '18 at 8:19
  • 1
    \$\begingroup\$ @Toby Speight: That gets to my point about making the problem statement more explicit. If you want to handle something more than ASCII or other simple character set, you can't always do it in place. Capitalizing a ligature or an accented character can mean that you no longer have a 1:1 ratio between the number of before and after chars. \$\endgroup\$ – Adrian McCarthy Feb 16 '18 at 21:29
  • \$\begingroup\$ Yes, I should have realised the implied change to the function prototype (particularly as you obviously have a different return type!). \$\endgroup\$ – Toby Speight Feb 19 '18 at 9:39
1
\$\begingroup\$

Two things came to my mind:

  1. The task of finding the first non-whitespace character could be solved using strspn, which is not only shorter but might also be useful in case you decide to consider e.g. tab characters as whitespace, too.

  2. Depending on your compiler optimisations (in particular, whether your compiler can optimise tail-recursive functions), you could consider a recursive definition which finds the first non-whitespace, (tries to) upper case it and then processes the remainder of the string.

void capitalize_string(char *s) {
    if (!*s)
        return;
    s += strspn(s, " ");
    *s = toupper(*s);
    capitalize_string(++s);
}
\$\endgroup\$

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.