DaniWeb Forum Index > Software Development > C++

C++ RSS

Review: small recursive code

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Dec 2007

Posts: 449

Reputation: Agni is a jewel in the rough

Solved Threads: 70

Agni

Offline

Posting Pro in Training

Review: small recursive code

Aug 8th, 2008

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

 Help with Code Tags 
 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.

thanks
-chandra

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Review: small recursive code

Aug 8th, 2008

Try to compress:

 Help with Code Tags 
 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;
}

•

Join Date: Jul 2005

Posts: 1,692

Reputation: Lerner is a name known to all

Solved Threads: 267

Lerner

Offline

Posting Virtuoso

Re: Review: small recursive code

Aug 8th, 2008

You might try the following untested logic:

 Help with Code Tags 
 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

 Help with Code Tags 
 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.

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Review: small recursive code

Aug 8th, 2008

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

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Review: small recursive code

Aug 8th, 2008

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

 Help with Code Tags 
 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' ;
}

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Review: small recursive code

Aug 8th, 2008

Yet another variant(s):

 Help with Code Tags 
 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));
}

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: Review: small recursive code

Aug 8th, 2008

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:

 Help with Code Tags 
 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;
}