• Advertisement
Sign in to follow this  

reversing a string

This topic is 4335 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Question goes like this How will you reverse a C-string without using any temporary variables? I tried this

#include <iostream>
#include<string>
int main()
{
	
char *str="dumbo";
std::cout<<strrev(str);
return 0;
}
But it didn't work but it works for str[]...I guess I understad the reason. because it's readonly. can't think of any other way without using temporary.

Share this post


Link to post
Share on other sites
Advertisement
Do you want to actually reverse the string, or just print the characters in reverse order?

You can't reverse the string in your example, because str is pointing to read-only memory. Seriously.

Share this post


Link to post
Share on other sites
oh yeah...
That would just print in reverse order..I am still thinking of a way without using temporary variable.

Share this post


Link to post
Share on other sites
For printing it backwards, I'd try this:


#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstring>

int main()
{
const char *str = "Hello World!";

std::reverse_copy(str, str+std::strlen(str), std::ostream_iterator<char>(std::cout));
}



For reversing the string itself, I'd try this:


#include <iostream>
#include <algorithm>
#include <cstring>

int main()
{
char str[] = "Hello World!";

std::reverse(str, str+std::strlen(str));
std::cout << str;
}



If for some reason using the STL isn't allowed, then I'm going to assume this is homework and I shouldn't be helping you.

Share this post


Link to post
Share on other sites
Nice...they should work fine.
I'll just post my attempt of writing reverse function without temporary variable

Share this post


Link to post
Share on other sites
maybe its just my bias, but i like my solution the best

void strrev(char *src)
{
char *ptr;

for (ptr = src; *ptr; ++ptr);
--ptr;

while (src < ptr)
{
*src ^= *ptr ^= *src ^= *ptr;
--ptr;
++src;
}
}

Share this post


Link to post
Share on other sites
Why are you using arrays of characters?

std::string s = "blah";
std::reverse( s.begin(), s.end() );

Share this post


Link to post
Share on other sites
Quote:
Original post by Thetan
maybe its just my bias, but i like my solution the best


I hope I never have to maintain your code. [wink]

Seriously though, the standard library is your friend.

Share this post


Link to post
Share on other sites
C++ all the way!

str.assign( str.rbegin(), str.rend() );

Share this post


Link to post
Share on other sites
I'm not saying you're wrong Fruny, but str.assign( str.rbegin(), str.rend() ); looks very worrying to me. If you're assigning a value to your string, wouldn't that invalidate your iterators? It will probably work anyway since the string will probably reuse its old allocated buffer, but still, is that a good idea?

Share this post


Link to post
Share on other sites
Quote:
Original post by Thetan
maybe its just my bias, but i like my solution the best
*** Source Snippet Removed ***


This is strictly illegal C++ since the same variable is modified twice in one statement. It may work in most of the compilers but illegal.

Share this post


Link to post
Share on other sites
I now tried to reverse bits of unsigned integer and wrote this but it crashes


#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>

int main()
{

unsigned int number=2;

std::stringstream str;

str<<number;

std::reverse(str.str().begin(),str.str().end());

std::cout << str.str();

return 0;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
If you're assigning a value to your string, wouldn't that invalidate your iterators? It will probably work anyway since the string will probably reuse its old allocated buffer, but still, is that a good idea?


No, it's guaranteed to work. A temporary string is first built out of the given range, and is then assigned. See 21.3.5.3-10 page 393.

Share this post


Link to post
Share on other sites
This is a typical interview question, used to see how well you understand arrays and pointers. Thetan's answer is what one generally looks for in this regard.

Share this post


Link to post
Share on other sites
Probably because str.str() is a temporary and writing to it's begin() and end()... well I doubt it's a good idea.


#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>

int main()
{

unsigned int number=2;

std::stringstream str;

str<<number;
std::string s = str.str();

std::reverse(s.begin(),s.end());

std::cout << s;

return 0;
}





but this still won't do what you want, it will make a string containing "2", and reverse that... You'll get "2" as a result.

Bit reversal is a cool thing to do, and in fact my favorite language does this rather well (it's 16 bits only, 32 bit would be done via splitting it into 16-bit components and reversing those):

DO .3 <- !3~#15'$!3~#240'
DO .3 <- !3~#15'$!3~#240'
DO .2 <- !3~#15'$!3~#240'

This obviously reverses the bits of .3 and stores the result in .2.

Here is some code I have just written in my boredom, complete with outputting goodness and silly variable names (may not work for all numbers... works for the ones I tested [wink])

#include <iostream>
#include <iomanip>
using namespace std;

//Kernighan's method (sanity check)
int bits(unsigned int v){
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++){
v &= v - 1; // clear the least significant bit set
}
return c;
}

int main(){
unsigned int x;
cin >> x;
cout << "was: " << x << endl;
cout << "was: 0x" << hex << x << endl;
int c = 8 * sizeof(unsigned int) - 1; //don't know how to get amount of bits without platform specific stuff... maybe log base 2 of int_max
int b = 0;
while(c > b){
cout << "c b: " << dec << c << " " << b << ", x: 0x" << hex << setfill('0') << setw(sizeof(unsigned int)*2) << x << dec << " -- bits = " << bits(x) << endl;
x = x & ~(1 << c) //unset cth bit
& ~(1 << b) //unset bth bit
| ((x & (1 << b))?(1<<c):0) //set cth bit if bth bit was on
| ((x & (1 << c))?(1<<b):0); //set bth bit if cth bit was on
++b; --c;
}
cout << "c b: " << dec << c << " " << b << ", x: 0x" << hex << setfill('0') << setw(sizeof(unsigned int)*2) << x << dec << " -- bits = " << bits(x) << endl;
cout << x << "\n0x" << hex << x << endl;
}



Share this post


Link to post
Share on other sites
Quote:

C++ all the way!


Quote:

How will you reverse a C-string without using any temporary variables?


Seeing as it looks like an interview question, they're obviously looking to see if he understands how pointer arithmetic and null terminated strings work. I've been asked this before, but the question was phrased as to rule out any use of library functions.

Something like this would be appropriate:

void reverse(char* ioString)
{
char* begin = ioString;

unsigned int length = 0;

//calculate the length of the string
for(; ioString[length] != '\0'; ++length);

char* end = begin + length;
while( begin < end )
{
--end;
char temp = *begin;
*begin = *end;
*end = temp;
++begin;
}
}




Then if they ask you to make your answer more generic, something like one of these:

template <class T>
void array_reverse(T* begin, T* end)
{
while( begin < end )
{
--end;
T temp = *begin;
*begin = *end;
*end = temp;
++begin;
}
}

template <class bidirectional_iter>
void range_reverse(bidirectional_iter begin, bidirectional_iter end)
{
while ( begin != end )
{
if( begin == --end ) break;
std::iterator_traits<bidirectional_iter>::value_type temp = *begin;
*begin = *end;
*end = temp;
++begin;
}
}




I assumed that by 'without using any temporary variables' they meant without using a secondary array.

Share this post


Link to post
Share on other sites
Let's not forget tag dispatching! [razz]


template <class RandomIterator>
void reverse(RandomIterator* begin, RandomIterator* end, random_access_iterator_tag)
{
typedef typename std::iterator_traits<RandomIterator>::value_type T;
while( begin < end )
{
--end;
T temp = *begin;
*begin = *end;
*end = temp;
++begin;
}
}

template <class bidirectional_iter>
void reverse(bidirectional_iter begin, bidirectional_iter end, bidirectional_iterator_tag)
{
while ( begin != end )
{
if( begin == --end ) break;
typename std::iterator_traits<bidirectional_iter>::value_type temp = *begin;
*begin = *end;
*end = temp;
++begin;
}
}

//not really necessary, but it will complain in a less confusing manner, probably
template <class Iter, class IncompatibleIteratorCategory>
void reverse(Iter, Iter, IncompatibleIteratorCategory){
struct dummy{};
typedef dummy::error IAmAfraidYourIteratorDoesNotMeetTheRequirementsForTheInPlaceReverseAlgorithmSir;
}

template<class Iterator>
void reverse(Iterator begin, Iterator end){
reverse(begin, end, typename std::iterator_traits<Iterator>::iterator_category());
}


Edit: Uh, I guess this was a little off-topic... [embarrass]

Share this post


Link to post
Share on other sites
TEUTON, we are rather happy when we can help someone.

However, your last questions smells more and more like homework questions: they are uncorrelated to each other (thus I don't think that they come from a book), and are very specific. You have to understand that coming here to have your answers prevents you from searching the answer by yourself, ans as a consequence you won't learn anything.

Moreover, if we answer homework questions on gamedev, it gives to the poster an unfair advantages in regard to his co-learners. This is comonly known as cheating, and that's why they are forbidden on gdnet.

I really suggest you to try to find the anwers by yourself. If you are stucked at a particular problem, and if this problem has really nothing to do with homework, then we'll be happy to help you.

@Nitage; you can use the ending char of the string (we know it is here, and we know that its value is \0) instead of a temporary char.

Share this post


Link to post
Share on other sites
Quote:

@Nitage; you can use the ending char of the string (we know it is here, and we know that its value is \0) instead of a temporary char.


Then I'd still need a variable to keep track of the length of the string.

There's two options here:

  • Use XOR swapping to avoid the temp variable (still need a variable to track how much of the string has been swapped)

  • Point out to the interviewer that you haven't used a temporary variable - you've used a local variable. If he asks further, tell him the only way to do this without using either a local var(or a function that uses one) would be to use a global or static var to track the array length, which would make the function unsafe for a multithreaded environment



I still think TEUTON's quesiton sound more like interview practice questions than homework.

Share this post


Link to post
Share on other sites
Thanks Nitage for supporting me.

yes, they are indeed interview questions. I am going through lot of placement sites which give up lot of material expected to be asked in interviews and written exams including tricky and non-sense questions.

And even if it was a homework question...then even I didn't break any rules(I think so). I showed the amount of code which I could solve and posted it.

Yes, I agree, I didn't search much before posting. I will try to remember that from next time.

[Edited by - TEUTON on April 8, 2006 4:24:21 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by NitageUse XOR swapping to avoid the temp variable (still need a variable to track how much of the string has been swapped)


It doesn't work for all cases. So this is not the valid swap technique.

Share this post


Link to post
Share on other sites
Quote:
Original post by TEUTON
Quote:
Original post by NitageUse XOR swapping to avoid the temp variable (still need a variable to track how much of the string has been swapped)


It doesn't work for all cases. So this is not the valid swap technique.


It works for chars which is what you asked about.
It's not a useful technique though, unless you aren't allowed to declare a temp variable.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement