具有正则表达式的字符串生成,如标准

前端之家收集整理的这篇文章主要介绍了具有正则表达式的字符串生成,如标准前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我不知道实现一个满足以下第二个想法要求的最佳字符串生成器类是可行的:

>使用regex生成标准
> Lexicographical order枚举.
计数推理
>索引访问

我不喜欢正则表达式:我不能想出一个开始的代码,但我只是想到一个天真的实现使用TList作为基类,并使用一个过滤器(Regex)与“强力”生成的字符串.

什么是其他最佳选择?

>订购:首先按长度(最短),然后按字典顺序排列.
>生成中使用的字符范围的规范:[A-Z],[a-z],数字,特殊符号和最终空格(正则表达式)的所有可打印或任何可能的组合.
>带有给定最小/最大值的字符串长度.
>搜索空间用边界约束:开始字符串一个可能性过滤的结束字符串(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();
    }
}

猜你在找的正则表达式相关文章