यहां हम देखेंगे कि ब्रैकेट की स्ट्रिंग में समान बिंदु कैसे प्राप्त करें। समान बिंदु वह सूचकांक 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]=='(') // जांचें कि पहला ब्रैकेट खुलने वाला है या नहीं, यदि हां तो open[1] = 1 मार्क करें
open[1] = 1;
if (str[total_length-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
