C++中的字符串反转

Question

我试图通过保持下面的空格来颠倒句子中单词的顺序。

[this is my test    string] ==> [string test my is    this]

我是按部就班地做的，

[this is my test    string] - input string
[gnirts    tset ym si siht] - reverse the whole string - in-place
[string    test my is this] - reverse the words of the string - in-place
[string test my is    this] - string-2 with spaces rearranged

有没有其他方法可以做到这一点？是否也可以就地完成最后一步？

Answer 1

你的方法很好。但是你也可以这样做：

继续扫描输入中的单词和空格，如果你找到一个单词，就把它放入

• 你找到空格，将空格的数量放入一个队列中

完成此操作后，堆栈上将有N字，队列中将有N-1编号。

While stack not empty do
 print S.pop
 if stack is empty break
 print Q.deque number of spaces
end-while

Answer 2

这是一种方法。

简而言之，构建两个标记列表:一个用于单词，另一个用于空格。然后拼接一个新的字符串，单词按逆序排列，空格按正序排列。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

string test_string = "this is my test    string";

int main()
{
    // Create 2 vectors of strings.  One for words, another for spaces.
    typedef vector<string> strings;
    strings words, spaces;
    // Walk through the input string, and find individual tokens.
    // A token is either a word or a contigious string of spaces.
    for( string::size_type pos = 0; pos != string::npos; )
    {
        // is this a word token or a space token?
        bool is_char = test_string[pos] != ' ';
        string::size_type pos_end_token = string::npos;

        // find the one-past-the-end index for the end of this token
        if( is_char )
            pos_end_token = test_string.find(' ', pos);
        else
            pos_end_token = test_string.find_first_not_of(' ', pos);

        // pull out this token
        string token = test_string.substr(pos, pos_end_token == string::npos ? string::npos : pos_end_token-pos);
        // if the token is a word, save it to the list of words.
        // if it's a space, save it to the list of spaces
        if( is_char )
            words.push_back(token);
        else
            spaces.push_back(token);
        // move on to the next token
        pos = pos_end_token;
    }

    // construct the new string using stringstream
    stringstream ss;
    // walk through both the list of spaces and the list of words,
    // keeping in mind that there may be more words than spaces, or vice versa
    // construct the new string by first copying the word, then the spaces
    strings::const_reverse_iterator it_w = words.rbegin();
    strings::const_iterator it_s = spaces.begin();
    while( it_w != words.rend() || it_s != spaces.end() )
    {
        if( it_w != words.rend() )
            ss << *it_w++;
        if( it_s != spaces.end() )
            ss << *it_s++;
    }

    // pull a `string` out of the results & dump it
    string reversed = ss.str();
    cout << "Input: '" << test_string << "'" << endl << "Output: '" << reversed << "'" << endl;

}

Answer 3

我会这样重新表述这个问题：

测试非空格标记被颠倒，但保留了它们的原始顺序测试5个非空格标记‘

• ’，‘is’，‘my’，‘’，‘
  • ’被颠倒为‘string’，‘test’，‘my’，‘is’，‘this’.

​

• 空间令牌保持原始顺序
  • 空间令牌‘’，‘’在非空间令牌的新顺序之间保持原始顺序

​

下面是一个O(N)解N是char数组的长度。不幸的是，它并没有像OP所希望的那样就位，但是它也没有使用额外的堆栈或队列--它使用一个单独的字符数组作为工作空间。

这是一段C语言的伪代码。

work_array = char array with size of input_array
dst = &work_array[ 0 ]

for( i = 1; ; i++) {
   detect i’th non-space token in input_array starting from the back side
   if no such token {
      break;
   }
   copy the token starting at dst
   advance dst by token_size
   detect i’th space-token in input_array starting from the front side
   copy the token starting at dst
   advance dst by token_size
}

// at this point work_array contains the desired output,
// it can be copied back to input_array and destroyed