कोष्ठकों का एक संतुलित व्यंजक एक ऐसा व्यंजक है जिसमें सभी प्रकार के कोष्ठकों के जोड़े एक साथ सही क्रम में होते हैं। इसका अर्थ यह है कि प्रत्येक प्रारंभिक कोष्ठक के लिए कोष्ठकों के उचित क्रम में एक समापन कोष्ठक होता है अर्थात { }।
अभिव्यक्ति - {([][]{})({}[]{})}
आउटपुट - संतुलित
अब, इस समस्या में हमें दी गई कोष्ठकों की संख्या से सभी संभव संतुलित व्यंजक बनाने हैं। और शर्त यह है कि दी गई स्थिति में प्रारंभिक कोष्ठक हों।
इस समस्या में, हमें एक पूर्णांक n और लंबाई 2n के कोष्ठकों की स्थिति की एक सरणी दी जाती है और हमें लंबाई 2n के संतुलित व्यंजकों की संख्या इस प्रकार से ज्ञात करनी होती है कि कोष्ठक खोलने से चिह्नित स्थिति में उद्घाटन कोष्ठक हो। {'.
उदाहरण -
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}. एल्गोरिदम
-
एक वाली सभी स्थितियां खुले कोष्ठक हैं।
-
निम्नलिखित नियमों का उपयोग करके पुनरावर्ती लूप का उपयोग करें,
-
यदि (शुरुआती कोष्ठकों की संख्या - समापन कोष्ठकों की संख्या)> 0 , तो 0 पर लौटें।
-
n तक लूप करने के बाद और यदि पुश और पॉप के बाद कुल कोष्ठक 0 है, तो 1 लौटाएं अर्थात प्राप्त समाधान। नहीं तो 0.
. लौटाएं -
अगर एक्सप्रेशन को 1 पहले से असाइन किया गया है, तो इंडेक्स को बढ़ाने और ब्रैकेट की कुल संख्या बढ़ाने पर दोबारा कॉल करें।
-
अन्यथा अनुक्रमणिका स्थान पर खुले कोष्ठकों को सम्मिलित करके फ़ंक्शन को पुनरावर्ती रूप से कॉल करें और फिर इसके लिए बंद कोष्ठक डालें और कोष्ठक की कुल संख्या घटाएँ और अगले अनुक्रमणिका पर जाएँ।
-
कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) <<endl;
return 0;
}