Recursively reversing words in a string

问题:

My friend got an assignment and I can't help him. Basically, using recursion he needs to print the words of a sentence in the reverse order. For example: Input - This is a sentence Output - sentence a is This

Here is an example I wrote him for a normal print, and I could do the whole sentence reversal with no problem, but I can't get neither an idea of a starting point for reversing only the words recursively without a linear approach and using the string library or linked lists or any other way:

#include <iostream>

using namespace std;

void revSentence(char sentence[], int i)
{
  if (sentence[i] == 0)
    return;
  cout<<sentence[i];
  i++;
  revSentence (sentence, i);
}

int main()
{
  char sentence[100];

  cin.getline (sentence, 100);
  int i = 0;

  revSentence(sentence, i);

  return 0;
}

Thing is it probably is something very simple because he is doing a fast course with only the basics, so they didn't use anything but the iostream library, so it must be something simple or at least not too complicated. So I'm asking for at least an idea of approach, or a solution. I've got a feeling I'm missing something very simple here but just can't see it.

Thanks in advance

回答1:

• It's not as easy as you might think.

• You need to change the location where the printing command is called and place it below revSentence() recursive call, this is called post-order traversal, while the one you are doing is called pre-order traversal.

• You also need a stack to push the reversed words.

---

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

void revSentence(std::string const &str, std::stack<char> &stk, int i) { 
  if(i == str.size()) return;
  revSentence (str, stk, i + 1);
  if((!stk.empty() && stk.top() != ' '  && str[i] == ' ') || i == 0) {
    if(!i) std::cout << str[i];
    while(!stk.empty()) { 
        std::cout << stk.top();
        stk.pop();
    }
    if(i) std::cout << str[i];
  }
  stk.push(str[i]);
  if(!i) std::cout << std::endl;
}

int main() {
  std::string sentence;
  std::stack<char> stk;
  std::getline (std::cin, sentence);
  int i = 0;
  revSentence(sentence, stk, i);

  return 0;
}

回答2:

I can not tell if you are allowed to use std::string and it's methods ... but if so...

In the following approach, I emphasize the finding of the first and last words in the input sentence, then using recursion on the leftover (here called sMiddle).

No additional stack of stl used.

The input string is duplicated in automatic variables, so it uses a bit more stack than some other choices (not a problem on Linux).

Assumes - no padding before 1st word, or after last word.

std::string revSentence(std::string s)
{
   std::string retVal;

   do
   {
      size_t posEndW1 = s.find(' ');
      if(posEndW1 == std::string::npos) break;

      // from line start to end of 1st word
      std::string wFirst = s.substr(0, (posEndW1)); 

      size_t posBeginW2 = s.rfind(' '); // from end of line
      if(posBeginW2 == std::string::npos) break;

      std::string wLast = s.substr(posBeginW2+1, std::string::npos); // to line end

      std::string sMiddle = s.substr(posEndW1+1, (posBeginW2-posEndW1-1));

      retVal = wLast + " " + revSentence(sMiddle) + " " + wFirst;
   }while(0);

   return(retVal);
}