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;
 }
}

• Devon Parsons: On your second for loop, I would recommend iterating over the stack's size instead of the original string's length - what if you later want to add a step where you put some more characters in the stack?
• rbp: Java already has a built-in stack that would be used implicitly by making reverseString() recursive!

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.

• Voo: Well if you start going to such lengths to take care of unicode, then you probably would want to really make the whole thing unicode aware. In which case a single unicode codepoint does not necessarily map to a single logical character, so you would have to take care of that too. Doing so in vanilla Java is a horrible undertaking though.
• amon: @Voo excellent catch! We'd need to find and reverse grapheme clusters. Feel free to write another answer or to edit my post to show how it's done (because I currently lack the knowledge to find grapheme clusters).
• Maja Piechotka: @Voo and then you have abstract characters, coded characters, user-perceived characters and grapheme clusters... all of which can be called characters.
• Maja Piechotka: It's also worth noting that reversing of array of code points is still not correct as you have ability to combine two code points - which should be kept in order. Otherwise the modification move to another character.

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.

• WernerCD: Major lesson? Many ways to do the same thing as a programmer. Kudos on this one.

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();

• rolfl: Hi, and welcome to Code Review, nice first answer, +1
• dusky: @maaartinus No, it does work with surrogate pairs. From Javadoc: If there are any surrogate pairs included in the sequence, these are treated as single characters for the reverse operation. Thus, the order of the high-low surrogates is never reversed.
• maaartinus: Sorry, I see, I can't read Javadoc. Removing my comment.

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));
}

• maaartinus: You won't name any variable char, at least not when you want it to compile. Moreover, note that repeating the type name usually carries no information. I personally never use long name for variables spanning no more than 1-3 lines, but it's just me.
• tim: @maaartinus good point, char was not the best alternative to choose :) And my suggestion was to get rid of it entirely, but if it is kept, I think it should have a better name then ch, otherwise there is really no reason for it to exist. Maybe charToStore and retrievedChar, or charToAppend.
• Arun Prakash: @tim Any easy way to find this running time?
• tim: @ArunPrakash I posted my timing code. It's not that accurate, but good enough for this situation, I think.

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(...).

• Vogel612: Please elaborate on why using printf would be better than using println. Additionally, please don't edit other people's answer to use a completely different class :(
• Andrei Socaciu: @Vogel612 Code is easier to read with printfs, especially if you have multiple arguments. As for the edit, Uwe's answer recommended using a StringBuilder, but his code example contained a StringBuffer, so I corrected that.
• Vogel612: Why not write the first in your answer and leave the second as a comment instead? ;)
• Andrei Socaciu: @Vogel612 simple: not enough rep to comment on others' answers.
• Vogel612: (facepalm to self) point taken.