यहां हम देखेंगे कि कोष्ठक की एक स्ट्रिंग में समान अंक कैसे प्राप्त करें। समान बिंदु सूचकांक I है, जैसे कि इसके पहले खुलने वाले कोष्ठकों की संख्या इसके बाद के समापन कोष्ठक की संख्या के बराबर है। मान लीजिए कि एक ब्रैकेट स्ट्रिंग "(())) (() () ()))" की तरह है, अगर हम करीब से देखते हैं, तो हम प्राप्त कर सकते हैं
तो 0 से 9 तक खुलने वाले कोष्ठकों की संख्या 5 है, और 9 से 14 तक के समापन कोष्ठकों की संख्या भी 5 है, इसलिए यह बराबर बिंदु है।
इस समस्या को हल करने के लिए, हमें इन कुछ चरणों का पालन करना होगा -
- हर इंडेक्स तक स्ट्रिंग में दिखाई देने वाले ओपनिंग ब्रैकेट्स की संख्या को स्टोर करें।
- संग्रह में बंद कोष्ठकों की संख्या प्रत्येक अनुक्रमणिका I तक दिखाई देती है लेकिन इसे अंतिम अनुक्रमणिका से किया जाना चाहिए।
- जांचें कि क्या किसी अनुक्रमणिका में कोष्ठक खोलने और बंद करने का मान समान है।
उदाहरण
#include<iostream>
#include<cmath>
using namespace std;
int findEqualPoint(string str) {
int total_length = str.length();
int open[total_length+1] = {0}, close[total_length+1] = {0};
int index = -1;
open[0] = 0;
close[total_length] = 0;
if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1
open[1] = 1;
if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark close[end] = 1
close[total_length-1] = 1;
for (int i = 1; i < total_length; i++) {
if ( str[i] == '(' )
open[i+1] = open[i] + 1;
else
open[i+1] = open[i];
}
for (int i = total_length-2; i >= 0; i--) {
if ( str[i] == ')' )
close[i] = close[i+1] + 1;
else
close[i] = close[i+1];
}
if (open[total_length] == 0)
return total_length;
if (close[0] == 0)
return 0;
for (int i=0; i<=total_length; i++)
if (open[i] == close[i])
index = i;
return index;
}
int main() {
string str = "(()))(()()())))";
cout << "Index of equal point: " << findEqualPoint(str);
} आउटपुट
Index of equal point: 9