CODEWITHSUNDEEP
javaarraysloopsstack
Jaden Hambley
Jaden Hambley

Reputation: 65

Reversing the characters of each individual word of a sentence without reversing the word order

I have this code that is supposed to do what the title said, reverse the order of characters without changing the order of the words:

package stackTests;

import java.util.Scanner;
import java.util.Stack;


public class StackTest
{
  Stack<Character> stack;

  public StackTest()
  {
    stack = new Stack<Character>();
  }

  public String reverseString(String str)
  {
    int start = 0;
    int start2 = 0;
    int size;
    char space = ' ';
    char[] cArr;
    Scanner scan = new Scanner(str);
    cArr = str.toCharArray();
    for (; start < cArr.length; start++)
    {
      if(cArr[start] == space || start == cArr.length - 1)
      {
        for (; start2 < stack.size(); start++)
        {
          System.out.print(stack.pop());
        }
      }
      else
      {
        stack.push(cArr[start]);
      }
      start2 = 0;
    }
    return str;
  }
}

It works fine if I enter a single word like "Hello"--it will output "olleH"--but as soon as it gets more complicated than one word it starts to output some weird things."Hello my name is" outputs "ollehem". I'm really new to Stacks and this is my first time using them. I'm not sure if there is a logic error or improper use of Stacks.

Upvotes: 2

Views: 163

Answers (3)

Atri
Atri

Reputation: 5831

Here is how you can do it in-place without using any extra space (Not using stack):

public class ReverseWordsInplace {

    public static void main(String[] args) {
        reverseWords(new StringBuilder("This is a test"));
    }

    public static void reverseWords(StringBuilder s) {
        StringBuilder str = new StringBuilder(s);
        int startWordIndex = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ' || str.length() - 1 == i) {
                int x = 0;
                int endWordIndex = str.charAt(i) == ' ' ? i - 1 : i;
                while (endWordIndex - x > startWordIndex + x) {
                    char c1 = str.charAt(startWordIndex + x);
                    char c2 = str.charAt(endWordIndex - x);
                    str.setCharAt(startWordIndex + x, c2);
                    str.setCharAt(endWordIndex - x, c1);
                    x++;
                }
                startWordIndex = i + 1;
            }
        }
        System.out.println(str);
    }
}

Output:

sihT si a tset

Upvotes: 0

Iłya Bursov
Iłya Bursov

Reputation: 24146

you're not outputting original spaces, this is why you're seeing strange results

here is fixed version:

public static void reverseString(final String str) {
    final Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        final char c = str.charAt(i);
        if (c == ' ') {
            while (!stack.isEmpty())
                System.out.print(stack.pop());
            System.out.print(' ');
        } else
            stack.push(c);
    }
    while (!stack.isEmpty())
        System.out.print(stack.pop());
}

another version without stack, with in-place replacement:

public static void reverseString(final String str) {
    final char[] chars = str.toCharArray();
    int start = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == ' ') {
            reverse(chars, start, i - 1);
            start = i + 1;
        }
    }
    reverse(chars, start, chars.length - 1);
    System.out.println(new String(chars));
}

private static void reverse(final char[] chars, int s, int e) {
    while (s < e) {
        final char t = chars[s];
        chars[s] = chars[e];
        chars[e] = t;
        s++;
        e--;
    }
}

Upvotes: 3

Eagle&#39;sNest
Eagle&#39;sNest

Reputation: 106

If you HAVE to use a stack, I would follow an algorithm like this:

String myString = "Hello World";
Stack<Character> stack = new Stack<Character>();
StringBuilder sb = new StringBuilder();
String[] splitString = myString.split(" ");

//Iterate through each word in the string
for(String s : splitString){

    //Push each character of the word into LIFO stack
    for(char c : s.toCharArray()){
        stack.push(c);
    }

    //Build new string with reverse ordered characters
    while(!stack.isEmpty()){
        sb.append(stack.pop());
    }

    //Append a space as long as it's not the last word of the original string
    if(!s.equals(splitString[splitString.length - 1]))
        sb.append(" ");
}

//Print the new string
System.out.println(sb.toString());

I'm not sure efficiency matters to you, but this algorithm would work in linear time, where n is the number of characters in the string.

Upvotes: 3

Related Questions