生成隨機數與字母

    一題目如下
   
   
   
    Write a parser for a simplified regular expression
   
    On an alphabet set [az] a simplified regular expression is much simpler than the normal regular expression
   
    It has only two meta characters: and *
   
    exact one arbitrary character match
   
    * zero or more arbitrary character match
   
   
   
    舉個例子表達式 ab*d 能匹配 abcd abccd abad 不能匹配abc （空字符串） abd
   
    二解法
   
    解析給定的表達式
   
    生成對應的 NFA（Nondeterministic Finite Automation）
   
    NFA轉化為DFA（Deterministic Finite Automation）
   
    利用DFA判斷輸入字符串
   
    三相關代碼
   
    FiniteAutomatajava 和Statejava隨手寫寫請選擇性參考
   
    FiniteAutomatajava
   
    package parser;
   
    import javautilHashMap;
   
    import javautilHashSet;
   
    import javautilIterator;
   
    import javautilLinkedList;
   
    import javautilMap;
   
    import javautilMapEntry;
   
    import javautilQueue;
   
    import javautilSet;
   
    public class FiniteAutomata {
   
    private State start;
   
    private final static char[] inputs;
   
    static {
   
    inputs = new char[];
   
    for （char i = ; i < ; i++） {
   
    inputs[i] = （char） （a + i）
   
    }
   
    }
   
    private final char episilon = ;
   
    private char stateId;
   
    public void compile（String pattern） {
   
    thisstateId = A;
   
    State NFA = toNFA（pattern）
   
    thisstart = convertToDFA（NFA）
   
    }
   
    private State convertToDFA（State NFA） {
   
    Map<Set<State> State> cache = new HashMap<Set<State> State>（）
   
    Queue<Set<State》 queue = new LinkedList<Set<State》（）
   
    // start state of DFA
   
    Set<State> start = episilon（NFA）
   
    State starter = nextState（）
   
    cacheput（start starter）
   
    queueoffer（start）
   
    while （！queueisEmpty（）） {
   
    Set<State> currentEpisilon = queuepoll（）
   
    State current = cacheget（currentEpisilon）
   
    // create new State
   
    for （char input : inputs） {
   
    Set<State> nextEpisilon = move（currentEpisilon input）
   
    if （nextEpisilonisEmpty（）） {
   
    continue;
   
    }
   
    State next;
   
    if （！ntainsKey（nextEpisilon）） {
   
    next = nextState（）
   
    cacheput（nextEpisilon next）
   
    queueoffer（nextEpisilon）
   
    } else {
   
    next = cacheget（nextEpisilon）
   
    }
   
    boolean isAccept = containsAcceptState（nextEpisilon）
   
    nextsetAccept（isAccept）
   
    currentsetTransition（input next）
   
    }
   
    }
   
    return starter;
   
    }
   
    private Set<State> move（Set<State> currentEpisilon char input） {
   
    Set<State> result = new HashSet<State>（）
   
    for （State s : currentEpisilon） {
   
    State next = stransit（input）
   
    if （next != null） {
   
    resultadd（next）
   
    }
   
    }
   
    return episilon（result）
   
    }
   
    private boolean containsAcceptState（Set<State> nextEpisilon） {
   
    for （State state : nextEpisilon） {
   
    if （stateisAccept（）） {
   
    return true;
   
    }
   
    }
   
    return false;
   
    }
   
    private Set<State> episilon（State s） {
   
    Set<State> cache = new HashSet<State>（）
   
    cacheadd（s）
   
    return episilon（s cache）
   
    }
   
    private Set<State> episilon（Set<State> states） {
   
    Set<State> cache = new HashSet<State>（）
   
    for （State s : states） {
   
    cacheadd（s）
   
    cacheaddAll（episilon（s cache））
   
    }
   
    return cache;
   
    }
   
    private Set<State> episilon（State s Set<State> cache） {
   
    State next = stransit（episilon）
   
    if （next != null && !ntains（next）） {
   
    cacheadd（next）
   
    cacheaddAll（episilon（s cache））
   
    }
   
    return cache;
   
    }
   
    private State toNFA（String pattern） {
   
    char[] expr = patterntoCharArray（）
   
    State currentState = nextState（）
   
    State starter = currentState;
   
    for （char c : expr） {
   
    if （c == ） {
   
    State nextState = nextState（）
   
    // add each transition for all inputs
   
    for （char i : inputs） {
   
    currentStatesetTransition（i nextState）
   
    }
   
    currentState = nextState;
   
    } else if （c == *） {
   
    State nextState = nextState（）
   
    // add each transition for all inputs
   
    for （char i : inputs） {
   
    currentStatesetTransition（i nextState）
   
    }
   
    currentStatesetTransition（episilon nextState）
   
    nextStatesetTransition（episilon currentState）
   
    currentState = nextState;
   
    } else if （c >= a && c <= z） {
   
    State nextState = nextState（）
   
    currentStatesetTransition（c nextState）
   
    currentState = nextState;
   
    } else {
   
    throw new RuntimeException（Unrecognized expression）
   
    }
   
    }
   
    currentStatesetAccept（true）
   
    return starter;
   
    }
   
    private State nextState（） {
   
    return new State（stateId++）
   
    }
   
    public void constructDFA（Map<State Map<Character State》 mapping） {
   
    Iterator<MapEntry<State Map<Character State>>> it = mapping
   
    entrySet（）iterator（）
   
    while （ithasNext（）） {
   
    Entry<State Map<Character State》 entry = itnext（）
   
    State state = entrygetKey（）
   
    Map<Character State> transition = entrygetValue（）
   
    statesetTransition（transition）
   
    }
   
    }
   
    public boolean match（String c） {
   
    char[] candidate = ctoCharArray（）
   
    for （char d : candidate） {
   
    start = starttransit（d）
   
    if （start == null） {
   
    return false;
   
    }
   
    }
   
    return startisAccept（）
   
    }
   
    public static String[] patterns = { abc * *abc *abc a*bc
   
    a*bc a* a* a* a* *abc* ***** … *
   
    bc* b*c*a * abc *a a a*c a*b
   
    };
   
    public static String[] candidates = { abc abc abc aaabbbabc
   
    aaabbbabc abc abc a aa abcdef abc abc
   
    abc abc abc abca abcd abcd abc abc
   
    abc abc };
   
    public static void main（String[] args） {
   
    FiniteAutomata fa = new FiniteAutomata（）
   
    for （int i = ; i < patternslength; i++） {
   
    pile（patterns[i]）
   
    Systemoutprintln（famatch（candidates[i]））
   
    }
   
    }
   
    }
   
    Statejava
   
    package parser;
   
    import javautilHashMap;  import javautilMap;
   
    public class State {
   
    private boolean accept = false;
   
    private char id;
   
    private Map<Character State> mapping = new HashMap<Character State>（）
   
    public State（char c） {
   
    thisid = c;
   
    }
   
    public State（char c boolean isAccept） {
   
    thisid = c;
   
    thisaccept = isAccept;
   
    }
   
    public State transit（char input） {
   
    return mappingget（input）
   
    }
   
    public void setTransition（char input State next） {
   
    thismappingput（input next）
   
    }
   
    public void setTransition（Map<Character State> mapping） {
   
    thismapping = mapping;
   
    }
   
    public boolean isAccept（） {
   
    return thisaccept;
   
    }
   
    public void setAccept（boolean b） {
   
    thisaccept = b;
   
    }
   
    @Override
   
    public int hashCode（） {
   
    final int prime = ;
   
    int result = ;
   
    result = prime * result + id;
   
    return result;
   
    }
   
    @Override
   
    public boolean equals（Object obj） {
   
    if （this == obj）
   
    return true;
   
    if （obj == null）
   
    return false;
   
    if （getClass（） != objgetClass（））
   
    return false;
   
    State other = （State） obj;
   
    if （id != otherid）
   
    return false;
   
    return true;
   
    }
   
    @Override
   
    public String toString（） {
   
    return State [id= + id + ];
   
    }
   
    }
From:http://tw.wingwit.com/Article/program/net/201311/12363.html