# algorithm – task: is it possible to continue the fragment in both directions?

## Question:

The task from the area of ​​"algorithms and data structures".

You are given a fragment of a sequence of brackets consisting of characters

`````` (){}[]
``````

It is required to determine whether it is possible to continue the fragment in both directions, having received the correct sequence. If possible – print the minimum correct sequence, otherwise – print "IMPOSSIBLE". The maximum string length is 10 ^ 6 characters.

Sample Input 1:

``````}[[([{[]}
``````

Sample Output 1:

``````{}[[([{[]}])]]
``````

Sample Input 2:

``````{][[[[{}[]
``````

IMPOSSIBLE

Ideas:

There is a standard algorithm for checking the correctness of the placement of parentheses, implemented through the stack. The bottom line is as follows:

• we go along the line, if we meet an open parenthesis, we push it onto the stack
• if we meet a closing parenthesis and there is a similar opening parenthesis at the top of the stack, then remove it (opening) from the stack
• if after the passage of the entire line the stack is empty, then the parentheses are placed correctly.

To solve this problem, this algorithm needs to be modified to make it possible (or determine the impossibility) of complementing the checked string to the correct one.

To do this, I tried to start counters for each bracket and its direction and keep the opposite bracket in the deck and remove it from the deck at the right time. But so far everything is covered by ifs and the algorithm still does not work correctly

` `class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() posible = True cin = input() a=Stack() s=Stack() for i in cin: if ( i == '(' or i == '[' or i == '{' ): s.push( i ) if ( i == ')' or i == ']' or i == '}'): if s.isEmpty(): a.push(i) else: temp = s.pop() if (i == ')' and temp != '(') or (i == ']' and temp != '[') or (i == '}' and temp != '{'): posible = False break if posible: while not a.isEmpty(): temp = a.pop() if temp == ']': temp = '[' if temp == ')': temp = '(' if temp == '}': temp = '{' print(temp, end = '') print(cin, end = '') while not s.isEmpty(): temp = s.pop() if temp == '[': temp = ']' if temp == '(': temp = ')' if temp == '{': temp = '}' print(temp, end = '') else: print('IMPOSSIBLE')``