Execute a Markov algorithm: Difference between revisions
Content added Content deleted
(→{{header|Tcl}}: Make the code more compact) |
(C) |
||
Line 98: | Line 98: | ||
should generate the output: |
should generate the output: |
||
: <code>11111111111111111111</code> |
: <code>11111111111111111111</code> |
||
=={{header|C}}== |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
#include <string.h> |
|||
#include <assert.h> |
|||
#define MAX_RULE_LEN 1024 |
|||
#define MAX_STR_LEN 1024 |
|||
typedef struct rulestruct { |
|||
char *trigger; |
|||
char *replacement; |
|||
bool terminal; |
|||
struct rulestruct *next; |
|||
} rule_t; |
|||
rule_t *free_rule(rule_t *r) |
|||
{ |
|||
if ( r == NULL ) return NULL; |
|||
if ( r->trigger != NULL ) free(r->trigger); |
|||
if ( r->replacement != NULL ) free(r->replacement); |
|||
rule_t *next = r->next; |
|||
free(r); |
|||
return next; |
|||
} |
|||
void free_rulelist(rule_t *head) |
|||
{ |
|||
rule_t *n = head; |
|||
while( n != NULL ) n = free_rule(n); |
|||
} |
|||
void readrules(FILE *f, rule_t **ruleset) |
|||
{ |
|||
char buffer[MAX_RULE_LEN]; |
|||
rule_t *t, *prev; |
|||
int i, j; |
|||
size_t l; |
|||
*ruleset = prev = NULL; |
|||
for(l=1; fgets(buffer, MAX_RULE_LEN, f) != NULL; l++ ) |
|||
{ |
|||
if ( buffer[0] == '#' ) continue; // not a rule but a comment |
|||
t = malloc(sizeof(rule_t)); assert( t != NULL ); |
|||
memset(t, 0, sizeof(rule_t)); // just to be sure, in case of failure, to avoid |
|||
// freeing unallocated memory |
|||
// skip blank lines (there cannot be leading spaces...!) |
|||
if ( (buffer[0] == '\n') || (buffer[0] == '\r') ) continue; |
|||
// it's a rule: let's move until the first " -> " |
|||
char *map = strstr(buffer, " -> "); |
|||
if ( map == NULL ) |
|||
{ |
|||
fprintf(stderr, "rule set syntax error line %d\n", l); |
|||
free_rule(t); |
|||
return; |
|||
} |
|||
i = map - buffer + 4; // skip " -> " |
|||
j = map - buffer - 1; |
|||
while( (buffer[j] == ' ') || (buffer[j] == '\t') ) j--; |
|||
buffer[j+1] = 0; |
|||
t->trigger = strdup(buffer); assert( t->trigger != NULL ); |
|||
//skip whitespaces after -> |
|||
for( ; (buffer[i] == '\t') || (buffer[i] == ' '); i++) ; |
|||
if ( buffer[i] == '.' ) |
|||
{ |
|||
t->terminal = true; i++; // terminal rule |
|||
} else { |
|||
t->terminal = false; // or not |
|||
} |
|||
j = i; // store this position and let's find the end |
|||
i += strlen(buffer+j); |
|||
for( i--; (buffer[i] == '\n') || (buffer[i] == '\r') ; i--) ; |
|||
buffer[i+1] = 0; |
|||
t->replacement = strdup(buffer+j); assert(t->replacement != NULL); |
|||
if ( prev == NULL ) |
|||
{ |
|||
*ruleset = t; |
|||
} else { |
|||
prev->next = t; |
|||
} |
|||
prev = t; |
|||
} |
|||
} |
|||
// each line of the file is a "string" |
|||
void markov(FILE *f, rule_t *rule) |
|||
{ |
|||
char buffer[2][MAX_STR_LEN]; // double to allow state changing and no overlapping |
|||
int bi; |
|||
rule_t *r; |
|||
char *p, *d, *bp; |
|||
bool repldone; |
|||
size_t s; |
|||
while( ( fgets(buffer[0], MAX_STR_LEN, f) != NULL ) ) |
|||
{ |
|||
bi = 0; |
|||
do |
|||
{ |
|||
repldone = false; |
|||
for( r = rule; r != NULL; r = r->next, bi++) |
|||
{ |
|||
bp = buffer[bi%2]; |
|||
d = buffer[(bi+1)%2]; |
|||
if ( (p = strstr(bp, r->trigger)) != NULL ) |
|||
{ |
|||
s = p - bp; |
|||
memcpy(d, bp, s); |
|||
strcpy(d + s, r->replacement); |
|||
strcpy(d + strlen(r->replacement) + s, bp + strlen(r->trigger) + s); |
|||
if ( r->terminal ) { |
|||
repldone = false; |
|||
bi++; // let be bi the current (last) buffer |
|||
break; |
|||
} |
|||
repldone = true; // a repl. was done |
|||
r = rule; // since a repl. was done, let's "reset" r |
|||
} else { |
|||
bi--; // stay on the same buffer |
|||
} |
|||
} |
|||
} while( repldone ); |
|||
} |
|||
puts(buffer[(bi)%2]); |
|||
} |
|||
int main(int argc, char **argv) |
|||
{ |
|||
FILE *rulefile_h = NULL; |
|||
FILE *stringfile_h = NULL; |
|||
rule_t *rulelist; |
|||
if ( argc < 3 ) { |
|||
printf("Usage: %s rulefile stringfile\n", argv[0]); |
|||
exit(EXIT_FAILURE); |
|||
} |
|||
rulefile_h = fopen(argv[1], "r"); assert( rulefile_h != NULL ); |
|||
stringfile_h = fopen(argv[2], "r"); assert( stringfile_h != NULL ); |
|||
readrules(rulefile_h, &rulelist); assert( rulelist != NULL ); |
|||
markov(stringfile_h, rulelist); |
|||
// dump rules |
|||
/* |
|||
rule_t *h = rulelist; |
|||
while( h != NULL ) |
|||
{ |
|||
printf("%s -> %s%s\n", h->trigger, h->replacement, h->terminal ? " [TERMINATING RULE]" : ""); |
|||
h = h->next; |
|||
} |
|||
*/ |
|||
free_rulelist(rulelist); |
|||
fclose(rulefile_h); fclose(stringfile_h); |
|||
return EXIT_SUCCESS; |
|||
}</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |