We consider brackets on Oracle SQL

It all started with the fact that on the codeforces.ru site in the next Codeforces Round I saw an interesting puzzle “Bracket sequence” and didn’t want to solve it in an “uninteresting way”.

Briefly, the conditions of the problem are reduced to finding in the line consisting only of the characters "(", ")", "[" and "]", the correct bracket sequence containing as many as possible brackets "[".


To begin with, we turn our flat line into a more convenient hierarchical representation:
')

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 

Each line will contain the next bracket, the position of the current bracket and the position of the previous bracket. With this you can already do something.

It remains to find all the correct bracket sequences. This is where the fun begins.
Since to determine the correctness of the expression we do not have a stack in which you can store parentheses, we had to go to the “trick”.

Let us find all possible sequences starting with “(” or “[” (the rest are incorrect by default). For each such sequence, we define the position of the first and last brackets and the “nesting level” of the last bracket, ie:

 "(" "1st - level"
      "(" "2nd - level"
       .. ... .. .. 
       "]" "2nd - level"
 .. ... .. ...

• The level increases if: the bracket opens, but there is nothing before it, or there was any opening;
• The level does not change if the bracket is opened, and before it was closed, or if the bracket is closed, and before it was opened;
• The level decreases if the bracket is closed, and before it was closed;

 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 = '[' 

Using this data, we can determine the “pest” bracket that makes the correct sequence wrong. To do this, we look through all the received sequences, and when the next bracket “appears”, we will find the previous bracket, which is on the same level with the current one (Thanks to Oracle for the analytical function lag). An incorrect sequence is obtained if one of the following situations occurs on one of the levels:

• closed bracket is closed
• the parenthesis closes the square
• square bracket covers the round

Any opening parenthesis at this iteration cannot break the sequence.

 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 

Thus, for each set of sequences starting from one position (start_pos) and ordered by the number of parentheses, we found the first incorrect sequence.
In each such set of sequences, we “discard” the sequence after the “wrong” one, and for all the remaining ones we check that the opened parentheses are closed (for this it is enough to count the number of opened and closed brackets of each type).
As a result, it remains to find the one, or maybe not the only, her (no, not the girl of your dreams, as you might think), the bracket sequence with the maximum number “[”.

All request:

 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