Все началось с того, что на сайте codeforces.ru в очередном Codeforces Round я увидел интересную задачку “Скобочная последовательность” и решать ее “неинтересным способом” никак не хотелось.
Вкратце условия задачи сводятся к нахождению в строке, состоящей только из символов «(», «)», «[» и «]», правильной cкобочной последовательности, содержащей как можно больше скобок «[».
Для начала превращаем нашу плоскую строчку в более удобное иерархическое представление:
with brackets as
(select '[[)]([][][][[()[()[()()]]]])]' b
from dual)
select substr(b,level,1) q,
level curr_pos,
level - 1 prev_pos
from brackets
connect by substr(b,level,1) is not null
В каждой строчке будет очередная скобка, позиция текущей скобки и позиция предыдущей скобки. С этим уже можно что-то сделать.
Осталось найти все правильные скобочные последовательности. Здесь начинается самое интересное.
Так как для определения правильности выражения у нас нет стека, в котором можно хранить скобочки, пришлось идти на “хитрость”.
Найдем все возможные последовательности, начинающиеся с «(» или «[» (остальные неправильные по умолчанию). Для каждой такой последовательности определим позицию первой и последней скобки и “уровень вложенности” последней скобки, т.е.:
«(» «1ый - уровень»
«(» «2ой – уровень»
.. ... .. ..
«]» «2ой – уровень»
.. ... .. .. .
- Уровень увеличивается, если: скобка открывается, а перед ней ничего не было, либо была любая открывающаяся;
- Уровень не изменяется, если скобка открывается, а перед ней была закрывающаяся, либо если скобка закрывается, а перед ней была открывающаяся;
- Уровень уменьшается, если скобка закрывается, а перед ней была закрывающаяся;
with brackets as
(select '[[)]([][][][[()[()[()()]]]])]' b
from dual) ,
all_brackets as
(select substr(b,level,1) q,
level curr_pos,
level-1 prev_pos
from brackets
connect by substr(b,level,1) is not null)
select replace(sys_connect_by_path(q,'-'), '-') str,
q,
connect_by_root(curr_pos) start_pos,
curr_pos end_pos,
sum( case
when (q = '(' or q = '[')
and (prior q is null)
then 1
when (q = '(' or q = '[')
and (prior q = '(' or prior q = '[')
then 1
when (q = '(' or q = '[')
and (prior q = ']' or prior q = ')')
then 0
when (q = ')' or q = ']')
and (prior q = '(' or prior q = '[')
then 0
when (q = ')' or q = ']')
and (prior q = ')' or prior q = ']')
then -1
end)
over (partition by connect_by_root(curr_pos)
order by connect_by_root(curr_pos), curr_pos) bracket_level
from all_brackets
connect by prior curr_pos = prev_pos
start with q = '(' or q = '['
С помощью этих данных мы можем определить, скобку “вредителя”, которая делает из правильной последовательности неправильную. Для этого просмотрим все полученные последовательности, и при “появлении” очередной скобки, найдем предыдущую скобку, находящуюся на одном уровне с текущей (Спасибо Oracle за аналитическую функцию lag). Неправильная последовательность получается, если на одном из уровней возникает одна из следующих ситуаций:
- закрывается закрытая скобка
- круглая скобка закрывает квадратную
- квадратная скобка закрывает круглую
Любая открывающаяся скобка на данной итерации не может “поломать” последовательность.
with brackets as
(select '[[)]([][][][[()[()[()()]]]])]' b
from dual) ,
all_brackets as
(select substr(b,level,1) q,
level curr_pos,
level - 1 prev_pos
from brackets
connect by substr(b,level,1) is not null),
brackets_comb as
(select replace(sys_connect_by_path(q,'-'), '-') str,
q,
connect_by_root(curr_pos) start_pos,
curr_pos end_pos,
sum( case
when (q = '(' or q = '[')
and (prior q is null)
then 1
when (q = '(' or q = '[')
and (prior q = '(' or prior q = '[')
then 1
when (q = '(' or q = '[')
and (prior q = ']' or prior q = ')')
then 0
when (q = ')' or q = ']')
and (prior q = '(' or prior q = '[')
then 0
when (q = ')' or q = ']')
and (prior q = ')' or prior q = ']')
then -1
end)
over (partition by connect_by_root(curr_pos)
order by connect_by_root(curr_pos), curr_pos) bracket_level
from all_brackets
connect by prior curr_pos = prev_pos
start with q = '(' or q = '[')
select start_pos,
end_pos,
str,
case
when q = ')'
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = '('
then 'ok'
when q = '('
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ')'
then 'ok'
when q = '('
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ']'
then 'ok'
when q = ']'
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = '['
then 'ok'
when q = '['
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ']'
then 'ok'
when q = '['
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ')'
then 'ok'
when lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) is null
and bracket_level > 0
then 'ok'
else 'not ok!'
end status
from brackets_comb bc
Таким образом, для каждого множества последовательностей, начинающихся с одной позиции (start_pos) и упорядоченных по количеству скобок, мы нашли первую неверную последовательность.
В каждом таком множестве последовательностей “выкинем” последовательности после “неправильной”, и для всех оставшихся проверим, что открывшиеся скобки закрылись (для этого достаточно посчитать количество открывшихся и закрывшихся скобок каждого вида).
В результате останется найти ту единственную, а может и не единственную, её (нет, не девушку своей мечты, как вы могли подумать), скобочную последовательность с максимальным количеством «[».
Весь запрос:
with brackets as
(select '[[]])[([[]][[(]])]' b
from dual) ,
all_brackets as
(select substr(b,level,1) q,
level curr_pos,
level - 1 prev_pos
from brackets
connect by substr(b,level,1) is not null),
brackets_comb as
(select replace(sys_connect_by_path(q,'-'), '-') str,
q,
connect_by_root(curr_pos) start_pos,
curr_pos end_pos,
sum( case
when (q = '(' or q = '[')
and (prior q is null)
then 1
when (q = '(' or q = '[')
and (prior q = '(' or prior q = '[')
then 1
when (q = '(' or q = '[')
and (prior q = ']' or prior q = ')')
then 0
when (q = ')' or q = ']')
and (prior q = '(' or prior q = '[')
then 0
when (q = ')' or q = ']')
and (prior q = ')' or prior q = ']')
then -1
end)
over (partition by connect_by_root(curr_pos)
order by connect_by_root(curr_pos), curr_pos) bracket_level
from all_brackets
connect by prior curr_pos = prev_pos
start with q = '(' or q = '['),
brackets_comb_status as
(select start_pos,
end_pos,
str,
case
when q = ')'
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = '('
then 'ok'
when q = '('
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ')'
then 'ok'
when q = '('
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos ) = ']'
then 'ok'
when q = ']'
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = '['
then 'ok'
when q = '['
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ']'
then 'ok'
when q = '['
and lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) = ')'
then 'ok'
when lag(q) over (partition by start_pos, bracket_level
order by start_pos, bracket_level, end_pos) is null
and bracket_level > 0
then 'ok'
else 'not ok!'
end status
from brackets_comb bc)
select str "последовательность",
cnt "колличество [",
start_pos "позиция с",
end_pos "позиция по"
from (
select str,
start_pos,
end_pos,
length(regexp_replace(str,'[)(]',''))/2 cnt,
max(length(regexp_replace(str,'[)(]',''))/2) over (order by null) best_cnt
from (
select str,
start_pos,
end_pos,
nvl(
lag(
case
when status = 'ok' then null
else status
end
ignore nulls)
over (partition by start_pos order by start_pos, end_pos),
status
) status
from brackets_comb_status
)
where status = 'ok'
and length(replace(str,'[','')) = length(replace(str,']',''))
and length(replace(str,'(','')) = length(replace(str,')',''))
) result
where best_cnt = cnt
Автор: beIive
