এই সমস্যায়, আমাদের এক্সপ্রেশন দেওয়া হয়। এবং আমাদের বন্ধনী নম্বর ক্রম প্রিন্ট করতে হবে। সমস্যাটি আরও ভালভাবে বোঝার জন্য আসুন একটি উদাহরণ দেখি।
উদাহরণ,
Input : ((()())()) Output : 1233442551
ব্যাখ্যা − এখানে আমরা 5টি বন্ধনী জোড়ার সম্মুখীন হয়েছি এবং আমরা সেগুলিকে তাদের [ সংঘটনের ক্রমানুসারে প্রিন্ট করেছি৷
এখন যেহেতু আমরা সমস্যা সম্পর্কে জানি, আসুন এই সমাধানটির একটি সমাধান তৈরি করি।
এই সমস্যার সমাধানের জন্য স্ট্যাক ডেটা স্ট্রাকচার প্রয়োজন। আমরা একটি ভেরিয়েবল ব্যবহার করব যা বাম বন্ধনীর সংখ্যা গণনা রাখে এবং স্ট্যাক ডান বন্ধনীর ট্র্যাক রাখে। আমরা বাম বন্ধনী গণনা করব এবং তাদের স্ট্যাকের মধ্যে ঠেলে দেব এবং ডান বন্ধনীর সম্মুখীন হলে পপ করব।
অ্যালগরিদম
Step 1 : Initialise leftBrackets = 1. stack rightBrackets, empty. Step 2 : traverse the expression using variable i = 0 to n-1. Step 3 : if expression[i] == ‘(’ i.e. left bracket is encountered. Then, Step 3.1 : PRINT ‘leftBracket ‘. Step 3.2 : push the value of leftBracket in stack. Step 3.3 : leftBracket++. Step 4 : if expression[i] == ‘)’ i.e. right bracket is encountered. Then, Step 4.1 : PRINT top of stack. Step 4.2 : pop top element of the stack. Step 5 : EXIT.
উদাহরণ
এখন উপরের অ্যালগরিদম বাস্তবায়নের জন্য প্রোগ্রামিং তৈরি করা যাক।
#include <bits/stdc++.h>
using namespace std;
void bracketCount(string expression, int n){
int leftBracket = 1;
stack<int> rightBracket;
for (int i = 0; i < n; i++) {
if (expression[i] == '(') {
cout<<leftBracket<<" ";
rightBracket.push(leftBracket);
leftBracket++;
}
else if(expression[i] == ')') {
cout<<rightBracket.top() << " ";
rightBracket.pop();
}
}
}
int main(){
string expression = "()((())()())";
int n = expression.size();
bracketCount(expression, n);
return 0;
} আউটপুট
1 1 2 3 4 4 3 5 5 6 6 2
