正则表达式

正则表达式

对于任意正则表达式都存在一个与之对应的非确定有限状态自动机(NFA),反之亦然

1.正则匹配

/**
 * 正则表达式的模式匹配
 * 概述: 每个正则表达式都对应一个NFA,反之亦然
 * 思路: 将正则表达式转换为有向图(仅将元字符"(*|)"转换为可直接比较的特定字符),这样就可以直接对字符进行匹配
 */
public class NFA {
    private DiGraph graph; //有向图
    private String regexp; //正则表达式
    private final int m;   //正则表达式字符数

    public NFA(String regexp) {
        this.regexp = regexp; //正则表达式
        this.m = regexp.length(); //长度
        this.graph = new DiGraph(m+1); //0-m状态, m为终态
        ArrayDeque<Integer> ops = new ArrayDeque<>(); //使用栈进行括号匹配,遇到'('入栈,遇到')'出栈
        for(int i=0;i<m;++i){
            int lp = i;
            char ch = regexp.charAt(i);
            if(ch == '(' || ch == '|') ops.push(i);
            else if(ch == ')'){
                int or = ops.pop();
                if(regexp.charAt(or) == '|'){ //处理或| ,只能处理单个|(改进:直接处理? 额外加上括号?)
                    graph.addEdge(or,i);
                    lp = ops.pop();
                    graph.addEdge(lp,or+1);
                }
                else if(regexp.charAt(or) == '(')
                    lp = or;
            }
            if(i<m-1 && regexp.charAt(i+1) == '*'){ //处理闭包*,返回到本身或者进入下一个状态
                graph.addEdge(lp,i+1);
                graph.addEdge(i+1,lp);
            }

            if(ch == '(' || ch == '*' || ch == ')') //处理元字符(不能直接比较,将其转换到特定的可比较的字符)
                graph.addEdge(i,i+1);
        }
        if(!ops.isEmpty()) throw new RuntimeException("格式不支持");
    }

    //整个txt和regexp是否完全匹配(通过有向图可达性(到达特定字符),计算出当前状态所有可能匹配情况)
    public boolean recognizes(String txt){
        DirectedDFS dfs = new DirectedDFS(graph,0); //有向图深度优先搜索计算可达性
        HashSet<Integer> current = new HashSet<>();
        HashSet<Integer> match = new HashSet<>();
        for(int i=0;i<txt.length();++i){
            for(int v=0;v<graph.V();++v)
                if(dfs.marked(v)) current.add(v); //所有可达的特定字符

            char ch = txt.charAt(i);
            if("()*|".indexOf(ch) != -1) throw new RuntimeException("txt中不能包含元字符: "+ch);
            for(int v: current){    //匹配所有可能情况
                if(v == m) continue;
                if(ch == regexp.charAt(v) || ch == '.')
                    match.add(v+1);
            }
            if(match.isEmpty()) return false; //不可达
            dfs = new DirectedDFS(graph,match); //深度优先搜索,所有当前匹配的状态match集合可达的下一特定字符

            current.clear();
            match.clear();
        }
        for(int v=0;v<graph.V();++v) //匹配到结尾,是否可达终态
            if(dfs.marked(v) && v == m) return true;
        return false;
    }
}