I just got done coding this C program:
Read the description of a deterministic finite automaton from standard input.
The first line of input is the number of states in the automaton, n
n lines follow, each one describing a state. Each line is composed of the name of the state, followed by its transitions, colon-separated. A transition is indicated like
(S,c)
and means that the automaton will move to state S upon reading the character c.If the name of a state begins with F, it's a terminal state. For example,
F1;(A,b);(C,d)
is a terminal state and the automaton will move to state A upon reading characer b, and to state C upon reading character d. The name of a state can be 10 characters long at most.After having read all the states, the program will read lines of text from standard input, until the line
STOP
is input. For every line, the automaton will determine if it belongs to the described language and, if it does, will echo it back.Note: the program must not print anything but the recognized lines to standard output.
I thought it was an interesting problem. A few notes:
There are no error messages to handle ill-formed input. We were required by those who gave us the assignment to focus on solving the problem, rather than making it become an input-checking exercise. So I'll pretty much assume the input is well-formatted throughout the program
There are no prompt texts like
Number of states?
due to the program being corrected by an automatic platform that matches the exepcted output with the one from the program.
My program passed the tests on that platform so it works. What I'm interested in is, what could I have done to improve the code? Thank you!
Code
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define SNL 10 // maximum number of characters in a state's name
typedef struct transition {
char c;
char *newState;
struct transition *nextPtr;
} Transition;
typedef struct state {
char *sName;
Transition *tList;
} State;
int getNStates() { // gets the number of states in the automaton
int n;
if(scanf("%d", &n) != 1 || n <= 0) {
exit(1);
}
return n;
}
State *createNewState(char stateName[]) { // creates a new state with the specified name and returns it
State *newState = malloc(sizeof(State));
if(newState == NULL) exit(1);
newState->sName = malloc(sizeof(char) * SNL);
if(newState->sName == NULL) exit(1);
strcpy(newState->sName, stateName);
newState->tList = NULL;
return newState;
}
void appendTransition(Transition **tList, char *newS, char ch) { // appends a new transition to the existing list, recursively
if(*tList == NULL) {
*tList = malloc(sizeof(Transition));
if(tList == NULL) exit(1);
(*tList)->newState = malloc(sizeof(char) * strlen(newS)); // allocate memory for new state's name
if((*tList)->newState == NULL) exit(1);
strcpy((*tList)->newState, newS); // initialize new transition
(*tList)->c = ch;
(*tList)->nextPtr = NULL;
} else {
appendTransition(&((*tList)->nextPtr), newS, ch);
}
}
State *move(State **automaton, int nStates, State *currState, char ch) { // returns a state if transition is found, NULL is no transition is found
Transition *tList = currState->tList;
if(tList == NULL) return NULL;
while(tList != NULL) {
if(tList->c == ch) { // found correct transition
for(size_t i = 0; i < nStates; i++) {
if(!strcmp(automaton[i]->sName, tList->newState)) { // find the correct state in the table
return automaton[i];
}
}
}
tList = tList->nextPtr;
}
return NULL;
}
int evaluate(State **automaton, int nStates, char *line) {
if(*automaton == NULL) {
return 1;
}
State *st = automaton[0]; // initial state is the first state
for(size_t i = 0; i < strlen(line); i++) {
st = move(automaton, nStates, st, line[i]); // transition to the next state
if(st == NULL) {
return 0;
}
}
if(st->sName[0] == 'F') { // if state name begins with 'F', it's a terminal state
return 1;
}
return 0;
}
int main() {
int n = getNStates();
char stateName[SNL]; // used to store current state's name
char newState[SNL]; // used to store newState's name for every transition
char c; // used to store character that leads to newState for every transition
char line[100]; // used to store current line of text
State **automaton = malloc(n*sizeof(State)); // create the automaton table
if(automaton == NULL) exit(1);
while(getchar() != '\n'); // clear buffer
for(size_t i = 0; i < n; i++) { // get as many lines of text as there are states
scanf("%[^\n]", line);
automaton[i] = malloc(sizeof(State)); // allocate memory for new state
if(automaton[i] == NULL) exit(1);
char *token = strtok(line, ";"); // first token is the state name
automaton[i]->sName = malloc(sizeof(char) * (strlen(token) + 1)); // allocate memory for state name
if(automaton[i]->sName == NULL) exit(1);
strcpy(automaton[i]->sName, token); // copy state name into the table
automaton[i]->tList = NULL; // initialize current state transition table
while(token = strtok(NULL, ";")) { // keep reading as long as there are transitions
sscanf(token, "(%[^,],%c)", newState, &c);
appendTransition(&(automaton[i]->tList), newState, c); // append new transition to state's list
}
while(getchar() != '\n'); // clear buffer
}
scanf("%100s", line); // read a line
while(strcmp(line,"STOP")) { // keep reading lines until you encounter "STOP"
if(evaluate(automaton, n, line)) { // print the line of text if it's recognized by the automaton
puts(line);
}
scanf("%100s", line); // read a line
}
return 0;
}
Example inputs/outputs:
test case 1
input:
5
A;(A,a);(B,c)
B;(A,a);(C,b);(B,c);(F2,k)
C;(F1,d);(A,a);(B,c)
F1;(C,b)
F2;
akcdbbbbc
cacack
cacbd
STOP
output:
cacack
cacbd
test case 2
input:
3
S1;(S1,b);(S2,a)
S2;(S1,f);(F1,d);(S2,c)
F1;(S2,e);(F1,x)
bbafacccdedxxedx
x
bad
STOP
output:
bbafacccdedxxedx
bad
test case 3
input:
1
F1;(F1,a)
a
aaa
bad
ab
STOP
output:
a
aaa