8
\$\begingroup\$

I have been learning C with K&R Book 2nd Ed. So far I have completed quite a few exercises.

For the following exercise (Chapter 3, Ex-3.3):

Exercise 3-3. Write a function expand(s1, s2) that expands shorthand notations like a-z in the string s1 into the equivalent complete list abc...xyz in s2. Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a-z0-9 and -a-z. Arrange that a leading or trailing - is taken literally.

I have written this solution. I would like to know how to improve it.

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

#define MAXLINE 1024

int get_line(char line[], int maxline);
void expand(const char s1[], char s2[]);
int match(int start, int end);

int
main(void)
{
    char s1[MAXLINE];
    char s2[MAXLINE];

    while (get_line(s1, MAXLINE) > 0) {
        expand(s1, s2);
        printf("%s", s2);
    }
    return (0);
}

/**
 *  Here I have tried to write a loop equivalent to the loop seen
 *  previously in chapter 1. (without using && and ||,
 *  as specified in chapter 2 of the book, exercise 2.2).
 *
 *  for (i = 0; i < lim-1 && (c = getchar()) != EOF && c != '\n'; ++i)
 *      ...
 **/
int
get_line(char s[], int lim)
{
    int c, i;

    i = 0;
    while (--lim > 0) {
        c = getchar();
        if (c == EOF)
            break;
        if (c == '\n')
            break;
        s[i++] = c;
    }
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return (i);
}


void
expand(const char s1[], char s2[])
{
    int i, j, ch;

    for (i = j = 0; (ch = s1[i++]) != '\0'; ) {
        if (s1[i] == '-' && match(s1[i-1], s1[i+1])) {
            for (i++; ch < s1[i]; ) {
                s2[j++] = ch++;
            }
        } else
            s2[j++] = ch;
    }
    s2[j] = '\0';
}


int
match(int start, int end)
{
    return ((isdigit(start) && isdigit(end)) ||
        (islower(start) && islower(end)) ||
        (isupper(start) && isupper(end)));
}

these are a few of the tests that I did with the program that I've written.

a-z
abcdefghijklmnopqrstuvwxyz

a-b-c
abc

a-z0-9
abcdefghijklmnopqrstuvwxyz0123456789

-a-z
-abcdefghijklmnopqrstuvwxyz

A-Z
ABCDEFGHIJKLMNOPQRSTUVWXYZ

0-9
0123456789

-A-D
-ABCD

0-7
01234567

a-h
abcdefgh
\$\endgroup\$
2
  • \$\begingroup\$ What output expected with input like "a-c-E", "a-c-a"? Loop logic appears flawed. \$\endgroup\$ Commented Sep 2, 2022 at 14:23
  • \$\begingroup\$ @chux-ReinstateMonica I didn't take those inputs into consideration, now that you mention it.. and I'm not quite sure what the expected results would be for those inputs. but perhaps, the outputs I would expect would be: "abc-E" Y "abc-a", maybe? \$\endgroup\$ Commented Sep 2, 2022 at 14:38

3 Answers 3

6
\$\begingroup\$

General Observations

The code generally looks good.

An experienced C programmer would probably use pointers rather than indexing through the array.

When unit testing code such as the functions int match(int start, int end) and void expand(const char s1[], char s2[]) it is generally better to create the strings to be tested in the code rather than reading in the strings, you should also prepare strings that are the expected output of the functions. Automated tests are better because they are reproducible.

One of the problems with using the K&R book is that it predates the introduction of the bool type into standard C. If I was writing this code I would include stdbool.h and have match return a bool instead of an int.

On Windows 10 using Visual Studio 2022 there seems to be a bug, the program never terminates when a new line is entered without any text.

Prefer C Standard Library Functions

The code includes the function get_line(char s[], int lim), however there are standard C library functions that can perform this operation, one is char fgets(char str, int count, FILE *stream). Using library functions is generally preferred over writing your own function because it doesn't need debugging and it may perform better than the function you write.

Code Organization

Function prototypes are very useful in large programs that contain multiple source files, and that in case they will be in header files. In a single file program like this it is better to put the main() function at the bottom of the file and all the functions that get used in the proper order above main(). Keep in mind that every line of code written is another line of code where a bug can crawl into the code.

Variable Names

The variable names s and lim are not as descriptive as they could be, for instance I might rename lib to be buffer_size.

Alternate Implementation

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

#define MAXLINE 1024

bool
match(int start, int end)
{
    return ((isdigit(start) && isdigit(end)) ||
        (islower(start) && islower(end)) ||
        (isupper(start) && isupper(end)));
}

void
expand(const char s1[], char s2[])
{
    int i, j, ch;

    for (i = j = 0; (ch = s1[i++]) != '\0'; ) {
        if (s1[i] == '-' && match(s1[i - 1], s1[i + 1])) {
            for (i++; ch < s1[i]; ) {
                s2[j++] = ch++;
            }
        }
        else
            s2[j++] = ch;
    }
    s2[j] = '\0';
}


int
main(void)
{
    char s1[MAXLINE];
    char s2[MAXLINE];

    while (strlen(fgets(s1, MAXLINE, stdin)) > 0) {
        expand(s1, s2);
        printf("%s", s2);
    }
    return (0);
}
\$\endgroup\$
12
  • 4
    \$\begingroup\$ "An experienced C programmer would probably use pointers rather than indexing through the array." Maybe that's true, but…why? More importantly, why is it better? If an experienced C programmer does it that way, it's probably because (A) they saw it done that way in K&R, and/or (B) compilers from a long time ago (back when this hypothetical programmer was getting their experience) were better at optimizing code written to iterate using pointers rather than array-indexing. But the latter is no longer true, and the former is hardly a reason to do anything. Indexing is more readable & extensible \$\endgroup\$ Commented Aug 30, 2022 at 3:16
  • \$\begingroup\$ @CodyGray depends on if you can use the optimizer or not, if you can the compiler substitutes in the pointers anyway. \$\endgroup\$
    – pacmaninbw
    Commented Aug 30, 2022 at 3:24
  • 2
    \$\begingroup\$ Why wouldn't you be able to use the optimizer? In general we first try to write the most readable code, then tweak if necessary to resolve actual performance problems. As @CodyGray says, some bad styles may have risen in the days when compilers didn't optimize well. \$\endgroup\$
    – Barmar
    Commented Aug 30, 2022 at 15:59
  • \$\begingroup\$ @Barmar Do you do any embedded programming or hardware i/o? C Optimizer can sometimes cause problems. \$\endgroup\$
    – pacmaninbw
    Commented Aug 30, 2022 at 19:26
  • \$\begingroup\$ return ((isdigit(start) && isdigit(end)) || (islower(start) && islower(end)) || (isupper(start) && isupper(end))); only makes sense if those sub-ranges are continuous. `isdigtis are continuous, the others are continuous in ASCII, but not certainly otherwise. \$\endgroup\$ Commented Sep 2, 2022 at 4:10
5
\$\begingroup\$

Simplifications

This code duplicates some of the loop content:

if (c == '\n')
    s[i++] = c;

We can rearrange the loop, testing for newline after the assignment, to avoid that duplication:

while (--lim > 0) {
    int c = getchar();
    if (c == EOF)
        break;
    s[i++] = (char)c;
    if (c == '\n')
        break;
}
s[i] = '\0';

The parentheses in return (i) are unnecessary. They are harmless, but look odd to a C programmer.


Pointer/index safety

It's good that we pass and use a limit argument when populating s1. But we never pass the size of s2 into expand(), so it's possible to write out of bounds (in general the output string will be at least as long as the input string; an input that looks like a-za-za-z… will produce much longer output).

This is an important lesson for a C programmer to learn, as errors in writing beyond array bounds have been a source of very many security vulnerabilities.

It is possible to write this program without reading a whole line at a time - that would allow the fixed-length buffers to be completely dispensed with, and reduce the possible habitat for bugs.


Character coding issues

You're testing your code on a system whose character coding has contiguous letters (e.g. ASCII). However, C doesn't mandate a particular character coding, and there exist codes, notably EBCDIC, which have discontiguous characters. On such systems, you'll expand a-z into something else (e.g. abcdefghi«»ðýþ±°jklmnopqrªºæ¸Æ¤µ~stuvwxyz when using code-page 37).

C does require that the digits are contiguous, so 0-9 using this method is always safe.

\$\endgroup\$
3
\$\begingroup\$

Small review int get_line(char s[], int lim)

int v. size_t

Use size_t lim to handle forming all strings, even very long ones.

Avoid UB

When lim == 1 (or smaller), code attempts if (c == '\n') s[i++] = c; yet c was never assigned. Better to declare int c = 0; or such. s2[j] = '\0' is not OK with pathologically cases like lim < 1

Pedantic: UB

Avoid UB of --lim when lim = INT_MIN. In general, consider how code reacts to lim <= 0, no matter how foolish it would be to pass that. At least avoid UB.

A quick and dirty preventive measure would use assert(lim > 0 && s != NULL);.


Sample alternative:

// Read a line of user input.
// Stop when not enough room, '\n', end-of-file or input error.
size_t get_line(size_t sz, char s[/* sz */]) {
  // Pedantic: Use unsigned char to avoid subtle problems with negative non-2's complement.
  unsigned char *us = (unsigned char *) s; 

  size_t i = 0;
  while (i + 1 < sz) {
    int c = getchar();
    if (c == EOF) {
      break;
    }
    us[i++] = c;
    if (c == '\n') {
      break;
    }
  }
  if (i < sz) { // Test only useful when sz == 0
    us[i] = '\0';
  }
  return i;
}

Additional code may be needed to well handle rare input errors. Unclear on OP's design goal for that.


OP's loop expand loop has a a flaw/weakness.

When a match is found, say from "a-d", the expand prints the a, b, c on that iteration and the next iteration prints the d. IMO, It would be better to consume all 3 characters of "a-d" and print the 4 the a, b, c, d on that iteration and the next iteration pick up with the text after the "a-d".

\$\endgroup\$
4
  • \$\begingroup\$ Why don't you use fgets instead? \$\endgroup\$ Commented Sep 2, 2022 at 5:32
  • 2
    \$\begingroup\$ @AyxanHaqverdili fgets() is a reasonable alternative. The differences are arcane. fgets() fails to provide a clean way to detect how many null characters were read. It is also limited to INT_MAX size buffer, even though larger buffers are rarely ever needed. fgets() does not null character terminate the buffer when nothing read due to end-of-file. fgets() implementations are dodgy with pathologic size <= 1. \$\endgroup\$ Commented Sep 2, 2022 at 6:12
  • \$\begingroup\$ Yes, you could perhaps implement this function in terms of fgets. The INT_MAX limitation is unlikely to be a problem for this exercise. Also, you can set the very first character to '\0' before calling fgets, so it is always properly terminated. \$\endgroup\$ Commented Sep 2, 2022 at 6:19
  • \$\begingroup\$ @AyxanHaqverdili I am readily familiar how to wrap fgets() to handle many of its short-comings. "you can set the very first character to '\0' before calling fgets, so it is always properly terminated." is insufficient when fgets() returns NULL due to input error as the entire buffer is indeterminate. "If a read error occurs during the operation, the array contents are indeterminate and a null pointer is returned." Better to test the return value and null character terminate if needed. \$\endgroup\$ Commented Sep 2, 2022 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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