PDA

View Full Version : [C programming] reverse string




gotenks05
Nov 4, 2009, 11:57 AM
Alright, I'm having another problem in C. I want to make a program that takes a string inputted by the user and reverses it. I got it to work, but it displays gibberish at the start, which I can't get rid of.

Here is the function prototype:

void reverse(char string[], int size);

Here is the function definition:

#include <stdio.h>

void reverse(char string[], int size)
{
int count = size -1;

for (count; count >= 0; count--)
{

if (string[count] >= 33 && string[count] < 123| string[count] >= 65 && string[count] < 123 | string[count] >= 97 && string[count] < 123)
{
printf("%c", string[count]);
}
}

printf("\n");
}

and here is the source:

#include <stdio.h>
#define Size 700
int main()
{
char sentence[Size];
int items = Size;

printf("Enter a string: ");

fgets(sentence, Size, stdin);

reverse(sentence, items);

return 0;
}

I defined a variable to 700, because that will accommodate most strings, since I have no idea how long the actual string a user inputs will be exactly. Both putchar and printf give me gibberish.



autorelease
Nov 4, 2009, 12:20 PM
You're not just printing the bytes of the string in reverse order; you're printing the bytes of the entire 700-byte buffer in reverse order.

I see that you've tried to compensate for this by trying to print only characters with certain ASCII values. However, when your program starts, your 700-byte buffer might not be all zeros; it'll probably be filled with random values, some of which will probably be letters. These gibberish values don't get overwritten by fgets(), so they'll be printed in your reverse() function.

So you shouldn't be passing 700 as the size parameter to reverse(). Use the actual length of the string the user entered. This can be computed with the strlen() function.

Also, technically, you're not reversing the string, you're printing the letters in reverse order. The characters in the string haven't moved anywhere. Actually reversing the bytes a string is a good exercise; do it without making a copy of the string for bonus points! ;-)

gotenks05
Nov 4, 2009, 12:40 PM
You're not just printing the bytes of the string in reverse order; you're printing the bytes of the entire 700-byte buffer in reverse order.

I see that you've tried to compensate for this by trying to print only characters with certain ASCII values. However, when your program starts, your 700-byte buffer might not be all zeros; it'll probably be filled with random values, some of which will probably be letters. These gibberish values don't get overwritten by fgets(), so they'll be printed in your reverse() function.

So you shouldn't be passing 700 as the size parameter to reverse(). Use the actual length of the string the user entered. This can be computed with the strlen() function.

Also, technically, you're not reversing the string, you're printing the letters in reverse order. The characters in the string haven't moved anywhere. Actually reversing the bytes a string is a good exercise; do it without making a copy of the string for bonus points! ;-)

Thanks that helped.

kylos
Nov 4, 2009, 04:44 PM
Also, your conditional is not doing what you think it is. It's simply accepting all characters between 33 (inclusive) and 123. I'd recommend checking for yourself to see why it's not doing what you think it is. However, following autorelease's advice, you won't even need this test to print valid data.

lloyddean
Nov 4, 2009, 05:21 PM
Since he's implied a solution but not posted it I'll throw this one down for future readers.

Assuming C99 and 'char string[]' is NOT a pointer to a string constant -


void reverse(char string[])
{
char* left = &string[0]-1;
char* right = &string[strlen(string)];
char temp;
while ( ++left < --right )
{
temp = *left;
*left = *right;
*right = temp;
}
}

gnasher729
Nov 4, 2009, 07:34 PM
Since he's implied a solution but not posted it I'll throw this one down for future readers.

Assuming C99 and 'char string[]' is NOT a pointer to a string constant -


void reverse(char string[])
{
char c;
for ( int i = 0; i < ((strlen(string)-1) / 2); i++ )
{
c = string[i];
string[i] = string[(strlen(string)-1) - i];
string[(strlen(string)-1) - i] = c;
}
}


Question: What happens when you pass in a string with a million characters?
Question: What happens when you pass in a string with 2, 4, 6 or 8 characters?

JangoFett124
Nov 4, 2009, 08:04 PM
Since he's implied a solution but not posted it I'll throw this one down for future readers.

Assuming C99 and 'char string[]' is NOT a pointer to a string constant -


void reverse(char string[])
{
char c;
for ( int i = 0; i < ((strlen(string)-1) / 2); i++ )
{
c = string[i];
string[i] = string[(strlen(string)-1) - i];
string[(strlen(string)-1) - i] = c;
}
}


Haven't tested it, but this seems more like it:


void reverse(char string[])
{
for (int low = 0, high = strlen(string)-1; low < high; ++low, --high)
{
const char temp = string[low];
string[low] = string[high];
string[high] = temp;
}
}


(I do feel a bit dirty doing the homework from someone that doesn't even seem all that appreciative looking at their post history. Hopefully tests have more weight than these assignments.)

lloyddean
Nov 4, 2009, 09:17 PM
Whoops you're right gnasher729.

kylos
Nov 5, 2009, 10:47 AM
lloyddean, it doesn't matter for efficiency, and it shouldn't introduce any bugs, but you don't have to execute your loop when low and high are equal.

lee1210
Nov 5, 2009, 10:54 AM
lloyddean, it doesn't matter for efficiency, and it shouldn't introduce any bugs, but you don't have to execute your loop when low and high are equal.

It would affect it if you changed your swap to the XOR trick instead of using a temp variable for swapping. If you use that trick on the same memory address, you end up zero'ing it.

-Lee

autorelease
Nov 5, 2009, 01:43 PM
It would affect it if you changed your swap to the XOR trick instead of using a temp variable for swapping. If you use that trick on the same memory address, you end up zero'ing it.

-Lee

The XOR trick is clever but you shouldn't use it unless you're an 8-bit assembler jockey. On modern hardware, the standard swap can be pipelined better, and the compiler might even recognize the swap and turn it into an exchange instruction.

Here's my solution to the in-place swap I suggested. JangoFett and lloyddean pretty much had it right, I just prefer for loops :p

void reverse(char *str)
{
char *front, *back;
for (front = str, back = str+strlen(str)-1; front < back; front++, back--)
{
char tmp = *front;
*front = *back;
*back = tmp;
}
}


This function can also be modified to test whether or not a string is a palindrome. Any takers? :)

lee1210
Nov 5, 2009, 02:20 PM
The XOR trick is clever but you shouldn't use it unless you're an 8-bit assembler jockey. On modern hardware, the standard swap can be pipelined better, and the compiler might even recognize the swap and turn it into an exchange instruction.

Here's my solution to the in-place swap I suggested. JangoFett and lloyddean pretty much had it right, I just prefer for loops :p

void reverse(char *str)
{
char *front, *back;
for (front = str, back = str+strlen(str)-1; front < back; front++, back--)
{
char tmp = *front;
*front = *back;
*back = tmp;
}
}


This function can also be modified to test whether or not a string is a palindrome. Any takers? :)


void reverse(char *str)
{
char *front, *back;
int isPalindrome = 1;
for (front = str, back = str+strlen(str)-1; front < back; front++, back--)
{
if(*front != *back) {
char tmp = *front;
isPalindrome = 0;
*front = *back;
*back = tmp;
}
}
if(isPalindrome == 1) printf("Found a palindrome! Huzzah!\n");
}


Also, i mentioned the XOR trick because it was one of the first things that really pulled me into CS. When my HS CS teacher showed it to us, it blew my mind. It is totally useless for modern programming, i just think it's interesting. Another a-ha moment was when a prof or TA in college said that you should ensure you check that the addresses aren't equal when passed into an XOR swap subroutine, or you'll lose your value.

-Lee

lloyddean
Nov 5, 2009, 09:25 PM
The XOR trick is clever but you shouldn't use it unless you're an 8-bit assembler jockey. On modern hardware, the standard swap can be pipelined better, and the compiler might even recognize the swap and turn it into an exchange instruction.


Yes it was quite useful back in the mid 70's for game programming on the very small memory systems of the day. And still useful in the very small embedded throw away processors.

But, I think it's best left as a curiosity on todays desktop systems and game consoles.