javaalgorithmlanguage-agnosticstring

Splitting a String into Smaller Parts based on Parens


Using java I am trying to develop a method using recursion to analyze a String of the form:

(PART0(PART1(PART2)(PART3)))

I want the method to split apart the relevant Strings. I want this method to give me the ability to perform some logic on each part of the String without the parentheses being involved in this order:

PART2
PART3
PART1
PART0

Here is what my method currently looks like:

private void check(String stmt) throws Exception {

    System.out.println(stmt);
    int firstIndex = 0;
    int lastIndex = 0;
    while(firstIndex !=-1){
        firstIndex = stmt.indexOf('(');
        lastIndex = stmt.lastIndexOf(')');

        check(stmt.substring(firstIndex+1,lastIndex));

     }
}

Here is what my output is so far:

(PART0(PART1(PART2)(PART3)))
PART0(PART1(PART2)(PART3))
PART1(PART2)(PART3)
PART2)(PART3

Basically it breaks down at this part: PART1(PART2)(PART3)

Is there a more elegant way to do this?


Solution

  • Nested contexts work most naturally as a stack.

    -Every time you start a new context (encounter '(') push()

    -Every time you exit a context (encounter ')') pop()

    -Each pop() will then correspond to the complete context

    i.e.:

    public static void main(String args[])
        {
             String s   = "(PART0(PART1(PART2)(PART3)))";
            Stack<StringBuilder> stack = new Stack<StringBuilder>();
            StringBuilder curr = null;
            for (int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i);
                if (c == '(')
                {
                    curr = new StringBuilder();
                    stack.push(curr);
                }
                else if (c == ')')
                {
                    System.out.println(stack.pop());
                }
                else
                {
                    curr.append(c);
                }
            }
        }
    

    You'd probably want to add some error checking as well, i.e. if there's no context to push to or pop then you've got mismatched parens (malformed string).