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