nfa.h

输入一个正则表达式

#ifndef _NFA_H_
#define _NFA_H_
#include <set>
#include <vector>
#include <iostream>

using namespace std;

typedef set <int>			StateSet;
typedef StateSet::iterator	StateIt;

class NFA
{
private:
	typedef StateSet				   *StateItem;
	typedef vector <StateItem>			StateTranTable;
	typedef StateTranTable::iterator	StateTranIt;

	// Create a new item, return the index of the new item
	int		newItem();

	// add a new item from another one, return the index of the new item
	int		addItem(StateItem si);

	// Destroy STT
	void	destroySTT();

	// move a NFA connected to this, and modify the state sequence
	void	merge(NFA *n);

	// add a fix number to each element of the set
	void	addSet(StateSet &ss, int num);

	// get Item connected to ss
	StateItem getConnect(StateSet &ss);

	// add Item si to all elements in ss
	void	addConnect(StateSet &ss, StateItem si);

	// copy the connection of src to dest
	void	copyConnection(StateSet &dest, StateSet &src);

	// Make a dead state item that all connection point to itself
	int		newDeadItem();
protected:
	int				alphaSize;
	StateSet		Q, F;
	StateTranTable	STT;
	int				STTSize;
public:
	NFA(int _alphaSize);
	~NFA();
	
	// Make a dead state that all empty sets are connected to
	int		makeDeadState();

	// NFA operation
	void unionSet(NFA *n);
	void intersectionSet(NFA *n);
	void join(NFA *n);
	void complementSet();
	void closure();

	// basic NFA of regular expression
	void emptyStr();
    void emptySet();
    void alphabet(int c);
	
	friend class DFA;
	// Out NFA State Transition Table(STT)
	friend ostream& operator<<(ostream &os, NFA *n);
};
// out State set
ostream& operator<<(ostream &os, StateSet &ss);

// test if set A intersect set B
int		intersect(StateSet &A, StateSet &B);

#endif