?
Solved

Reversing a string

Posted on 2009-02-11
33
Medium Priority
?
918 Views
Last Modified: 2012-05-06
Hello Experts,
i need a small function to reverse a string, it wil be called once from main along with string to be reversed as an argument.  When control comes back in main, string is printed, it should have been reversed.
like :
int main()
{
    char *str;
    gets(str);
    Reverse(str);
    cout<<"Reversed String is " << str ;
}

void Reverse(char *s) //suppose its prototype is given before main.
{
     //function body with recursive calls and ifs etc.
}

Please provide me the body of the Reverse function.


Thanks.
0
Comment
Question by:Gupi
  • 10
  • 9
  • 8
  • +2
33 Comments
 
LVL 29

Expert Comment

by:pepr
ID: 23619524
It seems to be homework, isn't it?
0
 

Author Comment

by:Gupi
ID: 23619570
No Its not homework.
its just my hobby to make such interesting programs in C/C++, Visual Basic, Java etc.
since long i was trying this, but could not do successfully.

please help.
thanks.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:Gupi
ID: 23619583
and Thanks
for the link provided, but none of the functions given there serve my purpose. some are non recursive
one is recursive as :
void StrReverse4(char *str)
{
      if(*str)
      {
            StrReverse4(str+1);
            putchar(*str);
      }
}


but, it too doesnot retrun Reversed String, it just displays on the screen.

0
 
LVL 29

Expert Comment

by:pepr
ID: 23619651
Anyway, there may be many ways to do it. Anyway, none of the solutions in the mentioned codeguru thread is not optimal.

The only recursive solution only outputs the string and does not place the result to the same memory place. The recursiove solution with the requested features needs to define one more function -- the core of the recursion (passing more than one argument to the recursion calls).

The non-recursive solution will always be more efficient. The solution in-situ (using the same place, no memory allocation) based on the for loop needs only n/2 swaps where n is length of the string.

The real life C++ solution would be to create std::string out of the char *. Then the std::reverse algorithm would be used for reversing the content of the string. As this was not the task of the homework, see the C++ solution that returns

C:\tmp\___C++>main.exe
Result: '.gnirts lamron a si sihT'
#include <algorithm>
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    char * sz = "This is a normal string.";
    string s(sz);                   // converted to std::string
    reverse(s.begin(), s.end());
    cout << "Result: '" << s << "'\n";
 
    return 0;    
}

Open in new window

0
 
LVL 29

Expert Comment

by:pepr
ID: 23619664
My correction. The StrReverse3 is the correct one with in-situ reversion.
0
 

Author Comment

by:Gupi
ID: 23621397
Hello experts,
i was coding Reverse(char *str) as given below.
but it is not working well.
Please check.
Thanks.

#include<conio.h>
#include<iostream.h>
#include<string.h>
char* Reverse(char *);
void main()
{
	char *str="Hello" ;
	clrscr();
	str=Reverse(str);
	cout<<"\n Reversed String : "<< str;
getch();
}
 
char * Reverse(char *S)
{
	char *ch, *t;
	cout<<"\n Reversing : "<<S;
 
	//if single char is left, return it, stopping Recursion.
	if(strlen(S)==1)
	{
		cout<<"\nNow Returning : "<<S<<"\n";
		return S ;
	}
	else
	{
		ch[0]=S[0]; //copy first char of S in ch
		// put NULL, making ch a string that
		// ends with null, having one char ch[0] in it.
		ch[1]=NULL ;
		//Reverse remaining part of String.
		t=S+1;
		t=Reverse(t);
		strcat(t,ch) ; //join Reversed String with last char.
		return t;
	}
}

Open in new window

0
 

Author Comment

by:Gupi
ID: 23621708
waiting..
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23622497
>>                 ch[0]=S[0]; //copy first char of S in ch

You haven't yet allocated memory for ch. So, you can't write to it.
0
 

Author Comment

by:Gupi
ID: 23629562
ok. Thanks Infinity08.
it will do it like : ch=(char *) malloc(2);

But, also next line ch[1]=NULL  will cause problem, becaue it will insert NULLs many times in the string.

Please look into.

thanks.
0
 
LVL 29

Expert Comment

by:pepr
ID: 23630813
Resursive solutions may help to get the solution easer based on the kind of idea of how one step should be solved. Technically, the recursive solution hides the existence of a stack (auxiliary memory) and of the loop (the recursion). This means that every recursive solution can be replaced by nonrecursive solution when you introduce a stack and a loop.

Now, the following resursive solution shows the reversed approach -- replacing the loop from the StrReverse3() code by the recursive call of the ReverseCore(). The mental picture is: Get the first character of the string and swap it with the last character of the string. Then do the same with the middle substring (if the middle exist).
#include <iostream>
using namespace std;
 
 
void ReverseCore(char * p1, char * p2)
{
    if (p1 < p2)
    {
        char ch = *p1;
        *p1 = *p2;
        *p2 = ch;
    
        ReverseCore(++p1, --p2);
    }
} 
 
 
void Reverse(char * sz)
{
    ReverseCore(sz, sz+strlen(sz)-1);
}
 
 
int main()
{
    // You often cannot define the sz as...
    // char * sz = "This is a normal string.";
    // as the literals may be stored (by the compiler
    // and linker) in the part of memory that 
    // cannot be modified. You should tell that
    // it should be array of characters initialized
    // from the literal. It behaves the same way
    //
    char sz[] = "This is a normal string.";
    Reverse(sz);
    cout << "Result: '" << sz << "'\n";
 
    return 0;    
}

Open in new window

0
 
LVL 29

Expert Comment

by:pepr
ID: 23630947
Another recursive solution is based on idea that would be used say in Lisp -- get the first character, reverse the tail, and append the char to the reversed tail. However, it may be not that crystal clear when doing it in-situ.
void ReverseCore(char c, char * dst, char * tail)
{
    // If there is some tail, get its first character
    // which is to be placed in front of the c and
    // do the same with the rest of the tail.
    //
    if (strlen(tail) > 0)
        ReverseCore(*tail, dst-1, tail+1); 
 
    // Now store the remembered character to the given 
    // destination.
    //
    *dst = c;
} 
 
 
void Reverse(char * sz)
{
    ReverseCore(*sz, sz+strlen(sz)-1, sz+1);
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23631090
>> But, also next line ch[1]=NULL  will cause problem, becaue it will insert NULLs many times in the string.

I'll give you a little hint ...

When reversing a string, doing it iteratively is a lot easier, and a lot faster ... What you want to do is swap the first with the last character, then the second with the second-to-last character, etc. until you arrive at the middle of the string.

If you really want to do it recursively, then the idea is that every recursive call saves the next character in the local context. When the end of the string is reached (at the deepest point of the recursion), these saved characters are then placed back in the string one by one (obviously in reverse order).
0
 

Author Comment

by:Gupi
ID: 23632040
Thanks Infinity08 !
>> If you really want to do it recursively, then the idea is that every recursive call saves the next character in the local context. When the end of the string is reached (at the deepest point of the recursion), these saved characters are then placed back in the string one by one (obviously in reverse order).

I tried, but its not working. Please Check.

#include<iostream.h>
#include<conio.H>
int main()
{
      void Reverse(char *);
      char *str="This is a string";
      Reverse(str);
      cout<<str;
return 0;
}

void Reverse(char *str)
{
      if(str==NULL)
            return;
      char s=*str;
      Reverse(++str);
      *str--=s;
}
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23632111
Ok. See my modifications and comments in the code below.

Notice that this code doesn't actually reverse the string (yet), but at least it runs fine.

To make it reverse the string, you'll need to do one more modification : namely, you need to place the characters back in reverse order. So, instead of placing the character at position i, you place it at position (n - i) where n is the length of the string.
I'll leave it to you to figure out how to do that.

I'm sure that by now, you'll agree with me that it's a lot easier to do this iteratively ? Maybe you're changing your mind ?
#include <iostream>                     /* <--- <iostream.h> is deprecated - use <iostream> instead */
 
int main(void) {
      void Reverse(char *);
      char str[] = "This is a string";  /* <--- you can't modify a string literal, so copy the string literal into a modifiable string */
      Reverse(str);
      std::cout << str;                 /* <--- specify the std:: namespace for cout */
      return 0;
}
 
void Reverse(char *str) {
      if (str == NULL || *str == '\0')  /* <--- check whether we reached the end of the string (using the '\0' terminator) */
            return;
      char s = *str;
      Reverse(str + 1);                 /* <--- don't increment str in the local context */
      *str = s;                         /* <--- no need to decrement */
}

Open in new window

0
 
LVL 29

Expert Comment

by:pepr
ID: 23632151
You cannot write the Reverse() with a single argument. The reason is that you have to switch the position of the character and of the reversed tail. In your case, your Reverse() does recursively nothing because...

      char c = *str;            // remember character on the first position
      Reverse(str + 1);      // reverse the string behind the first position
      *str = c;                    // put the character back to the first position where it already is

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23632156
>> In your case, your Reverse() does recursively nothing because...

You might want to read what I wrote above the code ... ;)
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 23632966
> You cannot write the Reverse() with a single argument.

You can if you poke '\0' into the char array as a place-holder and if you are allowed to use strchr to locate the end of the string (which is really cheating because that's going to be implemented as a loop).
void Reverse(char *p)
{
	if (!*p)
		return;
	char* end = strchr(p,'\0')-1;
	char end_val = *p;
	*p = *end;
	*end = '\0';
	Reverse(++p);
	*end = end_val;
}

Open in new window

0
 

Author Comment

by:Gupi
ID: 23634130
Thanks rstaveley !
your code is working.
but i want to try it in the way i have started it.

Infinity08, Please, i tried it as given below, but it is still not working.
>> I'll leave it to you to figure out how to do that.

Sorry, I cant.


#include <iostream.h>
#include<conio.H>
#include<string.h>
int main(void)
{
      void Reverse(char *);
      char str[] = "String";
      clrscr();
      Reverse(str);
      cout <<"\n\nReversed String : "<< str;
return 0;
}

void Reverse(char *str)
{
      int static i=0;
      if (str == NULL || *str == '\0')
          return;
      cout<<"\nReversing : "<<str;    //Ok
      char s = *str;
      cout<<"  ch = " <<s;               // Ok
      Reverse(str + 1);
      *(str+i) = s;        
      cout<<endl<< i<< "  " << str[i]; //Ok
      i++;
}
But final result is not ok.
0
 
LVL 29

Expert Comment

by:pepr
ID: 23634152
Well, but it is a kind of degradation of the algorithm as its time complexity is then O(n^2) instead of O(n).

This is also the case of my solution http:#23630947. However, the strlen() can be replaced there. However, the sz should also be tested to NULL before the first ReverseCore() call.
void ReverseCore(char c, char * dst, char * tail)
{
    if (*tail != '\0')
        ReverseCore(*tail, dst-1, tail+1); 
 
    *dst = c;
} 
 
 
void Reverse(char * sz)
{
    if (sz != NULL)
        ReverseCore(*sz, sz+strlen(sz)-1, sz+1);
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23634310
>> But final result is not ok.

You're very close.

Take a look at the below code. I made one small modification to your code : instead of having a static index, the code now takes a copy of the original char*, and keeps it in a static. This copy is then used to place the characters back into the string.
void Reverse(char *str) {
      static char *str_c = str;
      if (str == NULL || *str == '\0')
          return;
      char s = *str;
      Reverse(str + 1);
      *(str_c++) = s;        
}

Open in new window

0
 
LVL 17

Expert Comment

by:rstaveley
ID: 23634574
Works once, Inf!
#include <iostream>
#include <cstring>
 
#if 0
void Reverse(char *p)
{
	if (!*p)
		return;
	char* end = strchr(p,'\0')-1;
	char end_val = *p;
	*p = *end;
	*end = '\0';
	Reverse(++p);
	*end = end_val;
}
#endif
 
void Reverse(char *str) {
      static char *str_c = str;
      if (str == NULL || *str == '\0')
          return;
      char s = *str;
      Reverse(str + 1);
      *(str_c++) = s;
}
 
int main()
{
	{
		static char str[] = "Hello life";
		Reverse(str);
		std::cout << '[' << str << ']' << std::endl;
	}
	{
		static char str[] = "Goodbye world";
		Reverse(str);
		std::cout << '[' << str << ']' << std::endl;
	}
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23634663
>> Works once, Inf!

Yep, just once hehe. After that, the static needs to be reset somehow lol.
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 23634757
I used to get this sort of comment from QA: "Worked once. May work again." ;-)
0
 
LVL 29

Expert Comment

by:pepr
ID: 23635396
Well, there is a problem. The recursive solution should never use global variables (i.e. the static local variables). This may work in this very special case, but basically, it is wrong approach.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23635633
>> but basically, it is wrong approach.

I'd say that using recursion in the first place is the wrong approach here.
Let alone, if we're constrained by only being able to pass a char* as parameter.
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 23635692
My function in http:#23632966 doesn't suffer in that respect, but I confess that I've lost the plot here. Gupi, what are you looking for that you haven't already seen here?

You can use pepr's solution in http:23619651 with char arrays, if that's what you want.
char str[] = "abcdefg";
std::reverse(str,str+strlen(str));

Open in new window

0
 
LVL 17

Expert Comment

by:rstaveley
ID: 23635728
> You can use pepr's solution in XXXXXX with char arrays, if that's what you want.

http:#23619651 - I mean
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23635746
>> but I confess that I've lost the plot here.

Heh. I'm sorry if I had anything to do with that ;)
0
 

Author Comment

by:Gupi
ID: 23638775
a big thanks to all of you, Experts !

i know Recursion is slow.
but still some times, it preferred approach as it yields smaller and easily understandable code.
as in case of Tree Traversal (Inorder, Preorder etc) and Quick Sort etc.
here also i wanted to solve the problem using recursive procedure, but i also wished to pass just a single argrument, that is the string to be reversed, only.

Thanks pepr and rastevely for your suggestions.

Thanks infinity for your efforts, but Please, i still have one doubt,
can it be done without using static/global variable (and still passing single argument to the function)
or do you think it is not possible/feasible.
Please check and reply.
Thanks.
0
 

Author Comment

by:Gupi
ID: 23638886
i dont want to use static becaue as you have written following does not work :
from main :
char str1[]="String";
Reverse(str1};
cout <<str1 ;  //ok
char str2[]="Oh No !";
Reverse(str2);
cout<<str2;  //does not work due to static variables.

also, since the prototype given by u returns void, it cant be used like :
cout<<Reverse("A String");

This is what i wish/need.
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 23640148
>> but still some times, it preferred approach as it yields smaller and easily understandable code.

I wouldn't use that as an argument. The code is generally not smaller, and I'd argue that recursive code can be more difficult to understand than iterative code.

Plus : you have one serious limitation with recursive code : the stack depth is limited, so you can only make a limited amount of recursive calls.

Below, I've also included a simple iterative reversing of a string ... You be the judge which one is easier ;) And especially which one is more efficient !


>> can it be done without using static/global variable (and still passing single argument to the function)

Yes, and others have shown how to do that ... :

    pepr's http:#23630813 by using a helper function (and other similar ways)
    rstaveley's http:#23632966 which doesn't need the helper function

It gets complicated very quickly though as you have seen. Passing one extra parameter (an index, or the string length, or ...) would make things a lot easier.

Below is one more way from yours truly ;) Slightly different than the other approaches (but not much heh).


>> also, since the prototype given by u returns void, it cant be used like :
>> cout<<Reverse("A String");

That's easy enough to fix. Just make it return the string at the end.

Note however that you won't be able to call it with a string literal if you do the reversing in-place.
/* iterative : */
char *reverse(char *str) {
  char *first = str;
  char *last = str + strlen(str) - 1;
 
  while (first < last) {
    char tmp = *first;
    *first++ = *last;
    *last-- = tmp;
  }
 
  return str;
}
 
/* recursive : */
char *reverse(char *str) {
  char *strc = str;
  while (!(*strc)) ++strc;
 
  char *stre = strc;
  while (*stre) ++stre;
 
  char *strp = str + (stre - strc) - 1;
 
  char c = *strc;
  *strc = '\0';
  if (stre - strc > 1) reverse(str);
  *strp = c;
 
  return str;
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 23641396
Gupi, did you want to split the points with the other experts that participated ? I only joined this discussion later on, and I'm sure I don't deserve (all) of the points.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question