regular expression matching_valid number_parsing techniques

Implement regular expression matching with support for'.'and'*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

方法一：有限状态自动机。regular expression matching

public class Solution {
    Map<Integer, Set<Transfer>> nfa = new HashMap<>();
    int accept = 0;
    private Set<Transfer> getTransfers(int state) {
        Set<Transfer> transfers = nfa.get(state);
        if (transfers == null) {
            transfers = new HashSet<Transfer>();
            nfa.put(state, transfers);
        }
        return transfers;
    }
    private Set<Integer> getEpsilonStates(int state) {
        Set<Integer> states = new HashSet<>();
        Iterator<Transfer> it = getTransfers(state).iterator();
        while (it.hasNext()) {
            Transfer transfer = it.next();
            if (transfer.ch == (char)0) states.add(transfer.next);
        }
        return states;
    }
    private Set<Integer> getNextStates(int state, char ch) {
        Set<Integer> states = new HashSet<>();
        Iterator<Transfer> it = getTransfers(state).iterator();
        while (it.hasNext()) {
            Transfer transfer = it.next();
            if (transfer.ch == ch || transfer.ch == .) states.add(transfer.next);
        }
        return states;
    }
    private void addTransfer(int state, Transfer transfer) {
        Set<Transfer> transfers = getTransfers(state);
        transfers.add(transfer);
    }

    private void buildNFA(String re) {
        int state = 0;
        for(int i=0; i<re.length(); i++) {
            int next = state + 1;
            if (i<re.length()-1 && re.charAt(i+1) == *) {
                addTransfer(state, new Transfer((char)0, next));
                addTransfer(next, new Transfer(re.charAt(i), next));
                i ++;
            } else {
                addTransfer(state, new Transfer(re.charAt(i), next));
            }
            state = next;
        }
        accept = state;
        // printNFA();
    }
    
    private void printNFA() {
        System.out.println(this.nfa);
    }
    
    private Set<Integer> getClosure(Set<Integer> states) {
        Set<Integer> closure = new HashSet<>();
        closure.addAll(states);

        Set<Integer> found = new HashSet<>();
        found.addAll(states);
        
        while (!found.isEmpty()) {
            Set<Integer> epsilons = new HashSet<>();
            Iterator<Integer> it = found.iterator();
            while (it.hasNext()) {
                int state = it.next();
                epsilons.addAll(getEpsilonStates(state));
            }
            Iterator<Integer> eit = epsilons.iterator();
            found = new HashSet<>();
            while (eit.hasNext()) {
                int state = eit.next();
                if (closure.contains(state)) continue;
                closure.add(state);
                found.add(state);
            }
        }
        
        return closure;
    }
    
    public boolean isMatch(String s, String p) {
        buildNFA(p);
        Set<Integer> states = new HashSet<>();
        states.add(0);
        for(int i=0; i<s.length(); i++) {
            Set<Integer> closure = getClosure(states);
            Set<Integer> nexts = new HashSet<>();
            Iterator<Integer> it = closure.iterator();
            while (it.hasNext()) {
                nexts.addAll(getNextStates(it.next(), s.charAt(i)));
            }
            states = nexts;
        }
        states = getClosure(states);
        return states.contains(accept);
    }
}

class Transfer {
    char ch;
    int next;
    Transfer(char ch, int next) {
        this.ch = ch;
        this.next = next;
    }
    
    @Override
    public String toString() {
        return "(" + ch + ", " + next + ")";
    }
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-39693-1.html