▶ 书中第五章部分程序，包括在加上自己补充的代码，非确定性有穷自动机（NFA），grep 命令（利用 NFA 匹配）
● 非确定性有穷自动机（NFA）
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.DirectedDFS; public class class01
{ private Digraph graph; // 含 ε-转移 的有穷自动机图
private String regexp; // 输入的正则表达式
private final int m; // 正则表达式包含的字符数 public class01(String inputRegexp) // 根据正则表达式构造 NFA
{
regexp = inputRegexp;
m = regexp.length();
Stack<Integer> ops = new Stack<Integer>();
graph = new Digraph(m + 1); // 自动机的状态数比正则表达式多 1
for (int i = 0; i < m; i++)
{
int lp = i; // 指向当前操作数
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|') // 遇到 '(' 和 '|'，压栈
ops.push(i);
else if (regexp.charAt(i) == ')') // 遇到 ')'，吐栈
{
int or = ops.pop();
if (regexp.charAt(or ) == '|') // 吐出'|'，需要添加两条边，设原文为 (A|B)
{
lp = ops.pop(); // 取出在此之前的 '('
graph.addEdge(lp, or +1); // 第一条边从 '(' 指向 '|' 的后一节点，表示支路 B
graph.addEdge(or , i); // 第二条边从 '|' 指向 ')' 之后，表示支路 A
}
else if (regexp.charAt(or ) == '(') // 吐出 '('，说明存在一个整体'(...)'，用 lp 标记起点，服务于后边的 '*'
lp = or ;
else
assert false; // 栈顶是其他东西（遇不到该分支？因为没有把其他东西压入栈中）
}
if (i < m - 1 && regexp.charAt(i + 1) == '*') // 下一个字符是闭包，需要添加两条边
{
graph.addEdge(lp, i + 1); // 第一条边从当前节点指向 '*' 节点
graph.addEdge(i + 1, lp); // 第二条边从 '*' 节点指向当前节点，如果当前节点是 ')'，则指向当前整体的起点处
}
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')') // 如果当前符号是'(*)' 三者之一，则添加添加一条正常边指向下一节点
graph.addEdge(i, i + 1);
}
if (ops.size() != 0)
throw new IllegalArgumentException("Invalid regular expression");
} public boolean recognizes(String txt) // 使用生成的 NFA 识别输入的字符串
{
Bag<Integer> pc = new Bag<Integer>(); // 存放当前能够到达的所有节点
DirectedDFS dfs = new DirectedDFS(graph, 0); // 从节点 0 深度优先遍历，表示读取正文第 0 位之前就能通过 ε-转移 到达的所有状态，放入背包 pc 中
for (int v = 0; v < graph.V(); v++)
{
if (dfs.marked(v))
pc.add(v);
}
for (int i = 0; i < txt.length(); i++) // 循环每次取原文的一个字符
{
if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')') // 被匹配的原文不能包含 '(*|)'
throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'");
Bag<Integer> match = new Bag<Integer>(); // 临时背包，用于存放能与 txt[i] 匹配的所有正则表达式的状态（“状态” 指的是节点编号）
for (int v : pc) // 遍历 pc，即以当前能够到达的所有状态为起点尝试匹配 txt[i]
{
if (v == m) // pc 包含节点 m，说明已经到达了终点，完成匹配
continue;
if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.') // txt[i] 与正则表达式当前的某个状态可以匹配，向 match 中写入 v 的下一节点
match.add(v + 1);
}
dfs = new DirectedDFS(graph, match); // 以 match 所有元素为起点深度优先遍历，表示当前所有可达节点通过 ε-转移 到达的所有状态
pc = new Bag<Integer>(); // 更新 pc
for (int v = 0; v < graph.V(); v++)
{
if (dfs.marked(v))
pc.add(v);
}
if (pc.size() == 0) // pc 空，说明没有任何可达状态了，停止匹配
return false;
}
for (int v : pc) // 遍历 pc，如果包含节点 m，说明到达了终点，完成匹配
{
if (v == m)
return true;
}
return false;
} public static void main(String[] args)
{
String regexp = "(" + args[0] + ")", txt = args[1]; // 输入的正则表达式最外层用括号包住
class01 nfa = new class01(regexp);
StdOut.println(nfa.recognizes(txt));
}
}
● grep 命令实现
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.NFA; public class class01
{
private class01() {} public static void main(String[] args)
{
String regexp = "(.*" + args[0] + ".*)";
for (NFA nfa = new NFA(regexp); StdIn.hasNextLine();)
{
String line = StdIn.readLine();
if (nfa.recognizes(line))
StdOut.println(line);
}
}
}