Reversing strings inside parentheses

How can I optimize this algorithm to reverse strings inside parentheses?

String reverseParentheses(String s) {
String tmpCh = new String("");
String tmpChRe = new String("");
String tmp = new String("");
int l = s.length();
int n = 0;
int j =0;
for(int i = 0;i<l;i++){
if(s.charAt(i)=='(')
n++;
}
int T[] = new int[n];
for(int i=0;i<l;i++){
if(s.charAt(i)=='('){
T[j]=i;
j++;
}
}
j=0;
while(n>0){
j = T[n-1] + 1;
while(s.charAt(j)!=')'){
tmpCh = tmpCh + s.charAt(j);
j++;
}
for(int q=tmpCh.length()-1;q>=0;q--)
tmpChRe = tmpChRe + tmpCh.charAt(q);
tmp = s.substring(0,T[n-1]) + tmpChRe + s.substring(T[n-1]+tmpChRe.length()+2);
s = tmp;
n--;
tmp = "";
tmpCh = "";
tmpChRe = "";
}
return s ;
}

• @dhiareznov as in any examples? :) Mar 6, 2017 at 13:39
• @h.j.k. let's take "abc(de)fgh" as an input , the output is "abcedfgh" Mar 7, 2017 at 19:35

I consider your solution to be hard to read, and also inefficient.

String tmpCh = new String("");
String tmpChRe = new String("");
String tmp = new String("");
int l = s.length();
int n = 0;
int j =0;


Of the six variables declared at the top, the only one whose meaning is obvious is l — and since you use l in only one place, I wouldn't even bother making a variable for it.

Your variable naming is problematic. "tmp" is always meaningless as part of a local variable name; local variables are always, by definition, temporary. Furthermore, a better way to indicate the temporary nature of these variables is to place them in the proper scope. Instead of resetting them to empty strings at the end of your while(n>0) loop, declare and initialize them at the top of the loop, so that they are properly scoped:

// Useless assignment.  It gets reassigned right away inside the loop.
// j = 0;

// You only ever use n-1, then n is decremented at the end of the loop.
// So you might as well decrement it right away.
while (n-- > 0) {
// Formerly j
int parenStart = T[n] + 1;
int parenEnd = s.indexOf(')', parenStart);

// Formerly tmpCh
String contents = s.substring(parenStart, parenEnd);

// No need for tmpChRe.  No need for tmp.
s = s.substring(0, T[n]) +
new StringBuilder(contents).reverse() +
s.substring(T[n] + contents.length() + 2);
}
return s;


for(int i=0;i<l;i++){


This would be more conventional and easier to read:

for (int i = 0; i < l; i++) {


Efficiency

Strings in Java are immutable. Any time you concatenate strings using a + b, the compiler actually writes new StringBuilder(a).append(b).toString();. That creates a lot of garbage, and it also involves copying the entire contents of both strings. So, when you loops like this, which work build strings one character at a time, are hugely inefficient!

while(s.charAt(j)!=')'){
tmpCh = tmpCh + s.charAt(j);
j++;
}
for(int q=tmpCh.length()-1;q>=0;q--)
tmpChRe = tmpChRe + tmpCh.charAt(q);


If you need to build a string by repeatedly appending characters, create one StringBuilder and append to it. Note that StringBuilder also has a .reverse() method that would be helpful.

Suggested solution

This solution performs all of the manipulation within one char[] array, so there is hardly any new memory allocated. It also validates that the input string's parentheses are properly matched; your code would either ignore mismatches or crash with an ArrayIndexOutOfBoundsException.

public static String reverseParentheses(String s) {
char[] chars = s.toCharArray();
int[] openPosStack = new int[chars.length];
int openPosTop = -1;

for (int i = 0; i < chars.length; i++) {
switch (chars[i]) {
case '(':
// Push the index of the open parenthesis onto the stack
openPosStack[++openPosTop] = i;
break;
case ')':
// Reverse substring from the matching open parenthesis to here
if (openPosTop < 0) {
throw new IllegalArgumentException("Parenthesis mismatch");
}
int a, b;
for (a = openPosStack[openPosTop--], b = i; a < b; a++, b--) {
char swap = chars[a];
chars[a] = chars[b];
chars[b] = swap;
}
}
}
if (openPosTop >= 0) {
throw new IllegalArgumentException("Parenthesis mismatch");
}

// Remove parentheses from output
int o = 0;
for (int i = 0; i < chars.length; i++) {
switch (chars[i]) {
case '(': case ')':
break;
default:
chars[o++] = chars[i];
}
}
return new String(chars, 0, o);
}

• Very clear solution indeed, can you please write the algorithm you used? I would prefer you write some kind of comment on top of the method. Why you chose to remove parenthesis in another pass? Sep 25, 2017 at 20:43
• reverseInsideParentheses seem more accurate. Sep 25, 2017 at 20:44
• @CodeYogi You could try to remove the parentheses at the same time as the reversal is being done, but the bookkeeping would get very nasty. Sep 25, 2017 at 20:50
• I am too naive for this but I feel strongly that method is too long and doing too much. Sep 25, 2017 at 20:51