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&lt;l;i++){
            if(s.charAt(i)=='(')
                    n++;
    }
    int T[] = new int[n];
    for(int i=0;i&lt;l;i++){
            if(s.charAt(i)=='('){
                    T[j]=i;
                    j++;
            }
    }
    j=0;
    while(n&gt;0){
            j = T[n-1] + 1;
            while(s.charAt(j)!=')'){
                    tmpCh = tmpCh + s.charAt(j);
                    j++;
            }
            for(int q=tmpCh.length()-1;q&gt;=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 ;
}
I consider your solution to be hard to read, and also inefficient.

Readability


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&gt;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-- &gt; 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;


Please put some spaces here:


for(int i=0;i&lt;l;i++){



This would be more conventional and easier to read:

for (int i = 0; i &lt; 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&gt;=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 &lt; 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 &lt; 0) {
                throw new IllegalArgumentException("Parenthesis mismatch");
            }
            int a, b;
            for (a = openPosStack[openPosTop--], b = i; a &lt; b; a++, b--) {
                char swap = chars[a];
                chars[a] = chars[b];
                chars[b] = swap;
            }
        }
    }
    if (openPosTop &gt;= 0) {
        throw new IllegalArgumentException("Parenthesis mismatch");
    }

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