А в чём проблема-то? Идём слева направо. Если после открывающей скобки следует чужая закрывающая, то 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("<br>Input$num = $input");
$arr_input = str_arr_exchange($input);
$arr_output = $arr_input;
bracket_close($arr_input, $arr_output);
if ($arr_output === FALSE) {
print("<br> IMPOSSIBLE<br>");
} else {
$output = str_arr_exchange($arr_output);
print("<br>Output$num = $output<br>");
}
}
brackets_close($input1, 1);
brackets_close($input2, 2);
Результаты:
Input1 = }[[([{[]}
Output1 = {}[[([{[]}])]]
Input2 = {][[[[{}[]
IMPOSSIBLE
Уверенность в корректности алгоритма обеспечивается следующими соображениями:
1. Закрывающие скобки обрабатываются на месте, анализ ситуаций исчерпывающий.
2. Открывающие скобки всегда упорядочены.