We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

Reversing a string

Gupi
Gupi asked
on
Medium Priority
931 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.
Comment
Watch Question

CERTIFIED EXPERT

Commented:
CERTIFIED EXPERT

Commented:
It seems to be homework, isn't it?

Author

Commented:
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.

Author

Commented:
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.

CERTIFIED EXPERT

Commented:
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

CERTIFIED EXPERT

Commented:
My correction. The StrReverse3 is the correct one with in-situ reversion.

Author

Commented:
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

Author

Commented:
waiting..
CERTIFIED EXPERT
Top Expert 2009

Commented:
>>                 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.

Author

Commented:
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.
CERTIFIED EXPERT

Commented:
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

CERTIFIED EXPERT

Commented:
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

CERTIFIED EXPERT
Top Expert 2009

Commented:
>> 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).

Author

Commented:
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;
}
CERTIFIED EXPERT
Top Expert 2009

Commented:
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

CERTIFIED EXPERT

Commented:
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

CERTIFIED EXPERT
Top Expert 2009

Commented:
>> In your case, your Reverse() does recursively nothing because...

You might want to read what I wrote above the code ... ;)
> 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

Author

Commented:
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.
CERTIFIED EXPERT

Commented:
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

CERTIFIED EXPERT
Top Expert 2009

Commented:
>> 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

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

CERTIFIED EXPERT
Top Expert 2009

Commented:
>> Works once, Inf!

Yep, just once hehe. After that, the static needs to be reset somehow lol.
I used to get this sort of comment from QA: "Worked once. May work again." ;-)
CERTIFIED EXPERT

Commented:
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.
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> 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.
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

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

http:#23619651 - I mean
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> but I confess that I've lost the plot here.

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

Author

Commented:
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.

Author

Commented:
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.
CERTIFIED EXPERT
Top Expert 2009
Commented:
>> 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

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
CERTIFIED EXPERT
Top Expert 2009

Commented:
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.
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.