C# implementation- "Print all combinations of balanced parentheses"

Question

I implemented polygenelubricants's java code (Valid Permutation of Parenthesis) in C#.

My C# Code:

public static void CombiParentheses(int open, int close, StringBuilder str)
{
    if (open == 0 && close == 0)
    {
        Console.WriteLine(str.ToString());
        str.Clear();
    }
    if (open > 0) //when you open a new parentheses, then you have to close one parentheses to balance it out.
    {                
        CombiParentheses(open - 1, close + 1, str.Append("{"));
    }
    if (close > 0)
    {                
        CombiParentheses(open , close - 1, str.Append("}"));
    }
}

However I'm getting the wrong result:

CombiParentheses(3, 0, tempString2);
{{{}}}
}{}}
}{}
}{{}}
}{}

What causes this difference between C# and Java implementation?

My gut feeling is that it is related to the usage of `StringBuilder` vs. `string` in the Java version. Note that `StringBuilder`'s manipulation functions such as `Append()` return the original `StringBuilder` object itself, not a new one. — dotNET, Mar 14 '17 at 05:38
@MitchWheat: Can you explain please? I don't see any other difference from the Java version. Maybe you're looking at the optimized version in the linked post? — dotNET, Mar 14 '17 at 05:42
The problem is that the java version uses strings. Strings are immutable. If you call the method recursive using strings you'll create a new string instance thats used in recursive call. You uses a StringBuilder and passes the same instance every time to every call. Lets take a look at your first rec. call: string passes `s + "{"` to the call. The same call but the second rec. call will pass the original `s` + `}`. Your StringBuilder instead will contain the opening brace added before. — Sebastian Schumann, Mar 14 '17 at 05:42
To make it clear: First call: `open = close > 0`. `s = ""`, same like `str == ""`. At the first rec. call you pass `"{"` (because `s` is empty). Thats also the same like using StringBuilder. But the second rec. call will pass `"}"` in the string version because `s` is empty but it will pass `"{}"` in the StringBuilder version because you added a closing brace to the stringbuilder in the call before. — Sebastian Schumann, Mar 14 '17 at 05:47

roim · Accepted Answer · 2017-03-15T18:16:33.550

The issue is not in the Java->C# translation, but in the fact that you translated a string to a StringBuilder. When you call

str.Append("(");

You are appending "(" to the current string builder instance (str), and when you do

CombiParentheses(open - 1, close + 1, str.Append("("));

passing that instance itself on your method call, not a new instance.

An easy way to see the problem: suppose you're calling

CombiParentheses(2, 0, str);

When the second output string is written, the call stack will have been

CombiParentheses(2, 0, str):
    CombiParentheses(1, 1, str.Append("(")):
        CombiParentheses(0, 2, str.Append("(")):
            CombiParentheses(0, 1, str.Append(")")):
                CombiParentheses(0, 0, str.Append(")")); // StringBuilder was reset here!
        CombiParentheses(1, 0, str.Append(")")):
            CombiParentheses(0, 1, str.Append("(")):
                CombiParentheses(0, 0, str.Append(")"));

Since you're using a single string builder instance, and you cleared it right before the call stack went into

CombiParentheses(1, 0, str.Append(")"));

The next output will match the output of that call, as if str had no characters on it yet, not the output you're expecting (which would be as if str still had a "(" on it).

If you used a string instead, when you do (string + ")"), the result is a new string, not the same object that you modified, so the problem doesn't arise, when you get back to a CombiParentheses call made earlier in the recursive execution you still have the original string that CombiParentheses call received.

You can use this do see it in runtime:

public static void CombiParentheses(int open, int close, StringBuilder str)
{
    Console.WriteLine("open: {0}; close: {1}; str: {2}", open, close, str.ToString());
    if (open == 0 && close == 0)
    {
        Console.WriteLine(str.ToString());
        str.Clear();
    }

    if (open > 0)
    {
        CombiParentheses(open - 1, close + 1, str.Append("("));
    }

    if (close > 0)
    {
        CombiParentheses(open, close - 1, str.Append(")"));
    }
}

public static void CombiParenthesesFixed(int open, int close, string str)
{
    Console.WriteLine("open: {0}; close: {1}; str: {2}", open, close, str);
    if (open == 0 && close == 0)
    {
        Console.WriteLine(str);
    }

    if (open > 0)
    {
        CombiParentheses(open - 1, close + 1, str + "(");
    }

    if (close > 0)
    {
        CombiParentheses(open, close - 1, str + ")");
    }
}

C# implementation- "Print all combinations of balanced parentheses"

1 Answers1