C++ में स्ट्रिंग डिकोड करना

समस्या

मान लीजिए हमारे पास एक एन्कोडेड स्ट्रिंग है; हमें उसकी डिकोडेड स्ट्रिंग लौटानी है। एन्कोडिंग का नियम है: k[encoded_string], इसका मतलब है कि वर्गाकार कोष्ठक के अंदर की encoded_string को ठीक k बार दोहराया जाता है। हम मान सकते हैं कि मूल डेटा में कोई संख्यात्मक वर्ण नहीं हैं और अंक केवल उन दोहराव संख्याओं k के लिए हैं। इसलिए यदि इनपुट "1[ba]2[na]" है, तो आउटपुट "banana" होगा।

समाधान दृष्टिकोण

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

• एक खाली स्टैक बनाएं, i := 0 सेट करें
• जब तक i < स्ट्रिंग का आकार
  • यदि s[i] == ']' है
    • res := स्टैक से तत्व हटाएं और केवल वर्गाकार कोष्ठक के अंदर की स्ट्रिंग लें।
    • n := 0
    • जब तक स्टैक खाली नहीं है और स्टैक का शीर्ष एक संख्यात्मक वर्ण है, तब संख्याओं को समायोजित करके वास्तविक पूर्णांक n बनाएं
    • j को 1 से n तक लूप में
      • x को 0 से res के आकार तक लूप में
        • res[x] को स्टैक में डालें
  • अन्यथा s[i] को स्टैक में डालें
  • i को 1 बढ़ाएं
• ans := एक खाली स्ट्रिंग
• जब तक स्टैक खाली नहीं है
  • ans := स्टैक का शीर्ष तत्व + ans
  • स्टैक से पॉप करें
• ans लौटाएं

उदाहरण (C++):

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

#include <bits/stdc++.h> using namespace std; class Solution { public:    string decodeString(string s) {       stack <char> st;       int i = 0;       while(i<s.size()){          if(s[i] == ']'){             string res = "";             while(st.top()!='['){                res = st.top() + res;                st.pop();             }             st.pop();             int n = 0;             int x = 1;             while(!st.empty() && st.top()>='0' && st.top()<='9'){                n = n + (st.top()-'0')*x;                x*=10;                st.pop();             }             for(int j = 1; j <= n; j++){                for(int x = 0; x < res.size();x++){                   st.push(res[x]);                }             }          }          else{             st.push(s[i]);          }          i++;       }       string ans ="";       while(!st.empty()){          ans = st.top() + ans;          st.pop();       }       return ans;    } }; main(){    Solution ob;    cout << ob.decodeString("1[ba]2[na]"); }

इनपुट

"1[ba]2[na]"

आउटपुट

"banana"