मान लीजिए कि हमारे पास एक संतुलित कोष्ठक स्ट्रिंग S है, तो हमें निम्नलिखित नियम के आधार पर स्ट्रिंग के स्कोर की गणना करनी होगी -
- द () का स्कोर 1 है
- एबी का स्कोर ए + बी है, जहां ए और बी दो संतुलित कोष्ठक तार हैं।
- (A) का स्कोर 2 * A है, जहां A एक संतुलित कोष्ठक स्ट्रिंग है।
तो अगर इनपुट "(()(()))" जैसा है, तो आउटपुट 6 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- उत्तर:=0, एक स्टैक सेंट परिभाषित करें
- i के लिए 0 से लेकर स्ट्रिंग S के आकार तक
- अगर S[i] कोष्ठक खोल रहा है, तो -1 को स्टैक में डालें
- अन्यथा
- यदि स्टैक का शीर्ष -1 है, तो स्टैक से हटाएं और स्टैक में 1 डालें
- अन्यथा
- x :=0
- जबकि स्टैक का शीर्ष -1 नहीं है
- सेंट से x बढ़ाएं, सेंट से हटाएं
- x :=x * 2
- सेंट से हटाएं, और 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