Oracle SQL में कोष्ठक की गिनती

यह सब इस तथ्य के साथ शुरू हुआ कि अगले कोडफोर्स राउंड में साइट codeforces.ru पर मैंने एक दिलचस्प पहेली "ब्रैकेट अनुक्रम" देखी और मैं इसे "निर्बाध तरीके से" हल नहीं करना चाहता था।

संक्षेप में, समस्या की स्थितियों को केवल "" (",") "," ["और"] "सही कोष्ठक अनुक्रम जिसमें" कोष्ठक "के रूप में कई कोष्ठक शामिल हैं, को खोजने के लिए कम किया जाता है।


शुरू करने के लिए, हम अपनी सपाट रेखा को अधिक सुविधाजनक श्रेणीबद्ध प्रतिनिधित्व में बदलते हैं:

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 - स्तर"
       ।।… .. ।। 
       "]" "द्वितीय - स्तर"
 ..… ..…

• स्तर बढ़ जाता है अगर: ब्रैकेट खुलता है, और उसके सामने कुछ भी नहीं था, या कोई उद्घाटन नहीं था;
• यदि ब्रैकेट खोला जाता है, और उसके बंद होने से पहले, या ब्रैकेट बंद होने पर, और खोलने से पहले यह स्तर नहीं बदलता है;
• यदि ब्रैकेट बंद हो जाता है, और बंद होने से पहले यह स्तर घट जाता है;

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

इस डेटा का उपयोग करके, हम "कीट" ब्रैकेट को निर्धारित कर सकते हैं जो क्रम से सही अनुक्रम बनाता है। ऐसा करने के लिए, हम प्राप्त किए गए सभी अनुक्रमों के माध्यम से देखेंगे, और जब अगला कोष्ठक "प्रकट" होगा, तो हम पिछले कोष्ठक पाएंगे, जो कि वर्तमान एक के समान स्तर पर है (विश्लेषणात्मक फ़ंक्शन के लिए ओरेकल के लिए धन्यवाद)। निम्न स्थितियों में से किसी एक स्तर पर होने पर एक गलत अनुक्रम प्राप्त होता है:

• बंद कोष्ठक बंद हो जाता है
• कोष्ठक वर्ग बंद कर देता है
• वर्ग ब्रैकेट बंद दौर

इस पुनरावृत्ति में कोई भी उद्घाटन ब्रैकेट अनुक्रम को "तोड़" नहीं सकता है।

 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