এখানে আমরা দেখব কিভাবে ব্র্যাকেট স্ট্রিংয়ে সমান পয়েন্ট (equal point) বের করতে হয়। সমান পয়েন্ট হল ইনডেক্স i, যেন সেটির আগে থাকা ওপেনিং ব্র্যাকেটের সংখ্যা সেটির পরে থাকা ক্লোজিং ব্র্যাকেটের সংখ্যায় সমান হয়। ধরি একটি ব্র্যাকেট স্ট্রিং "(()))(()()())))" আছে, যদি gần থেকে দেখি তবে পাব:
০ থেকে ৯ ইনডেক্স পর্যন্ত ওপেনিং ব্র্যাকেট ৫টি, এবং ৯ থেকে ১৪ ইনডেক্স পর্যন্ত ক্লোজিং ব্র্যাকেটও ৫টি, তাই এটি সমান পয়েন্ট।
এটি সমাধান করতে নিচের ধাপগুলো ফলো করতে হবে:
- প্রতিটি ইনডেক্স 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] == '(') // প্রথম ব্র্যাকেট ওপেনিং কিনা চেক, হলে 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
