[C++知识库]Algorithm第四版算法 C++实现(二十八)——NFA（非确定有限状态自动机）正则表达式匹配模式

正则表达式相比大家都很熟悉，rege（regular expression）早在unix时代就已经出现，非常的常用。这是正则表达式的原理，NFA（非确定有限状态自动机），与KMP算法的原理类似，不同点是，因为或的存在，我们不能仅仅根据一个字符就推断出模式是否存在。所以我们需要NFA。不过在处理NFA之前，我们需要先把正则表达式进行处理，方法和dijkstra双栈算法非常相似（在学习栈的时候介绍过，处理运算表达式的算法）。经过这样的处理之后，我们再用有向图构造出自动机的模式，就可以用来匹配了。

class NFA
{
private:
	std::string re;
	digraph *g;
	int m;
public:
	NFA(std::string regexp)
	{
		std::vector<int> ops;
		re = regexp;
		m = re.length();
		static digraph gd(m + 1);
		g = &gd;
		for (int i = 0; i < m; i++)
		{
			int lp = i;
			if (re[i] == '(' || re[i] == '|')
			{
				ops.push_back(i);
			}
			else if (re[i] == ')')
			{
				int ort = ops.back();
				ops.pop_back();
				if (re[ort] == '|')
				{
					lp = ops.back();
					ops.pop_back();
					g->add_edge(lp,ort + 1);
					g->add_edge(ort, i);
				}
				else
				{
					lp = ort;
				}
			}
			if (i < m - 1 && re[i + 1] == '*')
			{
				g->add_edge(lp, i + 1);
				g->add_edge(i + 1, lp);
			}
			if (re[i] == '(' || re[i] == '|' || re[i] == ')')
			{
				g->add_edge(i, i + 1);
			}
		}
	}
	bool recognizes(std::string txt)
	{
		std::vector<int> pc;
		DFS dfs(*g, 0);
		for (int v = 0; v < g->numv(); v++)
		{
			if (dfs.is_marked(v))
			{
				pc.push_back(v);
			}
		}
		for (int i = 0; i < txt.length(); i++)
		{
			std::vector<int> match;
			for (int v : pc)
			{
				if (v < m)
				{
					if (re[v] == txt[i] || re[v] == '.')
					{
						match.push_back(v + 1);
					}
				}
			}
			pc.clear();
			DFS temp(*g,match[0]);
			dfs = temp;
			for (int v = 0; v < g->numv(); v++)
			{
				if (dfs.is_marked(v))
					pc.push_back(v);
			}
		}
		for (int v : pc)
		{
			if (v == m)
				return true;
		}
		return false;
	}
};

我弱弱的说一句，正则表达式的原理，理解就好，相比之下，还是记住正则表达式的匹配方法更加实用和重要。