#алгоритм #структуры_данных
Задача из области "алгоритмы и структуры данных".
Дан фрагмент последовательности скобок, состоящей из символов
(){}[]
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную
последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте
"IMPOSSIBLE".
Максимальная длина строки 10^6 символов.
Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]
Sample Input 2:
{][[[[{}[]
IMPOSSIBLE
Идеи:
Есть стандартный алгоритм проверки корректности расстановки скобок, реализуемый через
стэк. Суть в следудующем:
идем по строке, если встречаем открывающую скобку - заносим в стек
если встречаем закрывающую скобку и на вершине стека лежит аналогичная ей открывающая,
то удаляем ее (открывающюю) из стека
если после прохода всей строки стек пустой, значит скобки расставлены верно.
Для решения этого задания этот алгоритм нужно модифицировать, чтобы была возможность
(или определить невозможность) дополнения проверяемой строки до корректной.
Для этого пытался заводить счетчики на каждую скобку и ее направление и держать
противоположную скобку в деке и в нужный момент извлекать из дека. Но пока все покрывается
ифами и алгоритм все равно правильно не работает
Ответы
Ответ 1
Привет со Степика! Держи код, прошедший все тесты в том уроке: Pastebin. В кратце об алгоритме: открывающие скобки заносим в стек встречая закрывающие скобки проверяем на соответствие последней в стеке соответствует -> убираем из стека, иначе -> см.пункт 3 стек пуст? -> выводим слева, иначе -> IMPOSIBLE если после полного прохода последовательности стек не пуст, дополняем справа 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')Ответ 2
При реализации алгоритма проверки корректности строк можно встретиться со следующими ситуациями (кроме варианта когда каждой твари по паре): Прошли всю строку - в стеке остались открывающие скобки; Дошли до закрывающей скобки - стек пустой; Дошли до закрывающей скобки - на вершине стека другая скобка. В первом случае можно дополнить вашу строку справа чтобы принудительно закрыть скобки. Во втором случае можно дополнить скобками слева чтобы принудительно открыть их. Чтобы исправить третий случай, придется вставлять скобки в середину строки. Дополнено Допустим A, B, C и D пустые или сбалансированные выражения. Если мы имеем выражение A(B в стеке останется открывающая скобка и ее можно закрыть, дополнив строку закрывающей скобкой. Если мы имеем выражение A(B[C, то мы можем аналогично сделать сбалансированным выражение B[C и привести выражение A(B[C к A(B. Таким образом можно сбалансировать любое аналогичное выражение; Если мы имеем выражение A)B в ходе проверки будет попытка закрытия неоткрытой скобки (в стеке открытых скобок не будет). Исправить выражение можно дополнив выражение слева открывающей скобкой. Аналогично балансируется выражение A)B]C и имеющие больше закрытых; Если имеет место выражение вида A(B[C)D или A(B]C)D то при получении закрывающей скобки на вершине стека будет обнаружена скобка, которая не соответствует открывающей. Исправить эту ситуацию можно только в пределах внешних скобок, соответственно невозможно исправить такое выражение дополнением скобок слева или справа.Ответ 3
А в чём проблема-то? Идём слева направо. Если после открывающей скобки следует чужая закрывающая, то IMPOSSIBLE. И всё. Особенности программы: Для удобства обработки вместо символьных строк работаем с числовыми массивами. Открывающие скобки имеют номера 0-2. закрывающие 3-5. Открывающей скобке $i соответствует закрывающая скобка $i+3. Перевод в обе стороны обеспечивает функция str_arr_exchange(). Выходной массив инициализируется входным. Открывающие скобки сразу записываются в стек. Закрывающей скобке должна соответствовать последняя скобка в стеке либо пустой стек (иначе IMPOSSIBLE). Во втором случае выходной массив дополняется парной скобкой. В обоих случаях скобки удаляются из входного массива и стека. Если входной массив закончился, а в стеке остались открывающие скобки, то в выходной массив следует дописать парные им скобки. Программа на PHP использует рекурсивный вызов функции bracket_close() : $input1 = "}[[([{[]}"; $input2 = "{][[[[{}[]"; function str_arr_exchange($input){ $arr_brack = ["(","{","[",")","}","]"]; if(is_string($input)){ for ($output = [], $i = strlen($input)-1; $i>=0; $i--){ array_push($output, array_search($input[$i], $arr_brack)); } } else { $output = ""; while(!is_null($brack = array_pop($input))){ $output .= $arr_brack[$brack]; } } return $output; } function bracket_close(&$arr_input, &$arr_output, &$stack = []){ if($arr_output === FALSE) return; if(empty($arr_input)){ while(count($stack)){ // в стеке только открывающие скобки array_unshift($arr_output, array_pop($stack)+3); // конец строки - в начале массива } return; } if(empty($stack)){ // стек пуст $brack = array_pop($arr_input); if($brack>2){ // скобка закрывающая array_push($arr_output, $brack-3); // начало строки - в конце массива } else { array_push($stack, $brack); } } else { // стек непуст $old_brack = array_pop($stack); $new_brack = array_pop($arr_input); if($new_brack>2){ // скобка закрывающая if($old_brack == $new_brack - 3){ // скобки сомкнулись } else { // скобки конфликтуют $arr_output = FALSE; } } else { // скобка открывающая array_push($stack, $old_brack, $new_brack); } } bracket_close($arr_input, $arr_output, $stack); } function brackets_close($input, $num){ print("
Input$num = $input"); $arr_input = str_arr_exchange($input); $arr_output = $arr_input; bracket_close($arr_input, $arr_output); if ($arr_output === FALSE) { print("
IMPOSSIBLE
"); } else { $output = str_arr_exchange($arr_output); print("
Output$num = $output
"); } } brackets_close($input1, 1); brackets_close($input2, 2); Результаты: Input1 = }[[([{[]} Output1 = {}[[([{[]}])]] Input2 = {][[[[{}[] IMPOSSIBLE Уверенность в корректности алгоритма обеспечивается следующими соображениями: 1. Закрывающие скобки обрабатываются на месте, анализ ситуаций исчерпывающий. 2. Открывающие скобки всегда упорядочены.
Комментариев нет:
Отправить комментарий