C++ এ স্ট্রিং ডিকোড করুন

ধরুন আমাদের একটি এনকোডেড স্ট্রিং আছে; আমাদের তার ডিকোড করা স্ট্রিং ফেরত দিতে হবে। এনকোডিংয়ের নিয়ম হল:k[encoded_string], এটি নির্দেশ করে যে বর্গাকার বন্ধনীর ভিতরে এনকোডেড_স্ট্রিং ঠিক k বার পুনরাবৃত্তি হচ্ছে। আমরা ধরে নিতে পারি যে মূল ডেটাতে কোনো সংখ্যাসূচক অক্ষর নেই এবং সেই সংখ্যাগুলি শুধুমাত্র সেই পুনরাবৃত্তি সংখ্যাগুলির জন্য, k। তাই ইনপুট যদি “1[ba]2[na]” এর মত হয়, তাহলে আউটপুট হবে “কলা”।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি খালি স্ট্যাক তৈরি করুন, i :=0 সেট করুন
• যখন আমি <একটি স্ট্রিংয়ের আকার
  • যদি s[i] হয় ‘]’
    • res :=স্ট্যাক থেকে উপাদান মুছুন এবং শুধুমাত্র বর্গাকার বন্ধনীর ভিতরে থাকা স্ট্রিংটি নিন।
    • n :=0
    • স্ট্যাক খালি না থাকা অবস্থায়, এবং স্ট্যাক টপ একটি সাংখ্যিক অক্ষর, তারপর সংখ্যাগুলিকে মিটমাট করুন এবং n হিসাবে প্রকৃত পূর্ণসংখ্যা তৈরি করুন
    1 থেকে n
    রেঞ্জের মধ্যে j-এর জন্য
    • এক্সের জন্য রেঞ্জ 0 থেকে res এর মাপ
      • স্ট্যাকের মধ্যে res[x] ঢোকান
  • অন্যথায় স্ট্যাকের মধ্যে s[i] ঢোকান
  • 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"