Reversing a String using Stack

Question

Is this code okay?

import java.util.Stack;

public class StackReverse {

    public static void main(String[] args) {

        final String inputString = "code review";

        final String reversed = reverseString(inputString);
        System.out.println("The reversed string is " + reversed);

    }

    public static String reverseString(String originalString) {
        Stack<Character> stack = new Stack<>();
        String reversed = "";
        for (int i = 0; i < originalString.length(); i++) {
            char ch = originalString.charAt(i);
            stack.push(ch);
        }
        for (int i = 0; i < originalString.length(); i++) {
            char ch = stack.pop();
            reversed = reversed + ch;

        }
        return reversed;

    }

}

Answer 1

Unicode is hard to get right, especially in Java as it has a more or less broken concept of a “character”. An Unicode code point is a 21-bit number. These code points are encoded to bytes with the UTF-8 or UTF-16 encodings (well, there are a couple more…). But when Java was created, Unicode only had characters in a 16-bit range, and code points were encoded with the (now deprecated) UCS-2 encoding.

There's a lot of pain from the fact that the 21-bit Unicode code points don't fit into a single 16-bit char or Character in Java. Two consecutive chars might actually be surrogate pairs. When reversing a string, we have to special-case these. We can use the Character.isHighSurrogate(char) function to test whether a given char starts a surrogate pair. If we encounter such a code point, we advance to the next char in the string, and push it onto the stack first:

for (int i = 0; i < originalString.length(); i++) {
    char ch = originalString.charAt(i);
    if (Character.isHighSurrogate(ch)) {
        i++;
        if (i < originalString.length()) {
            stack.push(originalString.charAt(i));
        }
    }
    stack.push(ch);
}

As a test case, you can reverse a string with the smiley character 😃: "hi \ud83d\ude03". Reversed, it should be "\ud83d\ude03 ih".

---

It is best to think of Java's char as “an UTF-16 code unit” (see Wikipedia for all the details about UTF-16 you didn't want to know, but should). To learn about what Unicode is, and how to tame it, start with Joel Spolsky's Unicode blog post.

Answer 2

This question provides a really good example of how learning 'tools' is important, but understanding efficiency is better.

The purpose of the task was probably to teach you to use a stack, but there are properties of this challenge which are not well suited to an actual stack solution, and, more importantly, there are other ways of implementing a stack than a Stack object.

Let me make an assertion here: A Stack can be implemented with an array

Now, consider the things we know about this problem.... we know:

• the input is a string
• the output will be a string with the same length
• an array of char (char[]) can be used as the stack

How do you use an array of char as a stack? Well, you add the chars from the input string to an array, and as you do that, you increment the index in the array, so you are 'pushing' to the end, and then you can pop from the end to get the reverse mechanism.

Now, a quick way to create and push the chars from the input, to a stack, is:

char[] stack = input.toCharArray();

Then, a new String can be created with:

char[] reversed = new char[stack.length];
int pos = stack.length - 1;
for (int i = 0; i < stack.length; i++) {
    reversed[i] = stack[pos--]; // pop the stack on to the reversed array
}
return new String(reversed);

This will be significantly faster, it does use a stack, but implemented in an array.

Answer 3

@amon wrote a great answer. With Java 8, handling of surrogate pairs is even easier. There is a codePoints() method on the CharSequence interface.

public static String reverseString(String originalString) {
    Stack<Integer> stack = new Stack<>();
    StringBuilder reversed = new StringBuilder();

    originalString.codePoints().forEach(cp -> stack.push(cp));
    while (!stack.empty()) {
        reversed.appendCodePoint(stack.pop());
    }
    return reversed.toString();
}

In a professional project I would expect:

new StringBuilder(originalString).reverse().toString();

Answer 4

The code look good so far.

The only thing I would change is to use a StringBuilder for the reversed String as String concatenation with + is very inefficient as in your loop the compiler creates the following:

String reversed = "";
// some code
for (int i = 0; i < originalString.length(); i++) {
    char ch = stack.pop();
    StringBuffer tmp = new StringBuffer(reversed);
    tmp.append(ch);
    reversed = tmp.toString();
}
return reversed;

You create a whole lot of objects without any need.

Replace this part of the code with

StringBuilder reverse = new StringBuilder();;
// some code
for (int i = 0; i < originalString.length(); i++) {
    char ch = stack.pop();
    reverse.append(ch);
}
return reversed.toString();

This is much more efficient in time and memory consumption.

Answer 5

Sure, the code is ok, but it's not going to be the fastest way to reverse a string(*) (I'm assuming performance is not the main concern here).

Temporary Variables

You don't really need the two ch variables, you are using them only once, right on the next line. Just write:

stack.push(originalString.charAt(i));
[...]
reversed = reversed + stack.pop();

Naming

• ch is too short, I would name it char.
• reverseString could also be named reverse, it's obvious from the method signature (string in, string out), that it's reversing a string.
• originalString vs reversed: one contains String, one doesn't, this seems inconsistent.

Misc

• remove the additional newlines before closing }.
• reversed = reversed + ch; can be written as reversed += ch; (if you care about performance, use a StringBuilder).

Timing

_{(*) just for fun some quick numbers, reversing a string 1M times:}

reverseStack:         1558510624 <- your method
reverseStackBuilder:  768940393  <- your method with StringBuilder
reverseIt:            238292142  <- see http://stackoverflow.com/questions/7569335/reverse-a-string-in-java
reverseBuilder:       218474538  <- new StringBuilder(originalString).reverse().toString()
reverseArray:         206217358  <- rolfls code

The code used to get those numbers (it's not all that exact. I wouldn't trust it to accurately tell us which one of the fast functions is the best, but it can tell us that the stack version is a lot slower):

public static void main(String[] args) {
    int amount = 1_000_000;
    time((String s) -> reverseIt(s), amount, "reverseIt");
    time((String s) -> reverseBuilder(s), amount, "reverseBuilder");
    time((String s) -> reverseStack(s), amount, "reverseStack");
    time((String s) -> reverseStackBuilder(s), amount, "reverseStackBuilder");
    time((String s) -> reverseArray(s), amount, "reverseArray");
}

interface Function {
    String run(String s);
}

public static void time(Function func, int amount, String funcName) {
    String test = "test";
    for (int i = 0; i < amount / 100; i++) { // warm up
        func.run(i + test + i);
    }
    long startTime = System.nanoTime();
    for (int i = 0; i < amount; i++) { // actual timing
        func.run(i + test + i);
    }
    String spaces = ":                     "; // quick and dirty alignment
    System.out.println(funcName + spaces.substring(0, spaces.length() - funcName.length()) + (System.nanoTime() - startTime));
}

Answer 6

Two small things the other answers don't mention:

• The reverseString method should be private and not public.
• You can use System.out.printf(...) instead of System.out.println(...).