0

所以我有一个正则表达式模式，我想生成该模式允许的所有文本排列。

例子：

var pattern = "^My (?:biological|real)? Name is Steve$";
var permutations = getStringPermutations(pattern);

这将返回以下字符串列表：

我的名字是史蒂夫

我的真名是史蒂夫

我的生物学名字是史蒂夫

更新： 显然，正则表达式有无限数量的匹配项，所以我只想生成可选的字符串文字，如 (?:biological|real)? 从我上面的例子。(.)* 之类的匹配项太多，因此我不会从中生成它们。

4

3 回答 3

1

如果您将自己限制在两端锚定的正则表达式子集，并且只涉及文字文本、单字符通配符和交替，则匹配的字符串应该很容易枚举。我可能会将正则表达式重写为 BNF 语法并使用它来生成匹配字符串的详尽列表。对于您的示例：

<lang>   -> <begin> <middle> <end>
<begin>  -> "My "
<middle> -> "" | "real" | "biological"
<end>    -> " name is Steve"

从 RHS 上只有终结符的产生式开始，并列举 LHS 上的非终结符可以取的所有可能值。然后在 RHS 上使用非终结符进行制作。对于非终结符号的连接，形成由每个 RHS 非终结符号表示的集合的笛卡尔积。对于交替，取每个选项所代表的集合的并集。继续，直到你完成了<lang>，然后你就完成了。

但是，一旦包含了 '*' 或 '+' 运算符，您就必须处理无限数量的匹配字符串。如果您还想处理诸如反向引用之类的高级功能......您可能正在努力解决与停止问题同构的问题！

于 2009-10-08T00:17:13.827 回答
0

一种可能有点奇怪的方法是首先将可能的选择放入一个数组中，然后基于该数组生成正则表达式，然后使用相同的数组来生成排列。

于 2009-10-08T00:08:49.833 回答
0

这是我编写的一个函数的草图，该函数用于获取字符串列表并返回所有排列可能性的列表：（从每个字符串中获取字符）

public static List<string> Calculate(List<string> strings) {
            List<string> returnValue = new List<string>();
            int[] numbers = new int[strings.Count];
            for (int x = 0; x < strings.Count; x++) {
                numbers[x] = 0;
            }
            while (true) {
                StringBuilder value = new StringBuilder();
                for (int x = 0; x < strings.Count; x++) {
                    value.Append(strings[x][numbers[x]]);
                    //int absd = numbers[x];
                }
                returnValue.Add(value.ToString());
                numbers[0]++;
                for (int x = 0; x < strings.Count-1; x++) {
                    if (numbers[x] == strings[x].Length) {
                        numbers[x] = 0;
                        numbers[x + 1] += 1;
                    }
                }
                if (numbers[strings.Count-1] == strings[strings.Count-1].Length)
                    break;

            }
            return returnValue;
        }
于 2009-10-08T01:23:02.680 回答