বিবেচনা করুন আমাদের একটি এক্সপ্রেশন এক্সপ্রেশন আছে, এবং এক্সপ্রেশনের চারপাশে একটি ডুপ্লিকেট বন্ধনী আছে কি না তা আমাদের পরীক্ষা করতে হবে। একটি অভিব্যক্তিতে ডুপ্লিকেট বন্ধনী থাকবে যদি একটি উপ-অভিব্যক্তি একাধিক বন্ধনী সেট দ্বারা বেষ্টিত থাকে। উদাহরণস্বরূপ, যদি অভিব্যক্তিটি −
এর মত হয়(5+((7−3)))
এখানে উপ-অভিব্যক্তি (7 – 3) দুটি বন্ধনী জোড়া দ্বারা বেষ্টিত, তাই এগুলি ডুপ্লিকেট বন্ধনী।
এই সমস্যা সমাধানের জন্য, আমরা স্ট্যাক ব্যবহার করব। আমরা এক্সপের প্রতিটি অক্ষরের মাধ্যমে পুনরাবৃত্তি করব, এবং যদি অক্ষরটি '(', বা অপারেটর বা অপারেন্ডের যেকোন একটি বন্ধনী খুলতে থাকে, তবে এটিকে স্ট্যাকের মধ্যে ঠেলে দিন। যখন অক্ষরটি বন্ধনী বন্ধ করছে, তখন স্ট্যাক থেকে বারবার অক্ষরগুলি পপ করুন। যতক্ষণ না মেলা খোলা বন্ধনী পাওয়া যায়, এবং একটি কাউন্টার ব্যবহার করা হয়, যার মান খোলা এবং বন্ধ বন্ধনী জোড়ার মধ্যে দেখা প্রতিটি অক্ষরের জন্য বৃদ্ধি পাবে। যা কাউন্টারের মানের সমান, 1 এর কম, তারপর নকল বন্ধনীর জোড়া পাওয়া যায়, অন্যথায় পাওয়া যায় না।
উদাহরণ
#include<iostream>
#include<stack>
using namespace std;
bool hasDuplicateParentheses(string str) {
stack<char> stk;
for (int i = 0; i<str.length(); i++) {
char ch = str[i];
if (ch == ')') {
char top = stk.top();
stk.pop();
int count = 0;
while (top != '(') {
count++;
top = stk.top();
stk.pop();
}
if(count < 1) {
return true;
}
}
else
stk.push(ch);
}
return false;
}
int main() {
string str = "(5+((7-3)))";
if (hasDuplicateParentheses(str))
cout << "Duplicate parentheses has Found";
else
cout << "No Duplicates parentheses has Found ";
} আউটপুট
Duplicate parentheses has Found
