Hi Guys,

i just wrote a program to print a sentence backwards using recursion. But i'm not too happy about it, if someone can give me a more optimized solution i'll be glad. You have to use std::string class.

input:
where the streets have no name
output:
name no have streets the where

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

// read a sentence and print it backwards using recursion

std::string mySentence(std::string);

int main()
{
	std::string query;
	std::cout << "enter a sentence" << std::endl;

	if ( std::getline ( std::cin,query ) )
		std::cout << mySentence(query) << std::endl;
}

std::string
mySentence(std::string sentence)
{
	std::stringstream ss(sentence);
	std::string token;
    int wordCount = 0;
	while(ss>>token)
	{
		wordCount++;
	}

	if(wordCount == 1)
		return sentence;

                int count = 0;
	std::string::iterator it;
	it = sentence.end();
	while(*it != ' ')
	{
		it--;
		count++;
	}
    int len = sentence.length();
	int pos = len - count;
	std::string subString = sentence.substr(0,pos);
	return sentence.substr(pos) + mySentence(subString);
}

Try to compress:

bool Reverser(std::istream& sentence = std::cin, bool im1st = true)
{
    std::string word;
    if (sentence >> word)
    {
        if (Reverser(sentence,false))
            std::cout << " ";
        std::cout << word;
        if (im1st)
            std::cout << std::endl;
        return true;
    }
    return false;
}
Comments
thanks a lot

You might try the following untested logic:

declare mySentence() to:
1) have return type void
2) receive a reference to a stringstream
3) have a local string variable called token
4) if you can extract a string from the stringstream into token
   a) recursively call mySentence again passing it the
      stringstream which is now advanced 1 word from where it was
   b) output token after return from the recursive call

in main()
1) receive user input into a string
2) declare and initialize a stringstream with user input
3) call mySentence passing it the stringstream

Edit: Beaten by ArkM who is using similar logic. Here's the actual code I had written

void mySentence(std::stringstream & ss)
{
  std::string token;
  if(ss >> token)
  {
    mySentence(ss);
    std::cout << token << std::endl; 	
  }
}
Comments
thanks a lot, very neat code.

Yes, it's the same (obvious) recursive pattern.
Regrettably, I was forced to add some bells and twistles to separate words with blanks.
It seems there is some compression reserve here...

to reproduce the white spaces in the original in the reversed sentence:

#include <string>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <ctype.h>

template< typename REV_CHAR_ITER >
void print_reverse( REV_CHAR_ITER rbeg, REV_CHAR_ITER rend )
{
  REV_CHAR_ITER found = std::find_if( rbeg, rend, ::isspace ) ;
  std::copy( found.base(), rbeg.base(),
             std::ostream_iterator<char>(std::cout) ) ;

  if( found != rend )
  {
    std::cout << *found ;
    print_reverse( ++found, rend ) ;
  }
}

int main()
{
  const std::string sentence = "test sentence, containing "
                               "a few  extra     spaces,\t\ttabs" ;
  print_reverse( sentence.rbegin(), sentence.rend() ) ;
  std::cout << '\n' << sentence << '\n' ;
}
Comments
as usual, perfect solution... thanks a lot

Depending on the spacing...(if it doesn't matter) you can use a LIFO stack... I'd use the STL stack...the code would look like this:

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<string> sstack;
string word;

int main( void )
{
    while( cin >> word ) sstack.push( word );
    while( !sstack.empty() ) {
           cout << sstack.top() << " ";
           sstack.pop();
    return 0;
}
Comments
Thanks a lot, nice approach

Yet another variant(s):

void Reverser(std::istream& sentence = std::cin, char delim = '\n')
{
    std::string word;
    if (sentence >> word)
    {
        Reverser(sentence,' ');
        cout << word << delim;
    }
}
inline
void Reverser(const std::string& sentence)
{
    Reverser(std::istringstream(sentence));
}

Thanks a lot guys ... all these were excellent solutions... i'm trying to condition my 'approach' to solving problems ....

This article has been dead for over six months. Start a new discussion instead.