reverse a sentence with recursion

[jamesfarrow]

Hello everyone. I have been asked to reverse a sentence using recursion. Below is what I have managed to do so far, but now I am at a dead end. I can't seem to get my code to do what I want...
the final string should read
"Peppers Pickled of Peck a Picked Piper Peter"
I get
"sreppeP delkciP fo kceP a dekciP repiP reteP"

As you can see it is reversed - kind of. So it has got me thinking... I need to extract each word from the reversed string and then pass it to my recursion function to reverse again?
Any help is welcome!!

  
    char my_string[] {"Peter Piper Picked a Peck of Pickled Peppers"};
    std::cout << my_string << std::endl;
    int string_size{sizeof(my_string)};
    char copy[string_size];
    std::strcpy(copy, my_string);
    
    char *pstart = copy;
    char *pend = copy + (string_size - 1) - 1;
    
    
    
   
    reverse(pstart, pend);
    
    
    std::cout << copy << std::endl;
    
    
    return 0;
}

void reverse(char* start, char* end)
{
    while(start < end)
    {
        std::swap(*start, *end);
        return reverse(start + 1, end - 1);
    }
}

[lastchance]

Put your text in an istringstream. Call reverse on that istringstream.

In the function reverse:
- try to read a word from the stream; return immediately if this fails
- call reverse with the remaining stringstream (this is the recursion)
- output the word.

Your call stack will do the reversing for you.

[jamesfarrow]

Hi - thanks for the reply. To be honest I am do not how to use stringstreams - not come across them yet.

James

[Repeater]

Well that's unfortunate; std::string is the C++ way to do all this sort of thing. Messing around with arrays of char is awkward and error prone and essentially C code; not just in syntax, but in ways of thinking. Thinking in C is a common mistake newcomers to C++ make; I suspect that in such cases, people are actually being taught C, with a couple of extra bits on top, rather than being taught C++.

If you insist on doing this in C, you're going to have to write a function to extract an entire word from the sentence. Do you have to do this in C, or can you use std::string and other basics of C++? I see you're happy to use std::swap so clearly you're using some C++ basics.

[jamesfarrow]

Thanks for the reply. I have done it that way simply to get the recursion bit to work. Thinking on I can convert to C++ strings, get the recursion function to work first. Then maybe use find_first_of for the spaces and extract each word, reverse each word then += to my final string?

James

[Repeater]

Here's a somewhat clunky (but hopefully clear)way of doing it:

#include <iostream>
#include <string>

using namespace std;

string reverseSentence(string input)
{
  // No more sentence? Just return empty string
  if (input.size() == 0) {return string();}

  
  string nextWord;
	
  // Trim space off the front of the string before getting my word
  while (input.size() != 0 &&
	 input[0] == ' ')
    {
      input.erase(input.begin());
    }
	
  // Get my word by grabbing letters until there's no more letters or hit space
  while (input.size() != 0 &&
	 input[0] != ' ' )
    {
      nextWord+=input[0];
      input.erase(input.begin());
    }
	
  return (reverseSentence(input) + ' ' + nextWord);
}


int main() {
	
  string testString("Peter Piper Picked a Peck of Pickled Peppers");
	
  cout << reverseSentence(testString);
	
  // your code goes here
  return 0;
}

[jamesfarrow]

Thanks repeater, below is what I have managed to do with C++ strings, albeit rather rough and ready...

I am able to reverse the sentence as before only now the result is in a C++ string.

Thanks for all of your help - really appreciate it!

 std::string my_string {"Peter Piper Picked a Peck of Pickled Peppers"};
    std::cout << my_string << std::endl;

    std::string copy{my_string};
    int str_len{static_cast<int>( my_string.size())};
  
   
    reverse(copy, 0, str_len - 1);
    std::cout << copy << std::endl;
    
   
    
    return 0;
}

std::string reverse(std::string& str, int start, int end)
{
   while(start < end)
   {
       std::swap(str[start], str[end]);
       return reverse(str, start + 1, end - 1);
   }
    return str;
}

[lastchance]

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

void reverse( istringstream &in )
{
   string word;
   if ( !(in >> word) ) return;
   reverse( in );
   cout << word << ' ';
}

int main()
{
   string sentence;
   cout << "Enter a sentence: ";
   getline( cin, sentence );
   istringstream ss( sentence );
   reverse( ss );
}

Enter a sentence: Peter Piper picked a peck of pickled pepper
pepper pickled of peck a picked Piper Peter 

or, if you don't like stringstreams:

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

void reverse( string s )
{
   int p = s.find( ' ' );
   if ( p == string::npos )
   {
      cout << s << ' ';
      return;
   }
   reverse( s.substr( p + 1 ) );
   cout << s.substr( 0, p + 1 );
}

int main()
{
   string sentence;
   cout << "Enter a sentence: ";
   getline( cin, sentence );
   reverse( sentence );
}

[jamesfarrow]

Hi lastchance - thanks for your help.
I need a bit of help understanding reverse and how it works.
p is set to first instance of white space in string.
p is not = npos so skips over.
reverse is called again with a substring of s starting at p + 1.

it then continues until npos. Forgive my ignorance but how does the cost tie in at the end & is it possible to return a string from this function...

Thanks again

James

[jamesfarrow]

lastchance please see below.

Thanks again for your help with this!

std::string reverse( string s )
{
    std::string result;
    size_t p = s.find( ' ' );
    if ( p == string::npos )
    {
        result = s + ' ';
        return result;
  }
 
    return  reverse( s.substr( p + 1 ) ) + s.substr( 0, p + 1 ) ;
 }

[lastchance]

Sure, you can return what you would otherwise have printed out:

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

string reverse( string s )
{
   int p = s.find( ' ' );
   return p == string::npos ? s + ' ' : reverse( s.substr( p + 1 ) ) + s.substr( 0, p + 1 );
}

int main()
{
   string sentence;
   cout << "Enter a sentence: ";
   getline( cin, sentence );
   cout << reverse( sentence );
}

Enter a sentence: Peter Piper picked a peck of pickled pepper
pepper pickled of peck a picked Piper Peter  

[TheToaster]

You can use the exact same reverse function you made. Just change it to a template and change std::swap to std::iter_swap.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>

using namespace std;

template<typename Iter>
void reverse(Iter start, Iter end)
{
    while(start < end)
    {
        std::iter_swap(start, end);
        return reverse(start + 1, end - 1);
    }
}

int main()
{
    std::stringstream ss{"Peter Piper Picked a Peck of Pickled Peppers"};
    std::vector<std::string> vec{std::istream_iterator<std::string>{ss}, {}};
    reverse(std::begin(vec), --std::end(vec));
    for(auto&& i : vec) std::cout << i << ' ';
    return 0;
}

Though, I would personally rewrite it to make it more iterator friendly and make the end parameter point to one-past-the-last element in the list.

[jamesfarrow]

Thanks to everyone that has helped me! Starting to get somewhere now...