Ad:

C++ Discussion Thread
Unsolved
Views: 2203

Aug 8th, 2008

Review: small recursive code

Expand Post »

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

c++ Syntax (Toggle Plain Text)
#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);
}
#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);
}

Last edited by Agni; Aug 8th, 2008 at 9:29 am.

Agni

Featured Poster

Reputation Points: 431

Solved Threads: 116

Practically a Master Poster

Offline

654 posts
since Dec 2007

Permalink

Aug 8th, 2008

Re: Review: small recursive code

Try to compress:

C++ Syntax (Toggle Plain Text)
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;
}
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;
}

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 8th, 2008

Re: Review: small recursive code

You might try the following untested logic:

C++ Syntax (Toggle Plain Text)
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
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

C++ Syntax (Toggle Plain Text)
void mySentence(std::stringstream & ss)
{
  std::string token;
  if(ss >> token)
  {
    mySentence(ss);
    std::cout << token << std::endl; 	
  }
}
void mySentence(std::stringstream & ss)
{
  std::string token;
  if(ss >> token)
  {
    mySentence(ss);
    std::cout << token << std::endl; 	
  }
}

Last edited by Lerner; Aug 8th, 2008 at 11:01 am.

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

Aug 8th, 2008

Re: Review: small recursive 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...

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 8th, 2008

Re: Review: small recursive code

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

c++ Syntax (Toggle Plain Text)
#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' ;
}
#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' ;
}

vijayan121

Reputation Points: 1159

Solved Threads: 285

Posting Virtuoso

Offline

1,606 posts
since Dec 2006

Permalink

Aug 8th, 2008

Re: Review: small recursive code

Yet another variant(s):

C++ Syntax (Toggle Plain Text)
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));
}
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));
}

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 8th, 2008

Re: Review: small recursive code

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:

C++ Syntax (Toggle Plain Text)
#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;
}
#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;
}

gregorynoob

Reputation Points: 12

Solved Threads: 5

Junior Poster in Training

Offline

86 posts
since Jun 2008

Permalink

Aug 9th, 2008

Re: Review: small recursive code

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

Agni

Featured Poster

Reputation Points: 431

Solved Threads: 116

Practically a Master Poster

Offline

654 posts
since Dec 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: C++ member access question

Next Thread in C++ Forum Timeline: How to make sure no numbers are the same?

DaniWeb Message

Cancel Changes

User Name
Password