解析字符串并在多个字符串中生成所有可能的组合

Question

在我的Server数据库中，存储了表示问题的正确解决方案的字符串。在这个字符串中，可以使用某种格式来表示多个正确的解决方案。格式：

possible-text [posibility-1/posibility-2] possible-text

这说明可选性-1或可选性-2是正确的.有多少种可能性是没有限制的(例如pos-1 / pos-2 / pos-3 /.是可能的)。然而，一种可能性可以是无效的，例如：

I am [un/]certain.

这意味着答案可能是“我确定”或“我不确定”。格式也可以嵌套在句子中，例如：

I am [[un/]certain/[un/]sure].

这种格式也可以在一个句子中多次出现，例如：

[I am/I'm] [[un/]certain/[/un]sure].

我想要的是生成所有可能的组合。例如，上述表达式应返回：

I am uncertain.
I am certain.
I am sure.
I am unsure.
I'm uncertain.
I'm certain.
I'm sure.
I'm unsure.

筑巢是没有限制的，也没有多少可能性。如果只有一个可能的解决方案，那么它将不是以上述格式。我不知道该怎么做。

我必须用C#写这个。我认为一个可能的解决方案可能是编写一个regex表达式，该表达式可以捕获/格式并在列表中返回可能的解决方案(对于每个[]-pair)，然后以堆栈式的方式(某种递归和回溯方式)遍历它们来生成可能的解决方案，但我还没有找到一个可行的解决方案。

我不知道这件事到底是怎么开始的。如果有人能给我一些关于如何解决这个问题的建议，我将不胜感激。当我发现什么东西的时候，我会在这里加上它。

注意:我注意到有很多类似的问题，但是所有的解决方案似乎都是针对特定的问题，我认为不适用于我的问题。如果我错了，你还记得之前回答过的一个问题，你能告诉我吗？提前谢谢。

更新：只是为了澄清是否不清楚。代码中的每一行都是可能的输入。整条线都是输入的：

[I am/I'm] [[un/]certain/[/un]sure].

Answer 1

这应该能行。我没有对其进行优化或进行错误检查(以防输入字符串格式错误)。

class Program
{
    static IEnumerable<string> Parts(string input, out int i)
    {
        var list = new List<string>();
        int level = 1, start = 1;
        i = 1;
        for (; i < input.Length && level > 0; i++)
        {
            if (input[i] == '[')
                level++;
            else if (input[i] == ']')
                level--;

            if (input[i] == '/' && level == 1 || input[i] == ']' && level == 0)
            {
                if (start == i)
                    list.Add(string.Empty);
                else
                    list.Add(input.Substring(start, i - start));
                start = i + 1;
            }
        }
        return list;
    }

    static IEnumerable<string> Combinations(string input, string current = "")
    {
        if (input == string.Empty)
        {
            if (current.Contains('['))
                return Combinations(current, string.Empty);
            return new List<string> { current };
        }
        else if (input[0] == '[')
        {
            int end;
            var parts = Parts(input, out end);
            return parts.SelectMany(x => Combinations(input.Substring(end, input.Length - end), current + x)).ToList();
        }
        else
            return Combinations(input.Substring(1, input.Length - 1), current + input[0]);
    }

    static void Main(string[] args)
    {
        string s = "[I am/I'm] [[un/]certain/[/un]sure].";
        var list = Combinations(s);
    }
}

Answer 2

您应该创建一个解析器，该解析器逐个字符读取，并构建句子的逻辑树。当您有树时，很容易生成所有可能的组合。有几个可以使用的词法分析器，例如ANTLR：http://programming-pages.com/2012/06/28/antlr-with-c-a-simple-grammar/