diff options
| -rw-r--r-- | 0022/main.c | 150 |
1 files changed, 150 insertions, 0 deletions
diff --git a/0022/main.c b/0022/main.c new file mode 100644 index 0000000..760c7d7 --- /dev/null +++ b/0022/main.c @@ -0,0 +1,150 @@ +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <stdbool.h> + +#define VECTOR_DEF(T) \ + typedef struct { \ + T* buffer; \ + int size; \ + int cap; \ + } T##Vector; \ + \ + void T##Vector_init(T##Vector *self); \ + void T##Vector_push_back(T##Vector *self, T elem); \ + void T##Vector_insert_before(T##Vector *self, int n, T elem); \ + void T##Vector_pop(T##Vector *self); \ + bool T##Vector_empty(T##Vector *self); \ + void T##Vector_remove(T##Vector *self, size_t n); \ + size_t T##Vector_len(T##Vector *self); \ + T* T##Vector_begin(T##Vector *self); \ + T* T##Vector_last(T##Vector *self); \ + T* T##Vector_end(T##Vector *self); \ + T* T##Vector_ref(T##Vector *self, size_t n); \ + void T##Vector_swap(T##Vector *self, int i, int j); \ + T##Vector T##Vector_move(T##Vector *self); \ + void T##Vector_show(T##Vector *self, FILE* fp); \ + void T##Vector_free(T##Vector *self); + +#define VECTOR_IMPL(T) \ + void T##Vector_init(T##Vector *self) { \ + self->buffer = (T*)malloc(sizeof(T) * 16); \ + self->cap = 16; \ + self->size = 0; \ + } \ + \ + void T##Vector_push_back(T##Vector *self, T elem) { \ + if (self->size + 1 > self->cap) { \ + self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \ + self->cap *= 2; \ + } \ + self->buffer[self->size] = elem; \ + self->size += 1; \ + } \ + void T##Vector_insert_before(T##Vector *self, int n, T elem) { \ + if (n < 0 || n > self->size) { \ + return; \ + } \ + if (self->size + 1 > self->cap) { \ + self->buffer = malloc(sizeof(T) * self->cap * 2); \ + self->cap *= 2; \ + } \ + if (n != self->size) { \ + memmove(self->buffer + n + 1, \ + self->buffer + n, \ + sizeof(T) * (self->size - n)); \ + self->buffer[n] = elem; \ + self->size += 1; \ + } \ + } \ + void T##Vector_pop(T##Vector *self) { \ + self->size -= 1; \ + } \ + void T##Vector_remove(T##Vector *self, size_t n) { \ + if (n < 0 || n >= self->size) return; \ + memmove(self->buffer + n, \ + self->buffer + n + 1, \ + sizeof(T) * self->size - n - 1); \ + self->size -= 1; \ + } \ + T* T##Vector_begin(T##Vector *self) { return self->buffer; } \ + bool T##Vector_empty(T##Vector *self) { return self->size == 0; } \ + T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \ + T* T##Vector_last(T##Vector *self) { return self->buffer + self->size - 1; } \ + T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \ + void T##Vector_swap(T##Vector *self, int i, int j) { \ + T buf; \ + memcpy(&buf, self->buffer + i, sizeof(T)); \ + memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \ + memcpy(self->buffer + j, &buf, sizeof(T)); \ + } \ + T##Vector T##Vector_move(T##Vector *self) { \ + T##Vector dup = *self; \ + self->buffer = NULL; \ + self->size = 0; \ + self->cap = 0; \ + return dup; \ + } \ + void T##Vector_show(T##Vector *self, FILE* fp) { \ + fprintf(fp, "["); \ + for (int i = 0; i < self->size-1; i++) { \ + T##_show(&self->buffer[i], fp); \ + fprintf(fp, ", "); \ + } \ + if (self->size > 0) { \ + T##_show(&self->buffer[self->size - 1], fp); \ + } \ + fprintf(fp, "]"); \ + } \ + size_t T##Vector_len(T##Vector *self) { return self->size; } \ + void T##Vector_free(T##Vector *self) { free(self->buffer); } + +typedef char *String; + +void String_show(String *s, FILE *fp) { + fprintf(fp, "%s", *s); +} + +VECTOR_DEF(String); +VECTOR_IMPL(String); + +char *append(char *s, char c) { + int len = strlen(s); + char *ns = malloc(len + 2); + strcpy(ns, s); + ns[len] = c; + ns[len + 1] = '\0'; + return ns; +} + +void gen_impl(StringVector *res, char* current, int n, int unclosed, int finished) { + if (unclosed == 0 && finished == n) { + printf("add: %s\n", current); + StringVector_push_back(res, current); + StringVector_show(res, stdout); + return; + } + if (unclosed > 0) { + gen_impl(res, append(current, ')'), n, unclosed - 1, finished + 1); + } + if (unclosed + finished < n) { + gen_impl(res, append(current, '('), n, unclosed + 1, finished); + } + free(current); +} + +char** generateParenthesis(int n, int* returnSize) { + StringVector result; + StringVector_init(&result); + char *empty = malloc(1); + empty[0] = '\0'; + gen_impl(&result, empty, n, 0, 0); + *returnSize = StringVector_len(&result); + return result.buffer; +} + +int main() { + int size; + generateParenthesis(3, &size); + printf("\n"); +}
\ No newline at end of file |