এখানে আমরা দেখব কিভাবে বন্ধনীর একটি স্ট্রিং এ সমান পয়েন্ট পেতে হয়। সমান বিন্দু হল সূচক I, যেমন এর আগে খোলা বন্ধনীর সংখ্যা এর পরে বন্ধ বন্ধনীর সংখ্যার সমান। ধরুন একটি বন্ধনী স্ট্রিং "(()))()()()))" এর মতো, যদি আমরা কাছাকাছি দেখি, আমরা পেতে পারি
সুতরাং 0 থেকে 9 পর্যন্ত খোলা বন্ধনীর সংখ্যা 5 এবং 9 থেকে 14 পর্যন্ত বন্ধ বন্ধনীর সংখ্যাও 5, তাই এটি সমান বিন্দু৷
এই সমস্যা সমাধানের জন্য, আমাদের এই কয়েকটি ধাপ অনুসরণ করতে হবে -
- প্রত্যেক সূচী পর্যন্ত স্ট্রিং-এ প্রদর্শিত ওপেনিং ব্র্যাকেটের সংখ্যা সংরক্ষণ করুন i
- প্রত্যেকটি সূচী 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
