26
\$\begingroup\$

I've built a C decoder program. The length of an encoded message will be given and the message itself in the following line. All the characters of the message will be in uppercase letters. The task is to print out the decoded message.

Encoding: A->B, B->C...Y->Z, Z->A (well, you get the idea)

#include<stdio.h>

main()
{
    int size;
    scanf("%d", &size);

    char str[size];
    scanf("%s", str);

    for (int i=0; i<size; i++)
    {
        if (str[i]!='Z')
        {
            str[i] -= 1;
        }

        else
        {
            str[i] -= 25;
        }

        printf("%c", str[i]);
    }

    return 0;
}

Is this efficient enough? Could this be done in a simpler and more efficient way? Also, should I use gets() instead of scanf() to take the string as input?

Note that some of the things in my code are not valid C (e.g. not using int() before main(), variable declaration within loop conditional statement). But, my compiler ignores them. I'm a lazy person; I like to type less. I'm well-aware of the fact, nonetheless.

\$\endgroup\$
  • 3
    \$\begingroup\$ @πάνταῥεῖ The code does work in C99. \$\endgroup\$ – 200_success Jan 1 '17 at 21:31
  • 9
    \$\begingroup\$ What should I do when someone answers my question? \$\endgroup\$ – t3chb0t Jan 2 '17 at 12:29
  • 9
    \$\begingroup\$ Please stop editig the code. The edit invalidates the answers. \$\endgroup\$ – t3chb0t Jan 2 '17 at 12:30
  • 4
    \$\begingroup\$ Premature optimization is the root of all evil. Learn the algorithms and see how they work, how fast they work and why. Learn data structures. Then try applying these to your problems, but be aware that you only need to optimize where it is important. The answer to the question "Is it efficient enough" is "How efficient do you need it to be?". You could have an O(n^2) algorithm in your game and still work perfectly well, because we have fast PCs and algorithm would operate on small data. You could have O(n log(n)) and it would be too slow. Profile, then optimize. Not the other way around. \$\endgroup\$ – MatthewRock Jan 2 '17 at 12:30
  • 6
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Jan 2 '17 at 19:14
76
\$\begingroup\$

That's not a bad program, despite the number of suggestions I'm about to make. I do recognize you're a learner, and a young learner at that.

There are several levels at which we can analyze this program. One is checking the current implementation. Another is considering whether it is portable. We can question whether the interface is good — should humans be made to count? And there are alternative algorithms that could be used.

Some of the points I'm about to make are related to style. Although you can write programs in C in all sorts of ways, some of them are easier to read than others. What you show is not bad, but it isn't wholly consistent (and consistency is very important — and hard!).

Analyzing the current implementation — line by line.

#include<stdio.h>

Generally, put a space between #include and the header name, whether a standard header like <stdio.h> or your own header like "caesar.h".

main()

You should always specify the return type of every function, including main(). You're using either C99 or C11, so you are required to specify the return type. (The oldest version of the standard, C90, wasn't quite so fussy.). Further, the return type of main() should be int, though if you work with Microsoft compilers, they allow void too. The standard is quite clear; int is expected. It's often a good idea to say explicitly 'no command line arguments' by writing int main(void), but in practice, int main() also works fine almost all the time. (You have to be doing weird things for it to matter.)

{
    int size;
    scanf("%d", &size);

One of the painful lessons you'll learn coding C is that a lot of your effort is spent error checking. In particular, it is important to check input functions because they're one of the places where things can go wrong and have bad consequences on the rest of the program. The scanf() function returns the number of successful conversions; it can also return 0 indicating no successful conversion, and EOF indicating that there wasn't any data to read. You should also check that the input value is plausible: negative numbers, zero, even one are dubious, and so are huge numbers (e.g. more than 1024).

    char str[size];

This is a VLA — variable length array. They're very useful and have been a part of C since the C99 standard (though technically they're an optional feature in C11 — they were mandatory in C99). You've allocated enough space for size characters, but strings are terminated with a null byte, '\0', and you need to allow space for that. You should probably use char str[size+1];.

    scanf("%s", str);

Again, you should check that you got some data read. Note that with "%s", scanf() first skips any white space (blanks, tabs, newlines) and then reads one word — a sequence of non-blanks. You've not limited the size of the input. If the user said 10 characters but typed 20 characters before the newline or first blank or tab, you'd have problems. If the array size was fixed at, say, 1024 bytes in total, you could use "%1023s" to limit the input to 1023 non-blanks and the terminating null byte. With a variable length array, it's harder. (This is a common oversight in programs, even those by people with lots of experience.)

    for (int i=0; i<size; i++)

This loop is fine, except that many people prefer a bit more space around the operators. What you've written is self-consistent; that's good.

    {
        if (str[i]!='Z'){
            str[i] -= 1;
        }

You're assuming that the user is obedient and does exactly what you want. Unfortunately, users are seldom obedient and rarely do exactly what you want. If the user types 'abracadabra' instead of 'ABRACADABRA' as you expect, or if they type '@Wonderful2CU', you are not going to get the result you expect. You can handle this in various ways. The simple one, which you've currently chosen, is to ignore the issue — it is sometimes termed GIGO: Garbage In, Garbage Out. You could decide that you'll convert lower-case letters to upper-case and then decode them. You could decide to not touch non-letters. You could decide to complain about non-letters. On the whole, it would probably be best to handle lower-case like upper-case and not to change non-letters, but you might decide differently.

Many people would put a space before the {. Others (myself included) would put the { on the next line, like you did after the else below. Here is a case of inconsistency. Either you should use 1TBS (One True Brace Style), which is more or less what you're using in the if, or you should use Allman style, which is more or less what you're using in the else. See Wikipedia on Indent Style for more information (and many more styles).

        else
        {
            str[i] -= 25;
        }

You could simply translate 'Z' to 'A', rather than subtracting a magic number — str[i] = 'A'; would work well.

        printf("%c", str[i]);
    }

These lines are fine. However, it is good practice to end lines of output with a newline. You could sensibly add putchar('\n'); to add a newline.

    return 0;
}

I like to see the explicit return 0; at the end of main(); there are others who aren't convinced. With C99 and later, if you omit the explicit return 0;, then if the main() function — and only the main() function; it doesn't apply to any other functions — 'falls off the end' without any return, it is equivalent to doing return 0;.

Oops!

One other problem, pointed out by NowIGetToLearnWhatAHeadIs in comments is that your decoding steps are not an exact reverse of your encoding steps.

Original: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Encoded:  BCDEFGHIJKLMNOPQRSTUVWXYZA
Decoded:  ABCDEFGHIJKLMNOPQRSTUVWXA@

Minor cheating here; there was also a stray character after the @ because of the issues with string length.

Clearly, the decoded information is not the same as the original. Instead of Z being special, it is A that is special; we need to subtract 1 from everything else and either add 25 or map to Z when the letter is A.

Revising the current implementation

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

int main(void)
{
    int size;
    if (scanf("%d", &size) != 1)
    {
        fprintf(stderr, "Failed to read an integer\n");
        return 1;
    }
    if (size < 2 || size > 1024)
    {
        fprintf(stderr, "Size %d is not in the range 2..1024\n", size);
        return 1;
    }

    char str[size + 1];
    char fmt[10];
    snprintf(fmt, sizeof(fmt), "%%%ds", size);

    if (scanf(fmt, str) != 1)
    {
        fprintf(stderr, "Failed to read a string\n");
        return 1;
    }

    for (int i = 0; i < size; i++)
    {
        if (toupper((unsigned char)str[i]) == 'A')
        {
            str[i] = 'Z';
        }
        else if (isalpha((unsigned char)str[i]))
        {
            str[i] -= 1;
        }
        printf("%c", str[i]);
    }
    putchar('\n');

    return 0;
}

I used #include <ctype.h> to provide macros isalpha() and toupper(). One mildly irksome problem is that plain char can be a signed or unsigned type, and the macros from <ctype.h> expect an unsigned char converted to an int. Putting the (unsigned char) cast into those calls protects you from the sadistic user who types à or ÿ into your program. (There is more to handling accented characters than that, but it is an adequate safety precaution for now.)

Note that this 'decodes' Aa to ZZ; that can be fixed if it matters to you.

I also use snprintf() to create an appropriate format string to ensure that the buffer won't be overflowed. If the size given is 100, it generates %100s (which is the correct size to use since the array is 101 characters long — the difference by one is a nuisance).

Portability

You can skip this section if you wish — it matters to people like me who have to make the software they write work on lots of different machines. If you only have one machine type to work with, you can largely ignore it.

The original code used -= 25 and -= 1 to map the characters. As was noted in the comments, this assumes that the character code for Z is 25 larger than the character code for A. Now, in practice, that is valid for most of the character sets used in the world — and, in particular, it is accurate for Unicode. However, there are machines — IBM mainframes for example — where the code set used is called EBCDIC, where the code for A is 193, for I is 201, for J is 209, for R is 217, for S is 226, and for Z is 233. There are gaps in those ranges which cause confusion; the gap between Z and A is 40, not 25 as you might expect.

If you decided to worry about it, you should devise an alternative way of mapping the characters.

At some point, you'll note that the original Caesar cipher used a shift of 3, not 1, and you'd upgrade your code to handle any shift between 1 and 25 (there's not much point in shifting by 0 or 26; nothing changes). That complicates the checking for wraparound at the ends of the alphabet. Again, that isn't an immediate problem.

Interface design

You currently require the human to know how long the message is. I don't know about you, but I know I don't know how many characters are in the first sentence of this paragraph. Sure, I could count, but computers are much better at counting. You can work around this problem in various ways. One simple one is to provide a fixed size but large buffer (e.g. 1024 bytes) and simply read the data into that. You would probably use the fgets() function for the job instead of scanf(). Then you might read more than one line of input in a run of the program, too, using a loop. The revised program will look a bit simpler:

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

int main(void)
{
    char str[1024];

    while (fgets(str, sizeof(str), stdin) != 0)
    {
        int size = strlen(str);    
        for (int i = 0; i < size; i++)
        {
            if (toupper((unsigned char)str[i]) == 'A')
            {
                str[i] = 'Z';
            }
            else if (isalpha((unsigned char)str[i]))
            {
                str[i] -= 1;
            }
            printf("%c", str[i]);
        }
    }

    return 0;
}

This simply reads standard input until it encounters EOF. You might run your program as ./decode-caesar < encoded.txt, or you might type your encoded message by hand, in which case you'd indicate EOF by typing a control character at the start of a line — it would be Control-D on Unix systems or Control-Z on Windows systems (unless you've changed the default setting for EOF on Unix).

Note that fgets() preserves newlines and the revised algorithm doesn't change newlines so there's no need to print an extra newline at the end of the output.

Alternative designs

The programs so far have read a whole word or line at a time, and then processed each character in turn. Another way of doing it would be to simply read and process each character in turn. This is simpler still:

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

int main(void)
{
    int c;

    while ((c = getchar()) != EOF)
    {
        if (toupper(c) == 'A')
            c = 'Z';
        else if (isalpha(c))
            c -= 1;
        putchar(c);
    }

    return 0;
}

Note that I used int c; — that's because getchar() returns an int, not just a char. It has to return every possible char value and a separate EOF value, which means that it can't return just a char; it must return an int. A side-effect of that is that all characters in c will be in the range 0..255 (positive) because getchar() returns the character value converted to unsigned char. This means that it is safe to drop the casts in the calls to toupper and isalpha.

I've opted not to use braces around the single-line actions after the if and else clause. This is another style issue. There are those who argue that you should always use braces after if or else (and there are languages such as Perl that insist on braces there), partly on the grounds that if you ever add another statement to the else clause, you might forget to add the necessary braces. I'm not convinced by that argument, but maybe some programmers are careless enough that 'always use braces' really helps prevent bugs.

Wrapping up

There are lots of little details that could be explained and discussed. There are still caveats that could be discussed. However, they're minor enough that you don't need to worry about them at this stage, I think.

You asked about efficiency. The code you wrote is reasonably efficient. There are no gross inefficiencies in it. It is clean, and that is often more important than efficient. Before worrying about efficiency, measure whether there is a performance problem. With this code, there won't be a performance problem — none of the programs is inefficient — for the plausible sizes of input.

If you wanted to be more efficient, you'd print the whole word or line in one operation, rather than using printf("%c", str[i]) to print each character one at a time. You could replace printf("%c", str[i]) with putchar(str[i]) and it would be 'more efficient', but whether you'd be able to measure it is more debatable.

Michael Jackson (no, not the pop-star — but maybe he's before your time) had two rules for optimization (improving the efficiency of code):

  • First rule of optimization: Don't do it.
  • Second rule of optimization (for experts only): Don't do it yet.

You also ask about using gets(). You should never use gets()! There is no safe way to use gets() because you cannot prevent buffer overflows when you do. You should use fgets() by default, or getline() if you work on a POSIX-based system. Note that both those retain the newline, whereas gets() removes it. One good idiom for removing a trailing newline from fgets(buffer, sizeof(buffer), stdin) is buffer[strcspn(buffer, "\n")] = '\0'; which works correctly whether there's a newline in the buffer or not. With getline(), it tells you how long the string is so you can use that to remove the newline (though there's an outside chance that the file doesn't end with a newline, so the last line read won't have a newline — which is irksome).

Testing

Oh, and it is important to test code. I didn't run your code (or my code) on any data until @NowIGetToLearnWhatAHeadIs pointed out the error in the decoding. That was lazy of me — copying your mistake into my code. Testing is very important!

Fixing the mapping of 'a' to 'Z'

I've decided I'm not keen on the sloppy way my code maps 'a' to 'Z'. It is easy enough to fix. This variant of the third program handles it. It contains an assertion to ensure that the code is not used successfully on an EBCDIC machine.

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

int main(void)
{
    int c;

    assert('Z' - 'A' == 25 && 'z' - 'a' == 25);

    while ((c = getchar()) != EOF)
    {
        if (toupper(c) == 'A')
            c += 25;
        else if (isalpha(c))
            c -= 1;
        putchar(c);
    }

    return 0;
}

Sample input:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
09@?

Sample output:

ZABCDEFGHIJKLMNOPQRSTUVWXY
zabcdefghijklmnopqrstuvwxy
09@?

That's cleaner!

Using C11, you could use a 'static assert' instead of a run-time assertion. This would prevent the program compiling:

static_assert('Z' - 'A' == 25 && 'z' - 'a' == 25,
              "Alphabet should be contiguous but isn't");
\$\endgroup\$
  • \$\begingroup\$ Your implementations decode "BZ" to "AA". For example, ideone.com/Oh93oE. This seems wrong. \$\endgroup\$ – Brian Moths Jan 2 '17 at 1:38
  • \$\begingroup\$ @NowIGetToLearnWhatAHeadIs : the decoding is supposed to be the same as in the question. I'll test compile and check, but I think it would be the same with the original code. Thanks for the heads up. \$\endgroup\$ – Jonathan Leffler Jan 2 '17 at 1:42
  • \$\begingroup\$ I think that is an error in Soha Farhin Pine's code though. I think the decoding algorithm is supposed to invert the encoding algorithm described in the question. Specifically, I think B is supposed to decode to A, A is supposed to decode to Z and Z is supposed to decode to Y (since A encodes to B, Y encodes to Z, and Z encodes to A). \$\endgroup\$ – Brian Moths Jan 2 '17 at 1:46
  • 2
    \$\begingroup\$ @JonathanLeffler Really, really helpful! Thank you a gazillion times! Some of the things you pointed out (e.g. the formatting, or invalid C) were either typos or written because my compiler ignores them. I've not yet finished---nearly at the end---and I have to say, this is a fabulous answer! It must've taken you a lot of time and effort to type all this. I'm really grateful to you for your help. \$\endgroup\$ – Soha Farhin Pine Jan 2 '17 at 10:17
  • 1
    \$\begingroup\$ Maybe it should be "…which cause confusion" (meaning confusion to those who think the alphabet is always contiguous). The ranges were related to 9 columns on a punched card. It was not intended to imply that IBM went out of its way to cause chaos. Indeed, it could be argued that ASCII is the 'new kid on the block' and caused the chaos. \$\endgroup\$ – Jonathan Leffler Jan 3 '17 at 16:45
0
\$\begingroup\$

Here is an implementation of the current algorithm with appropriate error checking.

However, this algorithm seems to not match the content of the question as it increments the char value when the question indicates a need to decrement the value.

#include<stdio.h> // scanf(), perror(), fprintf() sprintf()
// need following header for error handling
#include <stdlib.h>  // exit(), EXIT_FAILRUE
#include <string.h>  // strlen()
#include <ctype.h>   // toupper(), isalpha()

// not a valid function signature: main()
int main( void )
{
//poor choice for a number that will never be <0    int size;
    size_t size;
//always check the returned value to assure the operation was successful    scanf("%d", &size);
    if( 1 != scanf( "%lu", &size ) )
    {
        perror( "scanf for string length failed" );
        exit( EXIT_FAILURE );
    }

    // implied else, scanf successful

// need to allow for NUL termination character    char str[size];
    char str[ size+1];
// always include a MAX CHARACTERS modifier to avoid buffer overflow    scanf("%s", str);
// note: this input will stop early if a space or newline is encountered
    char format[20] = {'\0'};
    sprintf( format, "%c%lu%c", '%', size, 's' );
    if( 1 != scanf( format, str ) )
    {
        perror( "scanf for string failed" );
        exit( EXIT_FAILURE );
    }

    // implied else, scanf successful

// never trust the user
    if( strlen( str ) != size )
    { // then wrong number of chars entered
        fprintf( stderr, "Num chars entered %lu does not match expected %lu chars\n",
                strlen(str),
                size );
        exit( EXIT_FAILURE );
    }

    // implied else, expected number of characters entered

//    for (int i=0; i<size; i++)
    for( size_t i=0; i<size; i++ )
    {
        // validate the input from the user
        if( !(isalpha(str[i])) || (toupper(str[i]) != str[i]) )
        { // invalid char entered
            fprintf( stderr, "invalid char %c entered, must all be upper case alpha\n", str[i] );
            exit(EXIT_FAILURE );
        }

        // implied else, valid character

        if (str[i]!='Z')
        { // any upper case char except 'Z'
// avoid implicit conversions str[i] -= 1;
            str[i]--;
        }

        else
        { // wrap around any 'Z'
            //str[i] -= 25;
            str[i] = 'A';
        }

        printf("%c", str[i]);
    } // end for

    return 0;
} // end function: main

However, calls to scanf() and printf() are expensive. Calling getchar() in a loop would be much faster for the line of data to be 'encoded' and calls to putc() inside that loop would be much faster.

\$\endgroup\$
  • \$\begingroup\$ I observe that using "%lu" instead of "%zu" is not strictly correct; the z modifier is correct for size_t. I also think it would be worth checking the non-negative value that's read for plausibility. The code will crash if the user types -1 as the size (out of stack space — and yes, you can type -1 for an unsigned integer). \$\endgroup\$ – Jonathan Leffler Jan 3 '17 at 15:07
  • \$\begingroup\$ Note that if your compiler provides a plain char type that is signed (which is allowed by the standard; so is unsigned), and if the user types accented characters, then the value stored in str[i] converted to an int may be negative. The <ctype.h> functions/macros expected either a plain char converted to unsigned char (hence a positive number in the range 0..UCHAR_MAX) or EOF (negative; usually, but not necessarily, -1). Calling isalpha(str[i]) on such a platform leads to undefined behaviour. A cast is secure (isalpha((unsigned char)str[i])) even though unpleasant. \$\endgroup\$ – Jonathan Leffler Jan 3 '17 at 15:40
  • \$\begingroup\$ @JonathanLeffler, you might not have noticed the statement at the beginning of this answer indicating that the answer was just improvements to the current code. Note: a zu modifier will allow a negative value to be entered while a lu will always treat the entered value as positive. \$\endgroup\$ – user3629249 Jan 5 '17 at 9:08
-2
\$\begingroup\$

This reminds me of some old times---doing programming practice and contest with my classmates and colleagues.

First of all, main() must return an int value. Some compilers will also accept void.

int main()

Then you cannot use a variable size array, since it will take more time to compile the program. In your case, you should do:

#include <memory>

....
//char str[size];
char* str = malloc(size + 1);  // also make sure size > 0, and +1 for NULL terminates a string

Inside the for loop, if you are sure all input characters range from A to Z...

str[i] = (str[i] - 'A' + 25) % 26 + 'A';

In the end, don't forget to free the string:

free(str);

I did not try compiling all this, so there might be any error.

\$\endgroup\$
  • 7
    \$\begingroup\$ How archaic a version of C do you use if variable length arrays are not available to you? \$\endgroup\$ – Jonathan Leffler Jan 1 '17 at 21:04
  • 5
    \$\begingroup\$ […continuation…] . I'm not convinced that a malloc() solution is the best alternative — I'd go with a fixed large-size (1024 or even 4096) array rather than go with malloc(), especially when the OP is a self-identified youngster. Yes, they'll learn malloc() soon enough (next week probably, if not this week), but it complicates things a bit unnecessarily, especially if you error check the allocation as you should. \$\endgroup\$ – Jonathan Leffler Jan 1 '17 at 23:18
  • 1
    \$\begingroup\$ My fault then, I did not learn C99 before switch to C++, then working in CPP and C mix-up environment, mostly in windows. BTW, to use big size array in stack is not a good idea. \$\endgroup\$ – Tiger Hwang Jan 1 '17 at 23:33
  • 4
    \$\begingroup\$ An array of 1 KiB is not a big stack allocation on any desktop machine these days. If you're working in an embedded environment, or perhaps if you're working with threads, some caution is required, but for single-threaded programs, even Windows provides 1 MiB of stack space by default; it is usually 8 MiB on Unix-based systems. Using just 1 KiB of space is not a serious memory stressor on either of those. \$\endgroup\$ – Jonathan Leffler Jan 2 '17 at 2:20
  • 1
    \$\begingroup\$ I also read this specification, and I think it's better not to use it. Maybe it's easier for beginner, but if you get use to this, it can cause hidden problem in bigger project and difficult to find out. I had a case that someone declare a buffer in some functions, each one not very big, but if they are calling in order, writing to a variable in stack modified another variable. This must be caused by stack overflow, it take me almost one week to figure it out and fix. \$\endgroup\$ – Tiger Hwang Jan 2 '17 at 9:25

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.