-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathA_bracket_generator.py
75 lines (61 loc) · 3.52 KB
/
A_bracket_generator.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
"""
A. Генератор скобок
Рита по поручению Тимофея наводит порядок в правильных скобочных
последовательностях (ПСП), состоящих только из круглых скобок ().
Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке
—– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все
ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов.
Таких всего две:
1. (())
2. ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на
второй позиции у первой ПСП стоит (, который идёт раньше ).
Формат ввода
На вход функция принимает n — целое число от 0 до 10.
Формат вывода
Функция должна напечатать все возможные скобочные последовательности
заданной длины в алфавитном (лексикографическом) порядке.
Пример 1
Ввод
3
Вывод
((()))
(()())
(())()
()(())
()()()
"""
def bracket_generator(n):
"""
Эта функция использует вспомогательную функцию generate_brackets,
которая принимает четыре аргумента:
`s:` текущая последовательность скобок, сгенерированная на данный момент
`n:` желаемая длина конечной последовательности скобок
`open_count:` количество открытых скобок, уже имеющихся в
последовательности
`close_count:` количество закрывающих скобок, уже имеющихся в
последовательности.
"""
def generate_brackets(s, n, open_count, close_count):
"""
Функция generate_brackets использует рекурсивный подход для генерации
всех возможных последовательностей скобок. На каждом шаге он проверяет,
достигла ли текущая последовательность желаемой длины 2n. Если да, то
он печатает последовательность. Если нет, он добавляет открытую скобку,
если количество открытых скобок меньше n, и добавляет закрывающую
скобку, если количество закрытых скобок меньше количества открытых
скобок.
"""
if len(s) == 2 * n:
print(s)
return
if open_count < n:
generate_brackets(s + "(", n, open_count + 1, close_count)
if close_count < open_count:
generate_brackets(s + ")", n, open_count, close_count + 1)
generate_brackets("", n, 0, 0)
if __name__ == '__main__':
n = int(input())
bracket_generator(n)