turing.c (2473B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdbool.h> 5 6 typedef struct node { 7 int id; 8 bool end; 9 } node; 10 11 typedef struct connection { 12 node *parrent; 13 char input; 14 char output; 15 int offset; 16 node *result; 17 } connection; 18 19 node nodes[128]; 20 int nodecount = 0; 21 22 connection connections[1024]; 23 int connectioncount = 0; 24 25 void perror(const char *msg) { 26 fprintf(stderr, "%s\n", msg); 27 exit(1); 28 } 29 30 node *findnode(int id) { 31 for (int i = 0; i < nodecount; i++) 32 if (nodes[i].id == id) return &nodes[i]; 33 return NULL; 34 } 35 36 int main(int argc, char **argv) { 37 if (argc <= 1) perror("no file given"); 38 39 FILE *f = fopen(argv[1], "r"); 40 if (f == NULL) perror("failed to open file"); 41 42 /* define nodes */ 43 char *line = malloc(128); 44 while (fgets(line, 128, f)[0] == '#') continue; /* handles comments */ 45 46 char *tok = strtok(line, " "); 47 while (tok != NULL) { 48 if (tok[0] == 'e') { 49 nodes[nodecount].end = true; 50 tok++; 51 } 52 nodes[nodecount].id = atoi(tok); 53 nodecount++; 54 tok = strtok(NULL, " "); 55 } 56 57 /* define connections */ 58 node *parrent, *result; 59 comment: 60 while (fgets(line, 128, f) != NULL) { 61 if (line[0] == '#' || line[0] == '\n') goto comment; 62 63 char *tok = strtok(line, " "); 64 if ((parrent = findnode(atoi(tok))) == NULL) perror("unknown node specified"); 65 connections[connectioncount].parrent = parrent; 66 67 tok = strtok(NULL, " "); 68 if (tok[0] == '#') connections[connectioncount].input = 0; 69 else connections[connectioncount].input = tok[0]; 70 71 tok = strtok(NULL, " "); 72 if (tok[0] == '#') connections[connectioncount].output = 0; 73 else connections[connectioncount].output = tok[0]; 74 75 tok = strtok(NULL, " "); 76 connections[connectioncount].offset = atoi(tok); 77 78 tok = strtok(NULL, " "); 79 if ((result = findnode(atoi(tok))) == NULL) perror("unknown node specified"); 80 connections[connectioncount].result = result; 81 82 connectioncount++; 83 } 84 85 char tape[4096] = {0}; 86 if (argc >= 3) strcat(tape, argv[2]); /* fill the tape with user input, if they give it */ 87 88 char *head = tape; 89 node *current = &nodes[0]; 90 91 for (;;) { 92 success: 93 for (int i = 0; i < connectioncount; i++) { 94 if (connections[i].parrent == current && connections[i].input == *head){ 95 *head = connections[i].output; 96 current = connections[i].result; 97 head += connections[i].offset; 98 goto success; 99 } 100 } 101 printf("%s\n", tape); 102 printf("%s\n", (current->end) ? "accept" : "reject"); /* did it end in a valid location */ 103 break; 104 } 105 106 return 0; 107 }