熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

生成隨機數與字母

2013-11-13 10:02:35  來源: .NET編程 
    一題目如下
   
   
   
    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
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.