▶ 书中第五章部分程序，包括在加上自己补充的代码，非确定性有穷自动机（NFA），grep 命令（利用 NFA 匹配）
● 非确定性有穷自动机（NFA）
1 package package01; 2 3 import edu.princeton.cs.algs4.StdOut; 4 import edu.princeton.cs.algs4.Bag; 5 import edu.princeton.cs.algs4.Stack; 6 import edu.princeton.cs.algs4.Digraph; 7 import edu.princeton.cs.algs4.DirectedDFS; 8 9 public class class01 10 { 11 12 private Digraph graph; // 含 ε-转移 的有穷自动机图 13 private String regexp; // 输入的正则表达式 14 private final int m; // 正则表达式包含的字符数 15 16 public class01(String inputRegexp) // 根据正则表达式构造 NFA 17 { 18 regexp = inputRegexp; 19 m = regexp.length(); 20 Stack<Integer> ops = new Stack<Integer>(); 21 graph = new Digraph(m + 1); // 自动机的状态数比正则表达式多 1 22 for (int i = 0; i < m; i++) 23 { 24 int lp = i; // 指向当前操作数 25 if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|') // 遇到 '(' 和 '|'，压栈 26 ops.push(i); 27 else if (regexp.charAt(i) == ')') // 遇到 ')'，吐栈 28 { 29 int or = ops.pop(); 30 if (regexp.charAt(or ) == '|') // 吐出'|'，需要添加两条边，设原文为 (A|B) 31 { 32 lp = ops.pop(); // 取出在此之前的 '(' 33 graph.addEdge(lp, or +1); // 第一条边从 '(' 指向 '|' 的后一节点，表示支路 B 34 graph.addEdge(or , i); // 第二条边从 '|' 指向 ')' 之后，表示支路 A 35 } 36 else if (regexp.charAt(or ) == '(') // 吐出 '('，说明存在一个整体'(...)'，用 lp 标记起点，服务于后边的 '*' 37 lp = or ; 38 else 39 assert false; // 栈顶是其他东西（遇不到该分支？因为没有把其他东西压入栈中） 40 } 41 if (i < m - 1 && regexp.charAt(i + 1) == '*') // 下一个字符是闭包，需要添加两条边 42 { 43 graph.addEdge(lp, i + 1); // 第一条边从当前节点指向 '*' 节点 44 graph.addEdge(i + 1, lp); // 第二条边从 '*' 节点指向当前节点，如果当前节点是 ')'，则指向当前整体的起点处 45 } 46 if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')') // 如果当前符号是'(*)' 三者之一，则添加添加一条正常边指向下一节点 47 graph.addEdge(i, i + 1); 48 } 49 if (ops.size() != 0) 50 throw new IllegalArgumentException("Invalid regular expression"); 51 } 52 53 public boolean recognizes(String txt) // 使用生成的 NFA 识别输入的字符串 54 { 55 Bag<Integer> pc = new Bag<Integer>(); // 存放当前能够到达的所有节点 56 DirectedDFS dfs = new DirectedDFS(graph, 0); // 从节点 0 深度优先遍历，表示读取正文第 0 位之前就能通过 ε-转移 到达的所有状态，放入背包 pc 中 57 for (int v = 0; v < graph.V(); v++) 58 { 59 if (dfs.marked(v)) 60 pc.add(v); 61 } 62 for (int i = 0; i < txt.length(); i++) // 循环每次取原文的一个字符 63 { 64 if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') // 被匹配的原文不能包含 '(*|)' 65 throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'"); 66 Bag<Integer> match = new Bag<Integer>(); // 临时背包，用于存放能与 txt[i] 匹配的所有正则表达式的状态（“状态” 指的是节点编号） 67 for (int v : pc) // 遍历 pc，即以当前能够到达的所有状态为起点尝试匹配 txt[i] 68 { 69 if (v == m) // pc 包含节点 m，说明已经到达了终点，完成匹配 70 continue; 71 if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') // txt[i] 与正则表达式当前的某个状态可以匹配，向 match 中写入 v 的下一节点 72 match.add(v + 1); 73 } 74 dfs = new DirectedDFS(graph, match); // 以 match 所有元素为起点深度优先遍历，表示当前所有可达节点通过 ε-转移 到达的所有状态 75 pc = new Bag<Integer>(); // 更新 pc 76 for (int v = 0; v < graph.V(); v++) 77 { 78 if (dfs.marked(v)) 79 pc.add(v); 80 } 81 if (pc.size() == 0) // pc 空，说明没有任何可达状态了，停止匹配 82 return false; 83 } 84 for (int v : pc) // 遍历 pc，如果包含节点 m，说明到达了终点，完成匹配 85 { 86 if (v == m) 87 return true; 88 } 89 return false; 90 } 91 92 public static void main(String[] args) 93 { 94 String regexp = "(" + args[0] + ")", txt = args[1]; // 输入的正则表达式最外层用括号包住 95 class01 nfa = new class01(regexp); 96 StdOut.println(nfa.recognizes(txt)); 97 } 98 }
● grep 命令实现
1 package package01; 2 3 import edu.princeton.cs.algs4.StdIn; 4 import edu.princeton.cs.algs4.StdOut; 5 import edu.princeton.cs.algs4.NFA; 6 7 public class class01 8 { 9 private class01() {} 10 11 public static void main(String[] args) 12 { 13 String regexp = "(.*" + args[0] + ".*)"; 14 for (NFA nfa = new NFA(regexp); StdIn.hasNextLine();) 15 { 16 String line = StdIn.readLine(); 17 if (nfa.recognizes(line)) 18 StdOut.println(line); 19 } 20 } 21 }