ধরুন আমাদের একটি সুষম বন্ধনী স্ট্রিং S আছে, আমাদের নিম্নলিখিত নিয়মের উপর ভিত্তি করে স্ট্রিংটির স্কোর গণনা করতে হবে -
- () স্কোর ১
- AB এর A + B স্কোর রয়েছে, যেখানে A এবং B দুটি সুষম বন্ধনী স্ট্রিং।
- (A) এর স্কোর 2 * A, যেখানে A হল একটি সুষম বন্ধনী স্ট্রিং।
সুতরাং ইনপুট যদি "(()(()))" এর মত হয়, তাহলে আউটপুট হবে 6।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- উত্তর :=0, একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
- এর জন্য 0 থেকে স্ট্রিং S
- এর মাপ পরিসীমা
- যদি S[i] বন্ধনী খুলছে, তাহলে স্ট্যাকের মধ্যে -1 ঢোকান
- অন্যথায়
- স্ট্যাকের শীর্ষ যদি -1 হয়, তাহলে স্ট্যাক থেকে মুছে ফেলুন এবং স্ট্যাকের মধ্যে 1 ঢোকান
- অন্যথায়
- x :=0
- যদিও স্ট্যাকের শীর্ষ -1
- নয়
- st দ্বারা x বাড়ান, st থেকে মুছুন
- x :=x * 2
- st থেকে মুছুন, এবং x সন্নিবেশ করুন
- যখন স্ট্যাক খালি থাকে না
- স্টের শীর্ষে উত্তর বাড়ান এবং শীর্ষ উপাদান মুছুন
- উত্তর ফেরত দিন।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int scoreOfParentheses(string S) {
int ans = 0;
stack <int> st;
for(int i = 0; i < S.size(); i+=1){
if(S[i] == '('){
st.push(-1);
}else{
if(st.top() == -1){
st.pop();
st.push(1);
}else{
int x = 0;
while(st.top() != -1){
x += st.top();
st.pop();
}
x *= 2;
st.pop();
st.push(x);
}
}
}
while(!st.empty()){
ans += st.top();
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.scoreOfParentheses("(()(()))"));
} ইনপুট
"(()(()))"
আউটপুট
6
