C#实现--“打印所有平衡括号的组合”

Question

我在Valid Permutation of Parenthesis中实现了多源洗脱剂的java代码。

我的C#代码：

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

然而，我却得到了错误的结果：

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

是什么导致了C#和Java实现之间的差异？

Answer 1

问题不在Java->C#翻译中，而是在将字符串转换为StringBuilder这一事实上。当你打电话的时候

str.Append("(");

您正在将"(“)附加到当前字符串生成器实例(str)中，并且当您这样做时。

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

在方法调用中传递实例本身，而不是新实例。

了解问题的一个简单方法:假设您正在打电话

CombiParentheses(2, 0, str);

当写入第二个输出字符串时，调用堆栈将被

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(")"));

因为您使用的是单个字符串生成器实例，并且在调用堆栈进入之前就清除了它

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

下一个输出将与该调用的输出相匹配，就好像str上没有字符但没有，而不是您期望的输出(这就好像str上仍然有一个"(" )。

如果使用字符串，则在执行(string + ")")时，结果是一个新的字符串，而不是您修改的相同对象，因此问题不会出现，当您回到递归执行的早期CombiParentheses调用时，仍然有CombiParentheses调用接收的原始字符串。

您可以使用它，请在运行时看到它：

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