/*
   Filename	: dfascan.cpp
   Author		: Loreto Aquino Jr.
   Date		: Dec 2005
   Subject		: ICSM361 - Theory of Automata and Formal Languages
   Remarks	: This program reads the DFA from an input file and
			  scan a string if it is accepted by the DFA.
*/

// header files
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <conio.h>

// user-defined functions
void readSeries(ifstream &inFile, char *array, char delimeter);
void readStates(ifstream &inFile, char *s_arr, char ns_arr[][50]);
void showDFA(char *a, char start, char *f, char *s, char t[][50]);
int searchArr(char arr[], char symbol);
int validate(char *i, char *a);
void askInput(char *s);

// main function
int main()
{
	ifstream dfa;				// declare input file

	char start_state, next_state, ch;			// variable declarations
	int ndx = 0, state_ndx, alpha_ndx, accepted = 0, validInput;

	char alphabets[50],			                 // data structures
		 states[50],
		 transitions[50][50],
		 final_state[50],
		 string[50];

	clrscr();
	dfa.open("dfa1.dat");				// open input file and check
	if (dfa.fail()) {				// if opening is successful
		cout << "Failed opening input file!" << endl;
		exit(1);
	}

	// read DFA description

	readSeries(dfa, alphabets, ':');			// read alphabets
	dfa.get(start_state);				// read starting state
	dfa.get(ch);				// read carriage return
	readSeries(dfa, final_state, ';');			// read final state(s)

	readStates(dfa, states, transitions); 		// read transition states

	// display DFA to screen
	showDFA(alphabets, start_state, final_state, states, transitions);

	// ask user input for DFA processing
	askInput(string);

	// validate input base on alphabets
	validInput = validate(string, alphabets);

	if (!validInput) {
		cout << endl << "Input contains invalid alphabets!" << endl;
		exit(0);
	}

	// process DFA transition
	state_ndx = searchArr(states, start_state);

	ndx = 0;

	while (string[ndx] != NULL) {
		// get index of input from the alphabets
		alpha_ndx = searchArr(alphabets, string[ndx]);
		// get the transition state base on the given input
		next_state = transitions[state_ndx][alpha_ndx];
		// move to the next state
		state_ndx = searchArr(states, next_state);

		ndx++;  // increment string index

	} // end of DFA process

	// scan string if it is accepted by the DFA
	ndx = 0;

	while (final_state[ndx] != NULL) {		// traverse array to check if
						// the current state is one
		if (final_state[ndx] == next_state)	// of the final state(s)
			accepted = 1;

		ndx++;
	} // end of string scanning

	// display result of scanning
	if (accepted)
		cout << endl << "Accepted!" << endl;
	else
		cout << endl << "Rejected!" << endl;

	dfa.close();				// close input file

	getch();                                			// pause screen to view output
	return 0;                               			// terminate main()

} // end of main()


// function to read input character series
void readSeries(ifstream &inFile, char *array, char delimeter)
{
	char ch;                    			// declare needed variables
	int ndx = 0;

	inFile.get(ch);				// read a character

	while (ch != '\n') { 				// perform until end of line

		if (ch != delimeter) {			// place read character into array if
			array[ndx] = ch;		// it is not equal to the delimeter
			ndx++;
		}
		inFile.get(ch);			// read next character
	}
	array[ndx] = '\0';				// null terminate array

} // end of readSeries()


// function to read DFA transition
void readStates(ifstream &inFile, char *s_arr, char ns_arr[][50])
{
	char state, hypen, greater, next_state;    		// declare needed variables
	int s_ndx = 0, ns_ndx = 0;

	inFile.get(state);				// read first state

	while (state != EOF) {			// loop while end of file is
						// not encountered
		inFile.get(hypen);			// read hypen
		inFile.get(greater);			// read greater than symbol

		s_arr[s_ndx] = state;			// move state to state array

		inFile.get(next_state);		// read transition states

		while (next_state != '\n') {		// loop while end of line is
						// not encountered
			if (next_state != ',') {		// move read character into array
				ns_arr[s_ndx][ns_ndx] = next_state;
				ns_ndx++;		// if it is not a delimeter
			}

			inFile.get(next_state);	// read next transition state

		} // end of while next_state not equal space

		ns_arr[s_ndx][ns_ndx] = '\0';		// null terminate transition array

		s_ndx++;				// increment index for next state
		ns_ndx = 0;			// reinitialize transition index
		inFile.get(state);			// read next state

	} // end of while state not equal EOF

	s_arr[s_ndx] = '\0';				// null terminate state array

} // end of readNextState()


// function to ask for user input
void askInput(char *s)
{
	char ch;                            			// declare needed variables
	int ndx = 0;

	cout << "Enter string:" << endl;			// prompt user to enter string

	do {
		cin.get(ch);			// move user input into a
						// string array
		if (ch != '\n') {
			s[ndx] = ch;
			ndx++;
		}
	} while (ch != '\n');

	s[ndx] = '\0';				// null terminate array

} // end of askInput()


// function to search a character in a given array
int searchArr(char *arr, char symbol)
{
	int ndx = 0;                    			// declare needed variable

	while (arr[ndx] != '\0') {			// search until array is not empty

		if (arr[ndx] == symbol)		// return the element index if the
			return ndx;		// array element matches with the
						// given symbol
		ndx++;
	}

	return -1;                      			// search error trapping

} // end of searchAlphabet()

// function to validate input
int validate(char *i, char *a)
{
	int found = 0;				// declare needed variables
	int i_ndx = 0, a_ndx;

	while (i[i_ndx] != NULL) {			// loop until all input character
		a_ndx = 0;				// are read

		while(a[a_ndx] != NULL) {		// check each input character
			if (i[i_ndx] == a[a_ndx]) {	// against the given alphabet
				found = 1;
				break;
			}
			a_ndx++;
		}

		if (!found)				// return false if the input
			return 0;			// character is not found

		i_ndx++;                        		// increment input index
		found = 0;                      		// reinitialize found flag
	}
	return 1;
} // end of validate()


// function to display the DFA
void showDFA(char *a, char start, char *f, char *s, char t[][50])
{
	int x, y;
	clrscr();					// clears screen and display
						// the screen labels
	cout << "Deterministic Finite Automaton" << endl << endl;
	cout << "Alphabets: ";

	x = 0;
	while (a[x] != NULL) {			// display the alphabets
		cout << a[x] << " ";
		x++;
	}

	cout << endl << endl;				// display start state
	cout << "Start state: " << start << endl << endl;
	cout << "Final state: ";

	x = 0;
	while (f[x] != NULL) {			// display final state(s)
		cout << f[x] << " ";
		x++;
	}

	cout << endl << endl;
	cout << "Transition Table" << endl << endl;

	x = 0;
	y = 0;
	while (s[x] != NULL) {			// display transition table
		cout << s[x] << "-> ";

		while (t[x][y] != NULL) {
			cout << t[x][y] << " ";
			y++;
		}
		x++;
		y = 0;
		cout << endl;
	}
	cout << endl;
 
} // end of displayDFA()