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
Answer:
Greetings from Stepik! Keep the code that has passed all the tests in that tutorial: Pastebin .
In a nutshell about the algorithm:
- open parentheses are pushed onto the stack
- when meeting the closing brackets, we check for compliance with the last one in the stack matches -> remove from the stack, otherwise -> see point 3
- is the stack empty? -> display on the left, otherwise -> IMPOSIBLE
-
if after a complete pass of the sequence the stack is not empty, we add to the right
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')