Упражнения на C: создание всех комбинаций правильно сформированных скобок из n заданных пар скобок

Программирование на C: Упражнение 11 с решением

Напишите C-программирование для генерации всех комбинаций правильно сформированных скобок из n заданных пар скобок.

 Пример: 
Вход n = 5
Выход: 
(() ()) (())
(() ()) () ()
(()) ((()))
(()) (() ())
(()) (()) ()
(()) () (())
(()) () () ()
() (((())))
() ((() ()))
() ((()) ())
() ((())) ()
() (() (()))
() (() () ())
() (() ()) ()
() (()) (())
() (()) () ()
() () ((()))
() () (() ())
() () (()) ()
() () () (())
() () () () ()

Код C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static char** generate_Parenthesis(int n, int* returnSize)
{
    int left_num, right_num, cap = 5000, ctr = 0;
    char *stack = malloc(2 * n + 1);
    char **parentheses = malloc(cap * sizeof(char *));
    char *p = stack;
    left_num = right_num = 0;
    stack[2 * n] ='\0';
    while (p != stack || ctr == 0) {
        if (left_num == n && right_num == n) {
            parentheses[ctr] = malloc(2 * n + 1);
            strcpy(parentheses[ctr], stack);
            ctr++;
            while (--p != stack) {
                if (*p =='(') {
                    if (--left_num > right_num) {
                        *p++ =')';
                        right_num++;
                        break;
                    }
                } else {
                    right_num--;
                }
            }
        } else {
            /* forward */
            while (left_num < n) {
                *p++ ='(';
                left_num++;
            }
            while (right_num < n) {
                *p++ =')';
                right_num++;
            }
        }
    }
    *returnSize = ctr;
    return parentheses;
}
int main(void)
{
    int i, ctr;
    i = 5;
    char ** lists = generate_Parenthesis(i, &ctr);
    for (i = 0; i < ctr; i++) {
        printf("%s\n", lists[i]);
    }
    return 0;
}

Пример вывода:

 ((((()))))
(((() ())))
(((()) ()))
(((())) ())
(((()))) ()
((() (())))
((() () ()))
((() ()) ())
((() ())) ()
((()) (()))
((()) () ())
((()) ()) ()
((())) (())
((())) () ()
(() ((())))
(() (() ()))
(() (()) ())
(() (())) ()
(() () (()))
(() () () ())
(() () ()) ()
(() ()) (())
(() ()) () ()
(()) ((()))
(()) (() ())
(()) (()) ()
(()) () (())
(()) () () ()
() (((())))
() ((() ()))
() ((()) ())
() ((())) ()
() (() (()))
() (() () ())
() (() ()) ()
() (()) (())
() (()) () ()
() () ((()))
() () (() ())
() () (()) ()
() () () (())
() () () () ()

Блок - схема:

Решение

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на C, чтобы проверить, является ли данная строка действительной или нет, строка содержит символы '(', ')', '{', '}', '[' и ']'. Строка действительна, если открытые скобки должны быть закрыты скобками того же типа и в правильном порядке.
Далее: Напишите программу на C для удаления дубликатов из заданного массива целых чисел.