Генерация случайной строки со сбалансированными скобками

Возникла тут проблемка генерить случайную строку со сбалансированными скобками. Т.е. строка abc(def(g)h)i - сбалансирована, а abc(def(g)hi и abc)(def)g - нет. Код есть, и он работает нормально но есть одна проблемка: почти все строки заканчиваются закрывающими скодками. Где я вижу проблему, и собственно вопрос - под кодом.
char * create_balanced_cstring(const char *alphabet, // строка нейтральных символов (напр abcdefg...) char obr, char cbr, // открывающая и закрывающая скобки unsigned lmin, unsigned lmax) // мин и макс длина строки { if (strchr(alphabet, obr) || strchr(alphabet, cbr)) return 0; if (lmin > lmax || lmin == 0) return 0;
int lenalph = strlen(alphabet); // длина "алфавита" нейтральных символов int length = rand() % (lmax - lmin + 1) + lmin; // длина генерирующейся строки char *s = (char*) malloc(length + 1); if (!s) return s;
int opened = 0; // кол-во открытых скобок int just_opened = 0; // флаг для избегания фрагментов '()' char curchar; // текущий символ в строке for (int i = 0; i < length; ++i) { if (opened == length - i) curchar = cbr; else { if (opened + i + 2 >= length) curchar = alphabet[rand() % lenalph]; else { int r = rand() % length; if (r < opened * 3 && !just_opened) curchar = cbr; else if (r > 2 * length / 3 - opened) curchar = obr; else curchar = alphabet[rand() % lenalph]; } }
if (curchar == obr) { ++opened; just_opened = 1; } else { just_opened = 0; if (curchar == cbr) --opened; }
s[i] = curchar; } s[length] = '\0';
return s; }
Проблема, ИМХО, тут:
int r = rand() % length; if (r < opened * 3 && !just_opened) curchar = cbr; else if (r > length - opened) curchar = obr; else curchar = alphabet[rand() % lenalph];
т.е. с выбором в (условно) начале строки - открывать скобку, закрывать, или ставить случайный символ. Хочется, чтобы вероятность открыть скобку увеличивалась, если их открыто мало и наоборот, закрыть - увеличивалась если открыто много и наоборот. Просто поиграться с коэффициэнтами? Текущие *3 и 2/3 - эмпирические, так вроде еще более-менее.
Т.е. в итоге нужно по 3-м параметрам (длина строки l, текущая позиция i и количество незакрытых в этой позиции скобок o) сделать распределение вероятности выбора открывающей/закрывающей скобки или "нейтрального" символа (не скобки) в данной позиции

Ответ

Посмотрите Кнута, "Искусство программирования", т. 4А, стр. 511 русского издания, алгоритм W - равномерно распределенные случайные строки вложенных скобок. Алгоритм генерирует случайную строку корректно вложенных скобок для заданного их количества.
Растыкать случайным образом 2n мест для скобок в строке, сгенерировать строку скобок и вставить на подготовленные места - не подойдет?