Daily Algorithm - reverseParentheses

You have a string s that consists of English letters, punctuation marks, whitespace characters, and brackets. It is guaranteed that the parentheses in s form a regular bracket sequence.

Your task is to reverse the strings contained in each pair of matching parentheses, starting from the innermost pair. The results string should not contain any parentheses.

Example

For string s = "a(bc)de", the output should be
reverseParentheses(s) = "acbde".

Input/Output

• [execution time limit] 3 seconds (java)

• [input] string s

  A string consisting of English letters, punctuation marks, whitespace characters and brackets. It is guaranteed that parentheses form a regular bracket sequence.

  Constraints:
  5 ≤ s.length ≤ 55.

• [output] string

Solution

public class ReverseParentheses {
    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 '(':
                    openPosStack[++openPosTop] = i;
                    break;
                case ')':
                    int a, b;
                    for (a = openPosStack[openPosTop--], b = i; a < b; a++, b--) {
                        char swap = chars[a];
                        chars[a] = chars[b];
                        chars[b] = swap;
                    }
            }
        }

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

    public static void main(String[] args) {
        String s = "a(bcdefghijkl(mno)p)q";

        System.out.println(reverseParentheses(s));
    }
}