Как отобрать из всех вариантов расставления скобок только математически правильные? У меня задание разместить скобки всеми возможными математически правильными вариантами.
например для варианта ( ){ }[ ] мой код находит :( ) [ ] { }
( ) [ { } ]
( ) { [ ] }
( ) { } [ ]
( [ ] ) { }
( [ ] { } )
( [ { ) ] }
( [ { } ] )
( { [ ) } ]
( { [ ] } )
( { } ) [ ]
( { } [ ] )
[ ( ) ] { }
[ ( ) { } ]
[ ( { ] ) }
[ ( { } ) ]
[ ] ( ) { }
[ ] ( { } )
[ ] { ( ) }
[ ] { } ( )
[ { ( ) } ]
[ { ( ] } )
[ { } ( ) ]
[ { } ] ( )
{ ( ) [ ] }
{ ( ) } [ ]
{ ( [ ] ) }
{ ( [ } ) ]
{ [ ( ) ] }
{ [ ( } ] )
{ [ ] ( ) }
{ [ ] } ( )
{ } ( ) [ ]
{ } ( [ ] )
{ } [ ( ) ]
{ } [ ] ( )
но не могу придумать условие отсеявания вариантов типа "{ [ ( } ] )"
Помогите пожалуйста !
Заранее спасибо !

Предыдущий
вопрос Следующий
вопрос

Для того чтобы отобрать только математически правильные варианты, можно воспользоваться стеком. Алгоритм может быть следующим:

Создать стек для хранения открывающих скобок.Пройти по каждой скобке в варианте.Если текущая скобка - открывающая скобка (скобка '{', '[' или '('), добавить ее в стек.Если текущая скобка - закрывающая скобка (скобка '}', ']' или ')'), проверить соответствует ли она последней открывающей скобке в стеке. Если да, то удалить последнюю открывающую скобку из стека и продолжить проверку. Если нет, то вернуть False.После прохода по всем скобкам варианта, если все открывающие и закрывающие скобки соответствуют друг другу и стек пуст, то вариант является математически правильным и его можно записать.

Пример кода на Python:

def is_valid(s):
stack = []
brackets = {'(':')', '[':']', '{':'}'}
for bracket in s:
if bracket in brackets.keys():
stack.append(bracket)
elif bracket in brackets.values():
if not stack or brackets[stack.pop()] != bracket:
return False
return len(stack) == 0
def generate_valid_variants(res, s, n, current, idx):
if idx == 2*n:
res.append(current)
return
for bracket in s:
new_current = current + bracket
if is_valid(new_current):
generate_valid_variants(res, s, n, new_current, idx+1)
def generate_all_valid_variants(s):
res = []
generate_valid_variants(res, s, len(s)//2, '', 0)
return res
s = '(){}[]'
variants = generate_all_valid_variants(s)
for variant in variants:
print(variant)

Этот код позволит отобрать только математически правильные варианты расстановки скобок из всех возможных вариантов.