नियमित ब्रैकेट अनुक्रम में एक या अधिक प्रकार के ओपनिंग और क्लोजिंग ब्रैकेट होते हैं, प्रत्येक ओपनिंग ब्रैकेट में क्लोजिंग ब्रैकेट होता है, और (कई प्रकार के मामले में) उनके प्रकार ओवरलैप नहीं होते हैं।
सही एसपी:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [( { } ) ] }
अमान्य एसपी:
)) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
यह जांचने के लिए कि कोष्ठकों का एक कोष्ठक अनुक्रम एक ही प्रकार का है, बस शेष राशि की जांच करें।
अर्थात, हम शून्य (संतुलन) के बराबर एक चर प्रारंभ करते हैं। फिर हम स्ट्रिंग के माध्यम से दौड़ते हैं (यदि आप नहीं जानते कि यह कैसे करना है - RUN, STUPID!), जब यह ओपनिंग ब्रैकेट से मिलता है तो बैलेंस बढ़ाता है और जब यह क्लोजिंग ब्रैकेट से मिलता है तो इसे घटाता है। यदि किसी भी स्तर पर शेष ऋणात्मक हो जाता है या अंत में यह शून्य के बराबर नहीं होता है, तो अनुक्रम गलत है।
|
कई प्रकार के कोष्ठकों की उपस्थिति के मामले में, सब कुछ थोड़ा और जटिल हो जाता है। हम बैलेंस वेरिएबल के रूप में कार्य करने के लिए एक स्टैक बनाते हैं। यह आवश्यक है क्योंकि कोष्ठक ओवरलैप नहीं कर सकते। जब हम एक रेखा के माध्यम से चलते हैं और एक उद्घाटन कोष्ठक का सामना करते हैं, तो हम इसे स्टैक पर धकेल देते हैं। जब हम क्लोजिंग ब्रेस का सामना करते हैं, तो हम उस टाइप के ओपनिंग ब्रेस को स्टैक से बाहर निकालने की कोशिश करते हैं। यदि स्टैक पर एक भिन्न प्रकार का ब्रेस है, तो अनुक्रम अमान्य है। यदि अंत में स्टैक खाली नहीं है, तो अनुक्रम भी अमान्य है।
|
चेक किए जाने के तरीके से सही ब्रैकेट अनुक्रमों की पीढ़ी सीधे होती है - हमें शुद्धता का उल्लंघन किए बिना नए ब्रैकेट जोड़ने की जरूरत है। यह पुनरावर्ती पुनरावृत्ति द्वारा किया जाता है। अगर आप उसे नहीं जानते - बीई... आह, नहीं, आप आगे पढ़कर समझने की कोशिश कर सकते हैं। यहाँ एक प्रकार के कोष्ठकों के लिए एक कोड नमूना दिया गया है:
<पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स">
#include <vector>
#include <iostream>
उपयोग नामस्थान एसटीडी;
int n; // आधी लंबाई
वेक्टर<char> उत्तर; // हमारा जवाब
void rec(int बैलेंस) {
if (ans.size() == 2 * n) { // अगर ऐसा होता है, तो हम किया < /span>
for (int i = 0; i < 2 * n; i++)
cout << उत्तर [मैं] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // जांचें, हम हम नए ओपनिंग ब्रेस को बंद कर देंगे
// अब अपने हाथों को देखें: हमें प्रत्येक अनुक्रम के लिए एक अलग वेक्टर बनाने की आवश्यकता नहीं है
ans.push_back('(');
आरईसी (बैलेंस + 1);
उत्तर.पॉप_बैक (); // इसे समझने के लिए, आपको रिकर्सन के बारे में पता होना चाहिए। सबसे पहले, हम वेक्टर में एक कोष्ठक जोड़ते हैं, और फिर हम इस सभी कोड को फिर से निष्पादित करते हैं।
// यानी, यदि हम कर सकते हैं, तो फिर से कोष्ठक जोड़ें।
// और यह तब तक होगा जब तक हम रिकर्सन को छोड़ना शुरू नहीं करते - यानी, जब तक हम वांछित लंबाई तक नहीं पहुंच जाते।
// इसके बाद ब्रैकेट हटना शुरू हो जाएंगे। यदि आप इसे समझते हैं - मैं आपको बधाई देता हूं, आप बहुत अच्छे हैं।
}
if (balance > 0) { // अगर हम किसी ब्रैकेट को बंद कर सकते हैं, तो हम उसे बंद कर देते हैं।
ans.push_back(')');
आरईसी (बैलेंस - 1);
उत्तर.पॉप_बैक ();
}
}
int main()
{
सिने>> एन;
आरईसी (0);
रिटर्न 0;
}
और अब कठिनाइयों का समय - आपको कई प्रकार के कोष्ठकों के लिए एल्गोरिथम स्वयं लिखना होगा! मुहाहाहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहहह!
|