|
一题目如下 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 + ]; } } |
