Brace expansion: Difference between revisions
Content added Content deleted
m (Added a link to the related task 'Brace expansion using ranges') |
|||
Line 450: | Line 450: | ||
{}} some {\\edge }{ cases, here\\\} |
{}} some {\\edge }{ cases, here\\\} |
||
{}} some {\\edgy }{ cases, here\\\}</pre> |
{}} some {\\edgy }{ cases, here\\\}</pre> |
||
=={{header|C}}== |
|||
Handles only properly formed input. |
|||
<lang c>#include <stdbool.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#define BUFFER_SIZE 128 |
|||
typedef unsigned char character; |
|||
typedef character *string; |
|||
typedef struct node_t node; |
|||
struct node_t { |
|||
enum tag_t { |
|||
NODE_LEAF, |
|||
NODE_TREE, |
|||
NODE_SEQ, |
|||
} tag; |
|||
union { |
|||
string str; |
|||
node *root; |
|||
} data; |
|||
node *next; |
|||
}; |
|||
node *allocate_node(enum tag_t tag) { |
|||
node *n = malloc(sizeof(node)); |
|||
if (n == NULL) { |
|||
fprintf(stderr, "Failed to allocate node for tag: %d\n", tag); |
|||
exit(1); |
|||
} |
|||
n->tag = tag; |
|||
n->next = NULL; |
|||
return n; |
|||
} |
|||
node *make_leaf(string str) { |
|||
node *n = allocate_node(NODE_LEAF); |
|||
n->data.str = str; |
|||
return n; |
|||
} |
|||
node *make_tree() { |
|||
node *n = allocate_node(NODE_TREE); |
|||
n->data.root = NULL; |
|||
return n; |
|||
} |
|||
node *make_seq() { |
|||
node *n = allocate_node(NODE_SEQ); |
|||
n->data.root = NULL; |
|||
return n; |
|||
} |
|||
void deallocate_node(node *n) { |
|||
if (n == NULL) { |
|||
return; |
|||
} |
|||
deallocate_node(n->next); |
|||
n->next = NULL; |
|||
if (n->tag == NODE_LEAF) { |
|||
free(n->data.str); |
|||
n->data.str = NULL; |
|||
} else if (n->tag == NODE_TREE || n->tag == NODE_SEQ) { |
|||
deallocate_node(n->data.root); |
|||
n->data.root = NULL; |
|||
} else { |
|||
fprintf(stderr, "Cannot deallocate node with tag: %d\n", n->tag); |
|||
exit(1); |
|||
} |
|||
free(n); |
|||
} |
|||
void append(node *root, node *elem) { |
|||
if (root == NULL) { |
|||
fprintf(stderr, "Cannot append to uninitialized node."); |
|||
exit(1); |
|||
} |
|||
if (elem == NULL) { |
|||
return; |
|||
} |
|||
if (root->tag == NODE_SEQ || root->tag == NODE_TREE) { |
|||
if (root->data.root == NULL) { |
|||
root->data.root = elem; |
|||
} else { |
|||
node *it = root->data.root; |
|||
while (it->next != NULL) { |
|||
it = it->next; |
|||
} |
|||
it->next = elem; |
|||
} |
|||
} else { |
|||
fprintf(stderr, "Cannot append to node with tag: %d\n", root->tag); |
|||
exit(1); |
|||
} |
|||
} |
|||
size_t count(node *n) { |
|||
if (n == NULL) { |
|||
return 0; |
|||
} |
|||
if (n->tag == NODE_LEAF) { |
|||
return 1; |
|||
} |
|||
if (n->tag == NODE_TREE) { |
|||
size_t sum = 0; |
|||
node *it = n->data.root; |
|||
while (it != NULL) { |
|||
sum += count(it); |
|||
it = it->next; |
|||
} |
|||
return sum; |
|||
} |
|||
if (n->tag == NODE_SEQ) { |
|||
size_t prod = 1; |
|||
node *it = n->data.root; |
|||
while (it != NULL) { |
|||
prod *= count(it); |
|||
it = it->next; |
|||
} |
|||
return prod; |
|||
} |
|||
fprintf(stderr, "Cannot count node with tag: %d\n", n->tag); |
|||
exit(1); |
|||
} |
|||
void expand(node *n, size_t pos) { |
|||
if (n == NULL) { |
|||
return; |
|||
} |
|||
if (n->tag == NODE_LEAF) { |
|||
printf(n->data.str); |
|||
} else if (n->tag == NODE_TREE) { |
|||
node *it = n->data.root; |
|||
while (true) { |
|||
size_t cnt = count(it); |
|||
if (pos < cnt) { |
|||
expand(it, pos); |
|||
break; |
|||
} |
|||
pos -= cnt; |
|||
it = it->next; |
|||
} |
|||
} else if (n->tag == NODE_SEQ) { |
|||
size_t prod = pos; |
|||
node *it = n->data.root; |
|||
while (it != NULL) { |
|||
size_t cnt = count(it); |
|||
size_t rem = prod % cnt; |
|||
expand(it, rem); |
|||
it = it->next; |
|||
} |
|||
} else { |
|||
fprintf(stderr, "Cannot expand node with tag: %d\n", n->tag); |
|||
exit(1); |
|||
} |
|||
} |
|||
string allocate_string(string src) { |
|||
size_t len = strlen(src); |
|||
string out = calloc(len + 1, sizeof(character)); |
|||
if (out == NULL) { |
|||
fprintf(stderr, "Failed to allocate a copy of the string."); |
|||
exit(1); |
|||
} |
|||
strcpy(out, src); |
|||
return out; |
|||
} |
|||
node *parse_seq(string input, size_t *pos); |
|||
node *parse_tree(string input, size_t *pos) { |
|||
node *root = make_tree(); |
|||
character buffer[BUFFER_SIZE] = { 0 }; |
|||
size_t bufpos = 0; |
|||
size_t depth = 0; |
|||
bool asSeq = false; |
|||
bool allow = false; |
|||
while (input[*pos] != 0) { |
|||
character c = input[(*pos)++]; |
|||
if (c == '\\') { |
|||
c = input[(*pos)++]; |
|||
if (c == 0) { |
|||
break; |
|||
} |
|||
buffer[bufpos++] = '\\'; |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} else if (c == '{') { |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
asSeq = true; |
|||
depth++; |
|||
} else if (c == '}') { |
|||
if (depth-- > 0) { |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} else { |
|||
if (asSeq) { |
|||
size_t new_pos = 0; |
|||
node *seq = parse_seq(buffer, &new_pos); |
|||
append(root, seq); |
|||
} else { |
|||
append(root, make_leaf(allocate_string(buffer))); |
|||
} |
|||
break; |
|||
} |
|||
} else if (c == ',') { |
|||
if (depth == 0) { |
|||
if (asSeq) { |
|||
size_t new_pos = 0; |
|||
node *seq = parse_seq(buffer, &new_pos); |
|||
append(root, seq); |
|||
bufpos = 0; |
|||
buffer[bufpos] = 0; |
|||
asSeq = false; |
|||
} else { |
|||
append(root, make_leaf(allocate_string(buffer))); |
|||
bufpos = 0; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
} else { |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
} else { |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
} |
|||
return root; |
|||
} |
|||
node *parse_seq(string input, size_t *pos) { |
|||
node *root = make_seq(); |
|||
character buffer[BUFFER_SIZE] = { 0 }; |
|||
size_t bufpos = 0; |
|||
while (input[*pos] != 0) { |
|||
character c = input[(*pos)++]; |
|||
if (c == '\\') { |
|||
c = input[(*pos)++]; |
|||
if (c == 0) { |
|||
break; |
|||
} |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} else if (c == '{') { |
|||
node *tree = parse_tree(input, pos); |
|||
if (bufpos > 0) { |
|||
append(root, make_leaf(allocate_string(buffer))); |
|||
bufpos = 0; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
append(root, tree); |
|||
} else { |
|||
buffer[bufpos++] = c; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
} |
|||
if (bufpos > 0) { |
|||
append(root, make_leaf(allocate_string(buffer))); |
|||
bufpos = 0; |
|||
buffer[bufpos] = 0; |
|||
} |
|||
return root; |
|||
} |
|||
void test(string input) { |
|||
size_t pos = 0; |
|||
node *n = parse_seq(input, &pos); |
|||
size_t cnt = count(n); |
|||
size_t i; |
|||
printf("Pattern: %s\n", input); |
|||
for (i = 0; i < cnt; i++) { |
|||
expand(n, i); |
|||
printf("\n"); |
|||
} |
|||
printf("\n"); |
|||
deallocate_node(n); |
|||
} |
|||
int main() { |
|||
test("~/{Downloads,Pictures}/*.{jpg,gif,png}"); |
|||
test("It{{em,alic}iz,erat}e{d,}, please."); |
|||
test("{,{,gotta have{ ,\\, again\\, }}more }cowbell!"); |
|||
//not sure how to parse this one |
|||
//test("{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\}"); |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Pattern: ~/{Downloads,Pictures}/*.{jpg,gif,png} |
|||
~/Downloads/*.jpg |
|||
~/Pictures/*.gif |
|||
~/Downloads/*.png |
|||
~/Pictures/*.jpg |
|||
~/Downloads/*.gif |
|||
~/Pictures/*.png |
|||
Pattern: It{{em,alic}iz,erat}e{d,}, please. |
|||
Itemized, please. |
|||
Italicize, please. |
|||
Iterated, please. |
|||
Itemize, please. |
|||
Italicized, please. |
|||
Iterate, please. |
|||
Pattern: {,{,gotta have{ ,\, again\, }}more }cowbell! |
|||
cowbell! |
|||
more cowbell! |
|||
gotta have more cowbell! |
|||
gotta have\, again\, more cowbell!</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |