读取确定性有限自动机的描述并构建它的C程序。

Question

我刚编写完这个C程序：

从标准输入中读取确定性有限自动机的描述。输入的第一行是自动机中的状态数，后面是n行，每一行描述一个状态。每一行都由状态的名称组成，然后是以冒号分隔的转换.转换类似于(S,c)，这意味着当读取字符c时，自动机将移动到状态S。如果状态的名称以F开头，则表示为结束状态。例如，F1;(A,b);(C,d)是一个终端状态，自动机将在读取字符b时移动到状态A，在读取字符d时移动到状态C，状态的名称最多可以是10个字符。在读取了所有状态后，程序将从标准输入中读取一行文本，直到输入行STOP。对于每一行，自动机将确定它是否属于所描述的语言，如果它属于，则会回显它。注:该程序不得打印任何东西，但认可的行，以标准输出。

我觉得这是个有趣的问题。几个注意事项：

1. 没有处理格式错误输入的错误消息.那些给我们分配任务的人要求我们集中精力解决问题，而不是把它变成一个输入检查练习。因此，我将假设输入在整个程序中都有良好的格式。
2. 没有像Number of states?这样的提示文本，因为程序被一个自动平台纠正，该平台将输出的输出与程序的输出相匹配。

我的程序在那个平台上通过了测试，所以它能工作。我感兴趣的是，我能做些什么来改进代码呢？谢谢!

代码

#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;
}

输入/输出实例：

测试用例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

测试用例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

测试用例3

input:
1
F1;(F1,a)
a
aaa
bad
ab
STOP

output:
a
aaa

Answer 1

总的来说，代码检查malloc()，有时检查scanf()是否有错误，通常在if语句和循环中使用大括号包装逻辑。这些函数一般都遵循Single Responsibility Principle。

不清楚为什么函数createNewState()是未使用的，因为这将大大简化main()函数。

应该有一个函数createNewTransition()来处理创建转换，这将简化void appendTransition(Transition **tList, char *newS, char ch)中的代码。

递归在void appendTransition(Transition **tList, char *newS, char ch)中是不必要的，在while循环中查找列表中的最后一个转换非常容易。

可读性

结构/类型名称很好，因为它们是描述性的。

由于stdlib.h已经包含在malloc()中，所以最好使用EXIT_SUCCESS和EXIT_FAILURE作为退出状态。

int main() {

...

    if(automaton == NULL) exit(EXIT_FAILURE);

    ...

    return EXIT_SUCCESS;
}

变量名n并不像它可能描述的那样具有描述性，因为获取状态数的函数称为getNStates() --变量可以称为nStates。

向用户通报

程序即使期望用户输入，也不会提示用户输入，程序也不会报告错误，只有在出现错误时才会退出。

应该提示用户输入，并将错误报告添加到错误处理中。

void  reportErrorAndQuit(char *emsg)
{
    fprintf(stderr, emsg);
    exit(EXIT_FAILURE);
}

int readNStates(){
    int nStates = 0;

    printf("Please enter the number of states in the automaton, the number of states must be greater than zero.\n");

    int scanfStatus = scanf("%d", &nStates);
    if (scanfStatus < 1 || scanfStatus == EOF) {
        reportErrorAndQuit("Unable to read input, exiting program\n");
    }

    return nStates;
}

int getNStates() { // gets the number of states in the automaton
    int nStates = 0;

    while  (nStates <= 0) {
        nStates = readNStates();
    }

    return nStates;
}

调用exit()

通常使用的方法并不是从exit(int exitStatus)调用main()为简单的return exitStatus;。从exit()以外的函数调用main()，因为其他函数不会将值返回到操作系统。

从stdin

读取输入行

C库提供了两个函数，用于读取一行输入，这可能比使用scanf("%[^\n]", line);更好。这些函数是焦炭*输入_缓冲器，int最大值_缓冲器_大小，档案*溪流)和gets(char *input_buffer)。函数fgets()被认为更安全，因为缓冲区大小是已知的，并且不会有缓冲区溢出。

        size_t charsRecieved = fgets(line, 100, stdin);
        if (size_t < 1) reportErrorAndQuit("Can't line read input from stdin\n");

在stdio.h中定义了一个常量，常与fgets()一起使用，这个常数是BUFSIZE，它与系统有关，通常是可以读取的最大行。

如果使用函数fgets()，则代码不必在scanf()之后清除输入缓冲区。

状态*移动( State **automaton，int nStates，State *currState，char ch)

在这个函数中，行

    if(tList == NULL) return NULL;

如果没有必要，while循环中的条件将处理这种情况，如果tList是NULL，则代码将不会进入循环。