Обратный порядок слов в строке

переверните строку, а затем, во втором проходе, переверните каждое слово...

в C#, полностью на месте без дополнительных массивов:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == ' ')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Not exactly in place, but anyway: Python:

>>> a = "These pretzels are making me thirsty"
>>> " ".join(a.split()[::-1])
'thirsty me making are pretzels These'

В Smalltalk:

'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]

Я знаю, что никто не заботится о Smalltalk, но это так красиво для меня.

вы не можете сделать разворот без, по крайней мере, некоторые дополнительные структуры данных. Я думаю, что самая маленькая структура будет одним символом в качестве буфера при обмене буквами. Его все еще можно считать "на месте", но это не совсем "дополнительная структура данных".

Ниже приведен код, реализующий то, что описывает Билл ящерица:

string words = "this is a test";

// Reverse the entire string
for(int i = 0; i < strlen(words) / 2; ++i) {
  char temp = words[i];
  words[i] = words[strlen(words) - i];
  words[strlen(words) - i] = temp;
}

// Reverse each word
for(int i = 0; i < strlen(words); ++i) {
  int wordstart = -1;
  int wordend = -1;
  if(words[i] != ' ') {
    wordstart = i;
    for(int j = wordstart; j < strlen(words); ++j) {
      if(words[j] == ' ') {
        wordend = j - 1;
        break;
      }
    }
    if(wordend == -1)
      wordend = strlen(words);
    for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) {
      char temp = words[j];
      words[j] = words[wordend - (j - wordstart)];
      words[wordend - (j - wordstart)] = temp;
    }
    i = wordend;
  }
}

на каком языке? Если PHP, вы можете взорвать на пространстве, а затем передать результат в array_reverse.

Если это не PHP, вам придется сделать что-то немного более сложное, например:

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

public static String ReverseString(String str)
{
    int word_length = 0;
    String result = "";
    for (int i=0; i<str.Length; i++)
    {
        if (str[i] == ' ')
        {
            result = " " + result;
            word_length = 0;
        } else 
        {
            result = result.Insert(word_length, str[i].ToString());
            word_length++;
        }
    }
    return result;
}

Это код на C#.

In Python...

ip = "My name is X Y Z"
words = ip.split()
words.reverse()
print ' '.join(words)

в любом случае cookamunga предоставил хорошее встроенное решение с использованием python!

это предполагает, что все слова разделены пробелами:

#include <stdio.h>
#include <string.h>

int main()
{
    char string[] = "What are you looking at";
    int i, n = strlen(string);

    int tail = n-1;
    for(i=n-1;i>=0;i--)
    {
        if(string[i] == ' ' || i == 0)
        {
            int cursor = (i==0? i: i+1);
            while(cursor <= tail)
                printf("%c", string[cursor++]);
            printf(" ");
            tail = i-1;
        }
    }
    return 0;
}

class Program
{
    static void Main(string[] args)
    {
        string s1 =" My Name varma:;
        string[] arr = s1.Split(' ');
        Array.Reverse(arr);
        string str = string.Join(" ", arr);
        Console.WriteLine(str);
        Console.ReadLine();

    }
}

Это не идеально, но это работает для меня прямо сейчас. Я не знаю, есть ли у него O(n) время выполнения btw (все еще изучая его^^), но он использует один дополнительный массив для выполнения задачи.

Это, вероятно, не лучший ответ на вашу проблему, потому что я использую строку dest для сохранения обратной версии вместо замены каждого слова в исходной строке. Проблема в том, что я использую локальную переменную стека с именем buf для копирования всех слов, и я не могу скопировать, но в исходную строку как это приведет к сбою, если исходная строка имеет тип const char*.

но это была моя первая попытка написать s.th вот так:) Ладно хватит болтать. вот код:

#include <iostream>
using namespace std;

void reverse(char *des, char * const s);
int main (int argc, const char * argv[])
{    
    char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created";
    char *x = (char*)"Dogfish! White-spotted Shark, Bullhead";

    printf("Before: |%s|\n", x);
    printf("Before: |%s|\n", s);

    char *d = (char*)malloc((strlen(s)+1)*sizeof(char));  
    char *i = (char*)malloc((strlen(x)+1)*sizeof(char));

    reverse(d,s);
    reverse(i,x);

    printf("After: |%s|\n", i);
    printf("After: |%s|\n", d);

    free (i);
    free (d);

    return 0;
}

void reverse(char *dest, char *const s) {
    // create a temporary pointer
    if (strlen(s)==0) return;
    unsigned long offset = strlen(s)+1;

    char *buf = (char*)malloc((offset)*sizeof(char));
    memset(buf, 0, offset);

    char *p;
    // iterate from end to begin and count how much words we have
    for (unsigned long i = offset; i != 0; i--) {
        p = s+i;
        // if we discover a whitespace we know that we have a whole word
        if (*p == ' ' || *p == '') {
            // we increment the counter
            if (*p != '') {
                // we write the word into the buffer
                ++p;
                int d = (int)(strlen(p)-strlen(buf));
                strncat(buf, p, d);
                strcat(buf, " ");
            }
        }
    }

    // copy the last word
    p -= 1;
    int d = (int)(strlen(p)-strlen(buf));
    strncat(buf, p, d);
    strcat(buf, "");

    // copy stuff to destination string
    for (int i = 0; i < offset; ++i) {
        *(dest+i)=*(buf+i);
    }

    free(buf);
}

мы можем ввести строку в стек и когда мы извлекаем слова, они будут в обратном порядке.

void ReverseWords(char Arr[])
{
    std::stack<std::string> s;
    char *str;
    int length = strlen(Arr);
    str = new char[length+1];
    std::string ReversedArr;
    str = strtok(Arr," ");
    while(str!= NULL)
    {
        s.push(str);
        str = strtok(NULL," ");
    }
    while(!s.empty())
    {
        ReversedArr = s.top();
        cout << " " << ReversedArr;
        s.pop();
    }
}

эта быстрая программа работает..не проверяет угловые случаи, хотя.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    char word[50];
    struct node *next;
};
struct stack
{
    struct node *top;
};
void print (struct stack *stk);
void func (struct stack **stk, char *str);
main()
{
    struct stack *stk = NULL;
    char string[500] = "the sun is yellow and the sky is blue";
    printf("\n%s\n", string);
    func (&stk, string);
    print (stk);
}
void func (struct stack **stk, char *str)
{
    char *p1 = str;
    struct node *new = NULL, *list = NULL;
    int i, j;
    if (*stk == NULL)
    {
        *stk = (struct stack*)malloc(sizeof(struct stack));
        if (*stk == NULL)
            printf("\n####### stack is not allocated #####\n");
        (*stk)->top = NULL;
    }
    i = 0;
    while (*(p1+i) != '')
    {
        if (*(p1+i) != ' ')
        {
            new = (struct node*)malloc(sizeof(struct node));
            if (new == NULL)
                printf("\n####### new is not allocated #####\n");
            j = 0;
            while (*(p1+i) != ' ' && *(p1+i) != '')
            {
                new->word[j] = *(p1 + i);
                i++;
                j++;
            }
            new->word[j++] = ' ';
            new->word[j] = '';
            new->next = (*stk)->top;
            (*stk)->top = new;
        }
        i++;
   }
}
void print (struct stack *stk)
{
    struct node *tmp = stk->top;
    int i;
    while (tmp != NULL)
    {
        i = 0;
        while (tmp->word[i] != '')
        {
            printf ("%c" , tmp->word[i]);
            i++;
        }
        tmp = tmp->next;
    }
    printf("\n");
}

большинство этих ответов не учитывают начальные и / или конечные пробелы во входной строке. Рассмотрим случай str=" Hello world"... Простой алгоритм реверсирования всей строки и реверсирования отдельных слов завершается переворачиванием разделителей, что приводит к f(str) == "world Hello ".

OP сказал:" Я хочу изменить порядок слов " и не упомянул, что ведущие и конечные пробелы также должны быть перевернуты! Итак, хотя уже есть тонна ответов, я предоставлю [надеюсь] больше правильным в C++:

#include <string>
#include <algorithm>

void strReverseWords_inPlace(std::string &str)
{
  const char delim = ' ';
  std::string::iterator w_begin, w_end;
  if (str.size() == 0)
    return;

  w_begin = str.begin();
  w_end   = str.begin();

  while (w_begin != str.end()) {
    if (w_end == str.end() || *w_end == delim) {
      if (w_begin != w_end)
        std::reverse(w_begin, w_end);
      if (w_end == str.end())
        break;
      else
        w_begin = ++w_end;
    } else {
      ++w_end;
    }
  }

  // instead of reversing str.begin() to str.end(), use two iterators that
  // ...represent the *logical* begin and end, ignoring leading/traling delims
  std::string::iterator str_begin = str.begin(), str_end = str.end();
  while (str_begin != str_end && *str_begin == delim)
    ++str_begin;
  --str_end;
  while (str_end != str_begin && *str_end == delim)
    --str_end;
  ++str_end;
  std::reverse(str_begin, str_end);
}

моя версия использования стека:

public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String ns= s.trim();
        Stack<Character> reverse = new Stack<Character>();
        boolean hadspace=false;

        //first pass
        for (int i=0; i< ns.length();i++){
            char c = ns.charAt(i);
            if (c==' '){
                if (!hadspace){
                    reverse.push(c);
                    hadspace=true;
                }
            }else{
                hadspace=false;
                reverse.push(c);
            }
        }
        Stack<Character> t = new Stack<Character>();
        while (!reverse.empty()){
            char temp =reverse.pop();
            if(temp==' '){
                //get the stack content out append to StringBuilder
                while (!t.empty()){
                    char c =t.pop();
                    sb.append(c);
                }
                sb.append(' ');
            }else{
                //push to stack
                t.push(temp);
            }
        }
        while (!t.empty()){
            char c =t.pop();
            sb.append(c);
        }
        return sb.toString();
    }
}

хранить каждое слово в виде строки в массиве, а затем печатать с конца

public void rev2() {
    String str = "my name is ABCD";
    String A[] = str.split(" ");

    for (int i = A.length - 1; i >= 0; i--) {
        if (i != 0) {
            System.out.print(A[i] + " ");
        } else {
            System.out.print(A[i]);
        }
    }

}

в Python, если вы не можете использовать [:: -1] или reversed(), вот простой способ:

def reverse(text):

  r_text = text.split(" ")
  res = []
  for word in range(len(r_text) - 1, -1, -1): 
    res.append(r_text[word])

  return " ".join(res)

print (reverse("Hello World"))

>> World Hello
[Finished in 0.1s]

печать слов в обратном порядке данного оператора с помощью C#:

    void ReverseWords(string str)
    {
        int j = 0;
        for (int i = (str.Length - 1); i >= 0; i--)
        {
            if (str[i] == ' ' || i == 0)
            {
                j = i == 0 ? i : i + 1;

                while (j < str.Length && str[j] != ' ')
                    Console.Write(str[j++]);
                Console.Write(' ');
            }
        }
    }

собственно, первый ответ:

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

не работает, потому что он отменяет во второй половине цикла работу, которую он сделал в первой половине. Итак, я

words = aString.split(" "); // make up a list
i = 0; j = words.length - 1; // find the first and last elements
while (i < j) {
    temp = words[i]; words[i] = words[j]; words[j] = temp; //i.e. swap the elements
    i++; 
    j--;
}

примечание: Я не знаком с синтаксисом PHP, и я догадался incrementer и decrementer синтаксис, так как он, кажется, похож на Perl.

Как насчет ...

var words = "My name is X Y Z";
var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() );

Я думаю, что это не в он-лайн-Тхо.

В c, это, как вы могли бы сделать это, O(N) и только с помощью O(1) структуры данных (т. е. char).

#include<stdio.h>
#include<stdlib.h>
main(){
  char* a = malloc(1000);
  fscanf(stdin, "%[^\n]", a);
  int x = 0, y;
  while(a[x]!='')
  {
    if (a[x]==' ' || a[x]=='\n')
    {
      x++;
    }
    else
    {
      y=x;
      while(a[y]!='' && a[y]!=' ' && a[y]!='\n')
      { 
        y++;
      }
      int z=y;
      while(x<y)
      {
        y--;
        char c=a[x];a[x]=a[y];a[y]=c; 
        x++;
      }
      x=z;
    }
  }

  fprintf(stdout,a);
  return 0;
}

Это можно сделать более простым с помощью sscanf:

void revertWords(char *s);
void revertString(char *s, int start, int n);
void revertWordsInString(char *s);

void revertString(char *s, int start, int end)
{
     while(start<end)
     {
         char temp = s[start];
         s[start] = s[end];
         s[end]=temp;
         start++;
         end --;
     }
}


void revertWords(char *s)
{
  int start = 0;

  char *temp = (char *)malloc(strlen(s) + 1);
  int numCharacters = 0;
  while(sscanf(&s[start], "%s", temp) !=EOF)
  {
      numCharacters = strlen(temp);

      revertString(s, start, start+numCharacters -1);
      start = start+numCharacters + 1;
      if(s[start-1] == 0)
      return;

  }
  free (temp);

}

void revertWordsInString(char *s)
{
   revertString(s,0, strlen(s)-1);
   revertWords(s);
}

int main()
{
   char *s= new char [strlen("abc deff gh1 jkl")+1];
   strcpy(s,"abc deff gh1 jkl");
   revertWordsInString(s);
   printf("%s",s);
   return 0;
}

import java.util.Scanner;

public class revString {
   static char[] str;

   public static void main(String[] args) {
    //Initialize string
    //str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o',
    //'r', 'l', 'd' };
    getInput();

    // reverse entire string
    reverse(0, str.length - 1);

    // reverse the words (delimeted by space) back to normal
    int i = 0, j = 0;
    while (j < str.length) {

        if (str[j] == ' ' || j == str.length - 1) {

            int m = i;
            int n;

            //dont include space in the swap. 
            //(special case is end of line)
            if (j == str.length - 1)
                n = j;
            else
                n = j -1;


            //reuse reverse
            reverse(m, n);

            i = j + 1;

        }
        j++;
    }

    displayArray();
}

private static void reverse(int i, int j) {

    while (i < j) {

        char temp;
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

        i++;
        j--;
    }
}
private static void getInput() {
    System.out.print("Enter string to reverse: ");
    Scanner scan = new Scanner(System.in);
    str = scan.nextLine().trim().toCharArray(); 
}

private static void displayArray() {
    //Print the array
    for (int i = 0; i < str.length; i++) {
        System.out.print(str[i]);
    }
}

}

в Java с помощью дополнительной строки (с StringBuilder):

public static final String reverseWordsWithAdditionalStorage(String string) {
    StringBuilder builder = new StringBuilder();

    char c = 0;
    int index = 0;
    int last = string.length();
    int length = string.length()-1;
    StringBuilder temp = new StringBuilder();
    for (int i=length; i>=0; i--) {
        c = string.charAt(i);
        if (c == SPACE || i==0) {
            index = (i==0)?0:i+1;
            temp.append(string.substring(index, last));
            if (index!=0) temp.append(c);
            builder.append(temp);
            temp.delete(0, temp.length());
            last = i;
        }
    }

    return builder.toString();
}

в Java на месте:

public static final String reverseWordsInPlace(String string) {
    char[] chars = string.toCharArray();

    int lengthI = 0;
    int lastI = 0;
    int lengthJ = 0;
    int lastJ = chars.length-1;

    int i = 0;
    char iChar = 0;
    char jChar = 0;
    while (i<chars.length && i<=lastJ) {
        iChar = chars[i];
        if (iChar == SPACE) {
            lengthI = i-lastI;
            for (int j=lastJ; j>=i; j--) {
                jChar = chars[j];
                if (jChar == SPACE) {
                    lengthJ = lastJ-j;
                    swapWords(lastI, i-1, j+1, lastJ, chars);
                    lastJ = lastJ-lengthI-1;
                    break;
                }
            }
            lastI = lastI+lengthJ+1;
            i = lastI;
        } else {
            i++;
        }
    }

    return String.valueOf(chars);
}

private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) {
    int lengthA = endA-startA+1;
    int lengthB = endB-startB+1;

    int length = lengthA;
    if (lengthA>lengthB) length = lengthB;

    int indexA = 0;
    int indexB = 0;
    char c = 0;
    for (int i=0; i<length; i++) {
        indexA = startA+i;
        indexB = startB+i;

        c = array[indexB];
        array[indexB] = array[indexA];
        array[indexA] = c;
    }

    if (lengthB>lengthA) {
        length = lengthB-lengthA;
        int end = 0;
        for (int i=0; i<length; i++) {
            end = endB-((length-1)-i);
            c = array[end];
            shiftRight(endA+i,end,array);
            array[endA+1+i] = c;
        }
    } else if (lengthA>lengthB) {
        length = lengthA-lengthB;
        for (int i=0; i<length; i++) {
            c = array[endA];
            shiftLeft(endA,endB,array);
            array[endB+i] = c;
        }
    }
}

private static final void shiftRight(int start, int end, char[] array) {
    for (int i=end; i>start; i--) {
        array[i] = array[i-1];
    }
}

private static final void shiftLeft(int start, int end, char[] array) {
    for (int i=start; i<end; i++) {
        array[i] = array[i+1];
    }
}

вот реализация C, которая делает слово reversing inlace, и у нее есть O(n) сложности.

char* reverse(char *str, char wordend=0)
{
    char c;
    size_t len = 0;
    if (wordend==0) {
        len = strlen(str);
    }
    else {
        for(size_t i=0;str[i]!=wordend && str[i]!=0;i++)
            len = i+1;
    }
            for(size_t i=0;i<len/2;i++) {
                c = str[i];
                str[i] = str[len-i-1];
                str[len-i-1] = c;
            }
    return str;
}

char* inplace_reverse_words(char *w)
{
    reverse(w); // reverse all letters first
    bool is_word_start = (w[0]!=0x20);

    for(size_t i=0;i<strlen(w);i++){
        if(w[i]!=0x20 && is_word_start) {
            reverse(&w[i], 0x20); // reverse one word only
            is_word_start = false;
        }
        if (!is_word_start && w[i]==0x20) // found new word
            is_word_start = true;
    }
    return w;
}

c# решение для обратного слова в предложении

using System;
class helloworld {
    public void ReverseString(String[] words) {
        int end = words.Length-1;
        for (int start = 0; start < end; start++) {
            String tempc;
            if (start < end ) {
                tempc = words[start];
                words[start] = words[end];
                words[end--] = tempc;
            }
        }
        foreach (String s1 in words) {
            Console.Write("{0} ",s1);
        }
    }
}
class reverse {
    static void Main() {
        string s= "beauty lies in the heart of the peaople";
        String[] sent_char=s.Split(' ');
        helloworld h1 = new helloworld();
        h1.ReverseString(sent_char);
    }
}

выход: горошина сердца то во лжи красоты нажмите любую клавишу чтобы продолжить . . .

лучше версии
Проверьте мой блог http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html

public string reverseTheWords(string description)
{
    if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1))
    {
        string[] words= description.Split(' ');
        Array.Reverse(words);
        foreach (string word in words)
        {
            string phrase = string.Join(" ", words);
            Console.WriteLine(phrase);
        }
        return phrase;
    }
    return description;
}

public class manip{

public static char[] rev(char[] a,int left,int right) {
    char temp;
    for (int i=0;i<(right - left)/2;i++)    {
        temp = a[i + left];
        a[i + left] = a[right -i -1];
        a[right -i -1] = temp;
    }

    return a;
}
public static void main(String[] args) throws IOException {

    String s= "i think this works";
    char[] str = s.toCharArray();       
    int i=0;
    rev(str,i,s.length());
    int j=0;
    while(j < str.length) {
        if (str[j] != ' ' && j != str.length -1) {
            j++;
        } else
        {
            if (j == (str.length -1))   {
                j++;
            }
            rev(str,i,j);
            i=j+1;
            j=i;
        }
    }
    System.out.println(str);
}

Я знаю, что есть несколько правильных ответов. Вот один из них в C, который я придумал. Это реализация исключенного ответа. Временная сложность равна O (n), и дополнительная строка не используется.

#include<stdio.h>

char * strRev(char *str, char tok)
{
   int len = 0, i;
   char *temp = str;
   char swap;

   while(*temp != tok && *temp != '') {
      len++; temp++;
   }   
   len--;

   for(i = 0; i < len/2; i++) {
      swap = str[i];
      str[i] = str[len - i]; 
      str[len - i] = swap;
   }   

   // Return pointer to the next token.
   return str + len + 1;
}

int main(void)
{
   char a[] = "Reverse this string.";
   char *temp = a;

   if (a == NULL)
      return -1; 

   // Reverse whole string character by character.
   strRev(a, '');

   // Reverse every word in the string again.
   while(1) {
      temp = strRev(temp, ' ');
      if (*temp == '')
         break;

      temp++;
   }   
   printf("Reversed string: %s\n", a); 
   return 0;
}

использование

char str[50] = {0};
strcpy(str, (char*)"My name is Khan");
reverseWords(str);

метод

void reverseWords(char* pString){
    if(NULL ==pString){
        return;
    }
    int nLen     = strlen(pString);
    reverseString(pString,nLen);
    char* start  = pString;
    char* end    = pString;
    nLen         = 0;
    while (*end) {
        if(*end == ' ' ){
            reverseString(start,nLen);
            end++;
            start = end;
            nLen  = 0;
            continue;
        }
        nLen++;
        end++;
    }
    reverseString(start,nLen);
    printf("\n Reversed: %s",pString);

}


void reverseString(char* start,int nLen){
    char* end = start+ nLen-1;
    while(nLen > 0){
        char temp = *start;
        *start    = *end;
        *end      = temp;
        end--;
        start++;
        nLen-=2;
    }
}