CODEWITHSUNDEEP
javarecursion
salamanka44
salamanka44

Reputation: 944

How to print the different ways of parenthesized string

I have to write a program which returns all the different ways of parenthesizing a string. For example, if the given string is "abcd", then we will have exactly these five distinct results:

((ab)c)d     (a(bc))d     (ab)(cd)     a((bc)d)     a(b(cd))

The number of parentheses depends on the length of the string of course, but I thought that the length of the string-2 is suitable (we don't have any idea of the number of parentheses that we can use...). It seems easy: I have just to insert parentheses into each possible position. I think that recursion is suitable here.

I tried to write this :

private static ArrayList<String> generateParens(String string, ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return null; 
    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            str[count+1] = string.charAt(count); 
            generateParens(string, list, leftRem - 1, rightRem, str, count+1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = string.charAt(count);
            str[count+1] = ')';
            generateParens(string, list, leftRem, rightRem - 1, str, count + 1);
        }
    }


    return list;
}

public static ArrayList<String> generateParens(String string) {
    char[] str = new char[string.length()*2]; //because we have a PAIR of parenthese
    ArrayList<String> list = new ArrayList<String>();
    String str2 = string + string;
    return generateParens(str2, list, string.length()-2, string.length()-2, str, 0);
}

I tried to write a recursive function, but I'm not very good in recursion, so I got a lot of problems, especially with indexes. I tried a lot of things, but I still have problems; I'm not sure whether it's only due to the indexes).

Can you help me please to fix that?

Upvotes: 0

Views: 331

Answers (1)

Prune
Prune

Reputation: 77860

You're thinking of this as a character insertion problem. I suggest another view.

Consider this as an algebraic expression, perhaps a + b / c - d, but without rules of operator precedence. You have to find all the possible different ways to compute this: which operations come first, second, and third. Another way to view it is that you have to build all the possible binary trees that have four leaf nodes. This gives us the expressions

((a+b)/c)-d    (a+(b/c))-d    (a+b)/(c-d)    a+((b/c)-d)    a+(b/(c-d))

I'll stick with the algebra idea for now. You are correct that you need exactly N-2 pairs of parentheses in any completed solution. You have N-1 operations, and all but the last (outermost operator) requires a pair of parentheses.

I suggest that you start at the bottom of the tree and work your way up. Keep a list of strings that you have to join. In each iteration, pick one pair of strings to join; stick parentheses around them, and recur with the shorter list. When the list is only two items long, you concatenate them without the outermost set of parentheses. For instance, in getting the second string, your sequence would work something like this, using brackets (array notation?) for the list:

private static genParen(leaves) // is the protocol.  Now for the execution sequence ...

call genParen(["a", "b", "c", "d"])
// Pick the second join ...
// Concatenate the 2nd & 3rd items; add parentheses
leaves[1] = "(" + leaves[1] + leaves[2] + ")"
// Delete item 2 from leaves, and recur:
  call genParen(["a", "(bc)", "d"])
  // This time, pick the first join ...
  leaves[0] = "(" + leaves[0] + leaves[1] + ")"
  // Delete item 1 from leaves, and recur:
    call genParen(["(a(bc))", "d"])
    // There are now only 2 elements remaining, so ...
    return leaves[0] + leaves[1]

Now, as you walk back up the tree, you can add each solution to a list of solutions that you maintain.

The "pick first" or "pick second" join logic isn't hand-waving: your function must iterate through each possible choice in turn: for a list of N elements, you have N-1 possible choices. You have to make each, recur with the shorter list, and save the results.

Also, you must watch your list of results, as there are ways to duplicate an output string. For example, there are two ways to generate (ab)(cd), depending on which single-letter leaf pair you pick first.

Is this enough to move you toward a solution?

Upvotes: 1

Related Questions