具有正则表达式的字符串生成,如标准
我不知道实现一个满足以下第二个想法要求的最佳字符串生成器类是可行的:
>使用regex生成标准 我不喜欢正则表达式:我不能想出一个开始的代码,但我只是想到一个天真的实现使用TList作为基类,并使用一个过滤器(Regex)与“强力”生成的字符串. 什么是其他最佳选择? >订购:首先按长度(最短),然后按字典顺序排列. 最后编辑 首先,我使用正则表达式代替正则表达式来改写标题. 我正在考虑修改第一个要求,因为它是一个敞开的门,可能导致不合理的问题. 我需要建议和帮助正确的措辞. 第二个想法要求编辑完成.仍然愿意提出改进建议.
我会通过构建语言的最低
Deterministic Finite Automaton 来做到这一点.如果您正在使用正则表达式,则可以通过Thompson的结构自动完成,然后再进行子集构造和最小化.例如见
this description.
使用DFA,您可以使用以下算法: Let P = { < START,[""] > } be a set of pairs <State,list of strings> for n = 0,1,... Max Let P' = {} be a new set while P is not empty Remove the pair <s,L> from P For each transition s -- c --> t in alpha order of c if t is an accepting state,output l + c for each string l in L put <t,L + c> in P' (** i.e. append c to each string in L) end Set P = P' end 请注意,标记为**的步骤需要设置为true,因为重复项可以轻松地出现. 这是一个核心算法. P可以随着输出长度呈指数增长,但这只是跟踪未来输出字符串的所有可能性的代价.您可以通过在列表L中维护排序顺序并通过在达到资源限制时切断搜索来确保您提到的订单/大小/空间限制. 编辑 这里是一个玩具Java示例,其中我已经将DFA用简单的二进制浮点文字编码,并带有可选的减号.这使用与上面的伪代码稍微不同的方案来获得输出的严格排序顺序和适应字符范围. import java.util.Comparator; import java.util.TreeSet; public class Test{ public static class DFA { public static class Transition { final int to; final char lo,hi; // Character range. public Transition(int to,char lo,char hi) { this.to = to; this.lo = lo; this.hi = hi; } public Transition(int to,char ch) { this(to,ch,ch); } } // transitions[i] is a vector of transitions from state i. final Transition [] [] transitions; // accepting[i] is true iff state i is accepting final boolean [] accepting; // Make a fresh immutable DFA. public DFA(Transition [] [] transitions,boolean [] accepting) { this.transitions = transitions; this.accepting = accepting; } // A pair is a DFA state number and the input string read to get there. private static class Pair { final int at; final String s; Pair(int at,String s) { this.at = at; this.s = s; } } // Compare pairs ignoring `at` states,since // they are equal iff the strings are equal. private Comparator<Pair> emitOrder = new Comparator<Pair>() { @Override public int compare(Pair a,Pair b) { return a.s.compareTo(b.s); } }; // Emit all strings accepted by the DFA of given max length. // Output is in sorted order. void emit(int maxLength) { TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder); pairs.add(new Pair(0,"")); for (int len = 0; len <= maxLength; ++len) { TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder); while (!pairs.isEmpty()) { Pair pair = pairs.pollFirst(); for (Transition x : transitions[pair.at]) { for (char ch = x.lo; ch <= x.hi; ch++) { String s = pair.s + ch; if (newPairs.add(new Pair(x.to,s)) && accepting[x.to]) { System.out.println(s); } } } } pairs = newPairs; } } } // Emit with a little DFA for floating point numbers. public void run() { DFA.Transition [] [] transitions = { { // From 0 new DFA.Transition(1,'-'),new DFA.Transition(2,'.'),new DFA.Transition(3,'0','1'),},{ // From 1 new DFA.Transition(2,{ // From 2 new DFA.Transition(4,{ // From 3 new DFA.Transition(3,new DFA.Transition(4,{ // From 4 new DFA.Transition(4,} }; boolean [] accepting = { false,false,true,true }; new DFA(transitions,accepting).emit(4); } public static void main (String [] args) { new Test().run(); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |