我试图通过保留以下空格来颠倒句子中的单词顺序。
[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
还有其他方法可以做到这一点吗?最后一步也可以就地做吗?
你的方法很好。但您也可以这样做:
S
Q
完成此操作后,堆栈上将有
N
个单词,队列中将有 N-1
个数字。
While stack not empty do
print S.pop
if stack is empty break
print Q.deque number of spaces
end-while
这里有一个方法。
简而言之,构建两个找到的标记列表:一个用于单词,另一个用于空格。 然后拼凑出一个新字符串,其中单词的顺序相反,空格的顺序正向。
#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;
}
我会这样重新表述这个问题:
以下是 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
对于从第一个单词到中心单词的单词,将单词 n 与单词长度 - n 进行交换 首先使用 split 功能,然后进行切换
此伪代码假设您不以空格结束初始字符串,但也可以对此进行适当修改。
1. Get string length; allocate equivalent space for final string; set getText=1
2. While pointer doesn't reach position 0 of string,
i.start from end of string, read character by character...
a.if getText=1
...until blank space encountered
b.if getText=0
...until not blank space encountered
ii.back up pointer to previously pointed character
iii.output to final string in reverse
iv.toggle getText
3. Stop
所有 strtok 解决方案都不适合您的示例,请参见上文。 试试这个:
char *wordrev(char *s)
{
char *y=calloc(1,strlen(s)+1);
char *p=s+strlen(s);
while( p--!=s )
if( *p==32 )
strcat(y,p+1),strcat(y," "),*p=0;
strcpy(s,y);
free(y);
return s;
}
太糟糕了,stl 字符串没有实现push_front。然后你可以用transform()来做到这一点。
#include <string>
#include <iostream>
#include <algorithm>
class push_front
{
public:
push_front( std::string& s ) : _s(s) {};
bool operator()(char c) { _s.insert( _s.begin(), c ); return true; };
std::string& _s;
};
int main( int argc, char** argv )
{
std::string s1;
std::string s( "Now is the time for all good men");
for_each( s.begin(), s.end(), push_front(s1) );
std::cout << s << "\n";
std::cout << s1 << "\n";
}
现在是所有好人的时代
nem doog lla rof 发出 eht si woN
复制数组中的每个字符串并以相反顺序打印(i--)
int main()
{
int j=0;
string str;
string copy[80];
int start=0;
int end=0;
cout<<"Enter the String :: ";
getline(cin,str);
cout<<"Entered String is : "<<str<<endl;
for(int i=0;str[i]!='\0';i++)
{
end=s.find(" ",start);
if(end==-1)
{
copy[j]=str.substr(start,(str.length()-start));
break;
}
else
{
copy[j]=str.substr(start,(end-start));
start=end+1;
j++;
i=end;
}
}
for(int s1=j;s1>=0;s1--)
cout<<" "<<copy[s1];
}
我想我只是使用空格字符来标记(strtok 或 CString::Tokanize)字符串。将字符串推入一个向量,然后以相反的顺序将它们拉出来,并在它们之间用空格连接起来。