Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में पैरेंथेसिस का स्कोर


मान लीजिए हमारे पास एक संतुलित पैरेंथेसिस स्ट्रिंग 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

  1. - C++ में पैरेंथेसेस को बैलेंस करने की लागत

    इस ट्यूटोरियल में, हम पैरेंथेसेस को बैलेंस करने की लागत खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें ब्रैकेट्स का एक अनुक्रम प्रदान किया जाएगा। हमारा कार्य समीकरण में उन पैरेंथेसेस को उनकी स्थिति को एक से शिफ्ट करके बैलेंस करना है और यदि उन्हें बैलेंस करना संभव नहीं है तो -1 प्रिंट करना ह

  1. - C++ में संतुलित पैरेंथेसिस के सभी संयोजन प्रिंट करना

    इस समस्या में, हमें एक पूर्णांक n दिया गया है। हमारा कार्य n संतुलित पैरेंथेसिस के सभी संभावित जोड़े प्रिंट करना है। संतुलित पैरेंथेसिस संतुलित पैरेंथेसिस वे पैरेंथेसिस जोड़े हैं जिनमें प्रत्येक संबंधित ओपनिंग सिंबल के लिए एक क्लोजिंग सिंबल होता है। साथ ही, जोड़े ठीक से नेस्टेड होने चाहिए। उदाहरण

  1. - C++ में वैध पैरेंथेसिस

    मान लीजिए हमारे पास एक अभिव्यक्ति है। अभिव्यक्ति में कुछ पैरेंथेसिस हैं; हमें जांचना है कि पैरेंथेसिस संतुलित हैं या नहीं। पैरेंथेसिस का क्रम (), {} और [] है। मान लीजिए दो स्ट्रिंग हैं। ()[(){()}] यह वैध है, लेकिन {[}] अवैध है। कार्य सरल है; हम इसे करने के लिए स्टैक का उपयोग करेंगे। हमें समाधान प्र