证明了对于任意正则表达式都存在一个与之对应的非确定有限状态自动机（即 NFA，反之亦然）。
对于 NFA，状态的匹配转换和字母表中的字符的对应关系就是连接操作的实现
将正则表达式字符串中所有左括号的索引压入栈。每当我们遇到一个右括号，根据括号中的不同内容，进行出栈，最终将左括号从栈中弹出。栈可以很自然的处理嵌套的括号。
闭包运算符（*）只可能出现在
（1）单个字符之后
单字符的闭包：arr[i...i+1]，其中 arr[i]是单字符，arr[i+1]是闭包运算符
G.addEdge(i,i+1);
G.addEdge(i+1,i);（2）右括号之后
闭包表达式：arr[lp...i...i+1]，其中 arr[lp]是左括号，arr[lp+1...i-1]之间是其他正则表达式， arr[i]是右括号，arr[i+1]是闭包运算符
G.addEdge(lp,i+1);
G.addEdge(i+1,lp);在型如（A|B）的正则表达式中，A 和 B 也都是正则表达式。
处理方式是增加 2 条 epsilon 转换：
一条从左括号对应的状态指向 B 中的第一个字符所对应的状态；
另一条从 '|' 字符所对应的状态指向右括号所对应的状态
或操作表达式：arr[lp...or...i]，其中 arr[lp]是左括号，arr[lp+1...or-1]之间是其他正则表达式， arr[or]是'|'，arr[or+1...i-1]之间是其他正则表达式，arr[i]是右括号
G.addEdge(lp,or+1);
G.addEdge(or,i);// 正则表达式的模式匹配（grep）
static class NFA {
// 匹配转换
char[] re;
// epsilon转换
Digraph G;
// 状态数量
int M;
// 根据给定的正则表达式，构造NFA
public NFA(String regexp) {
// 利用栈进行，类似Dijkstra的双栈算法，表达式求值过程
Deque<Integer> ops = new LinkedList<>();
re = regexp.toCharArray();
M = re.length;
// 还需要加一个终结状态，故 +1
G = new Digraph(M + 1);
// '*' '|' '(' ')' 元字符
for (int i = 0; i < M; i++) {
int lp = i;
// 对 '(' 与 '| '入栈。')' 在出栈时处理，不需入栈。'*'会提前处理，也不需入栈。
if (re[i] == '(' || re[i] == '|') {
ops.push(i);
}
// 右括号，准备出栈
else if (re[i] == ')') {
// 弹出栈顶元素
int or = ops.pop();
// 栈顶元素是或表达式
if (re[or] == '|') {
// 再次出栈，这次出栈的就是左括号
lp = ops.pop();
// 或表达式的操作
G.addEdge(lp, or + 1);
// '|' 的处理
G.addEdge(or, i);
}
// 栈顶元素是左括号
else {
// 记录左括号
lp = or;
}
}
// 到此，lp要么是左括号，要么是 '|'
// 查看下一个字符，re[M] 是终结符，不在模式串中
if (i + 1 < M && re[i + 1] == '*') {
// 合法的'|'之后应该是')'，不可能'|'之后是'*'
// 闭包表达式
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
// 这些元字符应该有下一个状态。'|' 之前已经处理了
if (re[i] == '(' || re[i] == '*' || re[i] == ')') {
G.addEdge(i, i + 1);
}
}
}
// NFA 是否能够识别文本 txt
public boolean recognizes(String txt) {
// 已经到达的状态
List<Integer> pc = new LinkedList<>();
// 有向图中深度优先遍历
DirectedDFS dfs = new DirectedDFS(G, 0);
// 初始化起点
for (int v = 0; v < G.V(); v++) {
if (dfs.marked(v)) {
pc.add(v);
}
}
for (int i = 0, n = txt.length(); i < n; i++) {
// 计算txt[i+1]可能达到的所有NFA状态
List<Integer> match = new LinkedList<>();
for (Integer v : pc) {
// 合法的结点状态
if (v < M) {
// 匹配转换
if (re[v] == txt.charAt(i) || re[v] == '.') {
match.add(v + 1);
}
}
}
// 下一轮识别
pc = new LinkedList<>();
// epsilon 转换
dfs = new DirectedDFS(G, match);
for (int v = 0; v < G.V(); v++) {
if (dfs.marked(v)) {
pc.add(v);
}
}
}
// 到达结束状态，能够识别
for (Integer v : pc) {
if (v == M) {
return true;
}
}
return false;
}
}
//有向图
static class Digraph {
// 点的个数
final int V;
// 边的个数
int E;
// 邻接表
Map<Integer, List<Integer>> adj;
public Digraph(int V) {
this.V = V;
this.E = 0;
adj = new HashMap<>();
for (int v = 0; v < V; v++) {
List<Integer> bag = new LinkedList<>();
adj.put(v, bag);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
// 增加一条 v->w 的边
public void addEdge(int v, int w) {
List<Integer> bag = adj.get(v);
bag.add(w);
E++;
}
// 有向图取反
public Digraph reverse() {
Digraph R = new Digraph(V);
for (int v = 0; v < V; v++) {
for (Integer w : adj.get(v)) {
R.addEdge(w, v);
}
}
return R;
}
}
// 有向图的可达性（深度优先搜索）
static class DirectedDFS {
// 是否可达
boolean[] marked;
// 单点的可达性
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
// 多源点可达性
public DirectedDFS(Digraph G, List<Integer> src) {
marked = new boolean[G.V()];
for (Integer s : src) {
if (!marked[s]) {
dfs(G, s);
}
}
}
// 深度优先遍历
private void dfs(Digraph G, int v) {
// 标记
marked[v] = true;
List<Integer> bag = G.adj.get(v);
// 对于改点相连的其他点，递归搜索
for (Integer w : bag) {
if (!marked[w]) {
dfs(G, w);
}
}
}
// 是否可达
public boolean marked(int v) {
return marked[v];
}
}