C++ में मान्य कोष्ठक बनाने के लिए न्यूनतम निकालें

मान लीजिए कि हमारे पास '(' , ')' का एक स्ट्रिंग s है और अंग्रेज़ी के छोटे अक्षर हैं। हमें कोष्ठकों की न्यूनतम संख्या ('(' या ')', किसी भी स्थिति में) को हटाना होगा ताकि परिणामी कोष्ठक स्ट्रिंग मान्य हो और कोई भी मान्य स्ट्रिंग लौटाए। एक कोष्ठक स्ट्रिंग तब मान्य होती है जब ये सभी मानदंड पूरे हो जाते हैं -

• यह खाली स्ट्रिंग है, इसमें केवल लोअरकेस वर्ण हैं, या

• इसे एबी के रूप में लिखा जा सकता है (ए बी के साथ जुड़ा हुआ है), जहां ए और बी वैध स्ट्रिंग हैं, या

• इसे (ए) के रूप में लिखा जा सकता है, जहां ए एक वैध स्ट्रिंग है।

तो अगर इनपुट "ए) बी (सी) डी" जैसा है, तो आउटपुट "एबी (सी) डी" होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• स्टैक सेंट को परिभाषित करें

• मैं के लिए 0 से s के आकार की सीमा में

  • अगर s[i] ='(', तो i को सेंट में डालें

  • अन्यथा जब s[i] ')' है, तब

    • यदि स्टैक खाली नहीं है, तो स्टैक से पॉप करें, अन्यथा s[i] ='*'

• जबकि सेंट खाली नहीं है,

  • s [ढेर का शीर्ष तत्व] ='*'

  • स्टैक से पॉप करें

• उत्तर:=खाली स्ट्रिंग

• मैं के लिए 0 से लेकर s - 1 के आकार तक के लिए

  • यदि s[i] '*' नहीं है, तो उत्तर :=ans + s[i]

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minRemoveToMakeValid(string s) {
      stack <int> st;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '(')st.push(i);
         else if(s[i] == ')'){
            if(!st.empty())st.pop();
            else s[i] = '*';
         }
      }
      while(!st.empty()){
         s[st.top()] = '*';
         st.pop();
      }
      string ans = "";
     for(int i = 0; i < s.size(); i++){
        if(s[i] != '*')ans += s[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}

इनपुट

"a)b(c)d"

आउटपुट

ab(c)d