कोष्ठक का एक संतुलित अभिव्यक्ति एक ऐसा अभिव्यक्ति है जिसमें सभी प्रकार के कोष्ठक सही क्रम में एक साथ होते हैं। इसका अर्थ है कि प्रत्येक प्रारंभिक कोष्ठक के लिए एक समापन कोष्ठक होता है जो कोष्ठक के उचित क्रम में होता है यानी { }।
अभिव्यक्ति - {([][]{})({}[]{})}
आउटपुट - संतुलित
अब, इस समस्या में हमें दी गई कोष्ठक की संख्या से सभी संभावित संतुलित अभिव्यक्ति बनानी हैं। और शर्त यह है कि दिए गए स्थान पर प्रारंभिक कोष्ठक होंगे।
इस समस्या में, हमें एक पूर्णांक n और लंबाई 2n के कोष्ठक की स्थिति की एक सरणी दी गई है और हमें लंबाई 2n की संतुलित अभिव्यक्ति की संख्या ज्ञात करनी है जैसे कि प्रारंभिक कोष्ठक द्वारा चिह्नित स्थानों पर प्रारंभिक कोष्ठक '{' होगा।
उदाहरण -
Input: n = 2, position [1, 0, 0, 0]
Output: 2
Explanation: सभी संभावित परिणाम हैं: {{}} , {}{}.
एल्गोरिदम
एक वाले सभी स्थान प्रारंभिक कोष्ठक हैं।
निम्नलिखित नियमों का उपयोग करके एक पुनरावर्ती लूप का उपयोग करें:
यदि (प्रारंभिक कोष्ठक की संख्या - समापन कोष्ठक की संख्या) > 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;
}
आउटपुट
3