Skip to content

Instantly share code, notes, and snippets.

@draftcode
Last active January 2, 2016 06:49
Show Gist options
  • Save draftcode/8266146 to your computer and use it in GitHub Desktop.
Save draftcode/8266146 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct _node {
char c;
struct _node *tr;
struct _node *next;
} node;
node *create_node(char c, node *tr, node *next) {
node *ret = malloc(sizeof(node));
ret->c = c;
ret->tr = tr;
ret->next = next;
return ret;
}
// -----------------------------------------------------------------------------
// expr ::= term | term + expr
// term ::= factor | factor term
// factor ::= atom | atom *
// atom ::= a-z | (expr)
bool expr(const char **pattern, node **head, node **tail);
bool term(const char **pattern, node **head, node **tail);
bool factor(const char **pattern, node **head, node **tail);
bool atom(const char **pattern, node **head, node **tail);
bool expr(const char **pattern, node **r_head, node **r_tail) {
node *head1, *tail1;
bool ret = term(pattern, &head1, &tail1);
if (!ret) return false;
if (**pattern == '+') {
(*pattern)++;
node *head2, *tail2;
expr(pattern, &head2, &tail2);
// head1 tail1
// -> O -eps-> O -...-> O -> O -eps->
// | ^
// +--eps-> O -...-> O ---+
// head2 tail2
node *head, *tail;
head = create_node(-1, head1, create_node(-1, head2, NULL));
tail = create_node(-1, NULL, NULL);
tail1->tr = tail;
tail2->tr = tail;
*r_head = head;
*r_tail = tail;
} else {
*r_head = head1;
*r_tail = tail1;
}
return true;
}
bool term(const char **pattern, node **r_head, node **r_tail) {
node *head, *tail;
bool ret = factor(pattern, &head, &tail);
if (!ret) return false;
node *n_head, *n_tail;
ret = term(pattern, &n_head, &n_tail);
if (!ret) {
*r_head = head;
*r_tail = tail;
} else {
tail->tr = n_head;
*r_head = head;
*r_tail = n_tail;
}
return true;
}
bool factor(const char **pattern, node **r_head, node **r_tail) {
node *head, *tail;
bool ret = atom(pattern, &head, &tail);
if (!ret) return false;
if (**pattern == '*') {
(*pattern)++;
// head tail
// -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
// | ^ | ^
// | +-----------eps--------+ |
// +--------------------eps-----------------+
tail->tr = create_node(-1, NULL, NULL);
tail = tail->tr;
head = create_node(-1, head, NULL);
tail->next = create_node(-1, head, tail->next);
// head tail
// -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
// | ^ | ^
// | +-----------eps--------+ |
// +--------------------eps-----------------+
tail->tr = create_node(-1, NULL, NULL);
tail = tail->tr;
head = create_node(-1, head, NULL);
head->next = create_node(-1, tail, head->next);
// head tail
// -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
// | ^ | ^
// | +-----------eps--------+ |
// +--------------------eps-----------------+
}
*r_head = head;
*r_tail = tail;
return true;
}
bool atom(const char **pattern, node **r_head, node **r_tail) {
if (**pattern == '(') {
const char *saved_pos = *pattern;
(*pattern)++;
if (expr(pattern, r_head, r_tail)) {
if (**pattern == ')') {
(*pattern)++;
return true;
}
}
*pattern = saved_pos;
return false;
} else if ('a' <= **pattern && **pattern <= 'z') {
node *n = create_node(**pattern, NULL, NULL);
(*pattern)++;
*r_head = n;
*r_tail = n;
return true;
}
return false;
}
// -----------------------------------------------------------------------------
bool match_node(node *n, const char *s) {
if (n == NULL || *s == '\0') {
return (n == NULL && *s == '\0');
}
while (n != NULL) {
if (n->c == *s) {
if (match_node(n->tr, s+1)) return true;
} else if (n->c == -1) {
if (match_node(n->tr, s)) return true;
}
n = n->next;
}
return false;
}
bool match(const char *pattern, const char *str) {
node *head, *tail;
if (!expr(&pattern, &head, &tail) || *pattern != '\0') {
fprintf(stderr, "syntax error\n");
exit(1);
} else {
return match_node(head, str);
}
}
int main(int argc, char* argv[]) {
const char *pattern = "(a+b+c+d)*e";
const char *str = "aaaaaaaaaaaabcde";
if (match(pattern, str)) {
printf("'%s' matches '%s'\n", str, pattern);
} else {
printf("'%s' does not match '%s'\n", str, pattern);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment