सी ++ में डीकोड स्ट्रिंग

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

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

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

उदाहरण (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"