dfa.h

安全数组 普通链表 哈希表 二叉搜索树 AVL树 集合类 通用自动机 所有类均使用模板编写

/* 通用 DFA 类（可自定义驱动对象类和状态对象类）
 */

#ifndef DFA_CLASS
#define DFA_CLASS

#include "hashtable.h"	// 哈系表
#include "binstree.h"	// 二叉搜索树

template <class T, class S> 
class CDFATable;
template <class T, class S> 
class CDFA;

// 自动机表中的条目类
template <class T, class S>
class CDFAEntry
{
private:
	S m_state;		// 自动机当前状态（行）（要查询的状态）
	T m_symbol;		// 列（DFA 由 T 对象驱动到下一个状态）（选择的路径）
	S m_data;		// 数据成员（将转到的下一状态）

private:
	CDFAEntry(void){}; // 用户不可实例化该类
	CDFAEntry(S state, T symbol, S data):
			  m_state(state), m_symbol(symbol), m_data(data){};

public:
	// 重载运算符
	CDFAEntry<T, S>& operator= (const CDFAEntry<T, S>& rh); // 将另一条目的值赋给本条目
	bool operator== (const CDFAEntry<T, S>& entry) const; // 是否同一条目（注意不是判断两条目的数据是否相等）（为哈希函数服务）

	friend class CDFATable<T, S>;
	friend class CDFA<T, S>;
};

template <class T, class S>
CDFAEntry<T, S>& CDFAEntry<T, S>::operator= (const CDFAEntry<T, S>& rhs)
{
    // 不能赋值给自己
	if (this == &rhs)
        return *this;
	
	m_data = rhs.m_data; // 设置两条目的数据相等
    return *this;
}

// 是否同一条目
template <class T, class S>
bool CDFAEntry<T, S>::operator == (const CDFAEntry<T, S>& rhs) const
{
	// 行和列将作为哈希表的 key
	return (m_state == rhs.m_state && m_symbol == rhs.m_symbol);
}

/* ------------------------------------------------------------------------ */

// 自动机表类
template <class T, class S>
class CDFATable
{
private:
	HashTable< CDFAEntry<T, S> > m_DFATable;	// 存储 DFA Transition table
	static unsigned long hashfunc(const CDFAEntry<T, S>& entry){return(entry.m_state);} // 哈希函数（注意哈希函数要求的返回值和 S，必要时请手工重写该函数）

private:
	CDFATable(void):m_DFATable(20, hashfunc){};	// 定义哈系表有 20 个桶（可按需调整）（用户不可实例化该类）

	bool Query(CDFAEntry<T, S>& entry){return(m_DFATable.Find(entry));};  // 查询表成员
	void Update(const CDFAEntry<T, S>& entry){m_DFATable.Update(entry);}; // 更新表成员（如不存在，会自动添加）

	friend class CDFA<T, S>;
};

/* ------------------------------------------------------------------------ */

// 自动机类
template <class T, class S>
class CDFA
{
private:
	CDFATable<T, S> m_SimuTable;
//	BinSTree< S > m_AcceptStates;	// Accepting state 列表，这样比较划算（无论从速度还是存储空间）

public:
	CDFA(void){};

	void Clear(void); // 清空自动机（以便重新进行输入）
	void Insert(S state, T symbol, S data, bool accept = false); // 插入数据，最后参数决定 data 是否是 Accepting state
	S Move(S state, T symbol); // 由参数返回下一状态，没有将返回 -1
//	bool Simulate(char *string); // 该 DFA 接受字符串，则为 True

	// **
	BinSTree< S > m_AcceptStates;	// Accepting state 列表，这样比较划算（无论从速度还是存储空间）
};

template <class T, class S>
void CDFA<T, S>::Clear(void)
{
	m_SimuTable.m_DFATable.ClearList();
	m_AcceptStates.ClearList();
}

template <class T, class S>
void CDFA<T, S>::Insert(S state, T symbol, S data, bool accept)
{
	m_SimuTable.Update(CDFAEntry<T, S>(state, symbol, data));

	if (accept)
		m_AcceptStates.Insert(data); // BinSTree 类不会插入重复的元素
}

template <class T, class S>
S CDFA<T, S>::Move(S state, T symbol)
{
	CDFAEntry<T, S> next(state, symbol, -1);
	m_SimuTable.Query(next);

	return next.m_data;
}

/*
bool CDFA::Simulate(char *string)
{
	int curstate = 0; // 先设为 Start state
	int nextch = 0; // 下一个字符	

	while (curstate != -1 && string[nextch] != '\0') {
		curstate = Move(curstate, string[nextch]);
		nextch++;
	}

	if (!m_AcceptStates.Find(curstate))
		return false;

	return true;
}
*/

#endif  // DFA_CLASS