Giải mã chuỗi trong C ++

Giả sử chúng ta có một chuỗi được mã hóa; chúng ta phải trả về chuỗi đã giải mã của nó. Quy tắc cho mã hóa là:k [encoded_string], điều này cho biết vị trí chuỗi mã hóa bên trong dấu ngoặc vuông đang được lặp lại đúng k lần. Chúng ta có thể giả định rằng dữ liệu ban đầu không chứa bất kỳ ký tự số nào và các chữ số đó chỉ dành cho các số lặp lại đó, k. Vì vậy, nếu đầu vào giống như “1 [ba] 2 [na]”, thì đầu ra sẽ là “chuối”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một ngăn xếp trống, đặt i:=0
• while i
• nếu s [i] là ‘]’
  • res:=xóa phần tử khỏi ngăn xếp và chỉ lấy chuỗi nằm trong dấu ngoặc vuông.
  • n:=0
  • trong khi ngăn xếp không trống và đỉnh ngăn xếp là một ký tự số, sau đó chứa các số và tạo thành số nguyên thực tế là n
  • cho j trong phạm vi từ 1 đến n
    • cho x trong phạm vi 0 đến kích thước của res
      • chèn res [x] vào ngăn xếp
• nếu không thì chèn s [i] vào ngăn xếp
• tăng tôi lên 1

Ví dụ (C ++):

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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]");
}

Đầu vào

"1[ba]2[na]"

Đầu ra

"banana"