递归地反转字符串中的单词 [英] Recursively reversing words in a string

问题描述

我的朋友有一个作业，我无法帮助他.基本上，他需要使用递归以相反的顺序打印句子中的单词.例如: 输入-这是一个句子 输出-句子a是这个

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;
}

这可能很简单，因为他只使用基础知识就可以完成快速课程，因此他们只使用iostream库，而没有使用其他任何东西，因此它一定很简单，或者至少不太复杂.因此，我至少要求一种方法或解决方案的想法.我有一种感觉，我在这里错过了一些非常简单的东西，但看不到它.

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.

预先感谢

推荐答案

• 这并不像您想的那么容易.

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

    您需要更改打印命令的调用位置，并将其放置在revSentence()递归调用(称为post-order traversal)下，而您正在执行的调用称为pre-order traversal.

    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;
    }
    

    这篇关于递归地反转字符串中的单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！