Считаем скобочки на Oracle SQL / Хабр

Все началось с того, что на сайте 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