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

Giả sử chúng ta có một chuỗi được mã hóa; nhiệm vụ là trả về chuỗi đã giải mã. Quy tắc mã hóa là: k[encoded_string], chỉ ra rằng encoded_string bên trong ngoặc vuông được lặp lại chính xác k lần. Ta có thể giả định dữ liệu gốc không chứa ký tự số và các chữ số chỉ dùng cho số lần lặp k. Ví dụ, nếu đầu vào là "1[ba]2[na]", đầu ra sẽ là "banana".

Để giải quyết bài toán này, ta thực hiện các bước sau:

• Tạo một ngăn xếp rỗng, đặt i := 0
• Trong khi i < độ dài chuỗi:
  • Nếu s[i] là ']':
    • res := lấy phần tử từ ngăn xếp và chỉ lấy chuỗi bên trong ngoặc vuông.
    • n := 0
    • Trong khi ngăn xếp không rỗng và đỉnh ngăn xếp là ký tự số, ghép các số để tạo thành số nguyên thực tế n
    • Với j từ 1 đến n:
      • Với x từ 0 đến độ dài res - 1:
        • Đẩy res[x] vào ngăn xếp
  • Ngược lại, đẩy s[i] vào ngăn xếp
  • Tăng i lên 1
• ans := chuỗi rỗng
• Trong khi ngăn xếp không rỗng:
  • ans := phần tử đỉnh ngăn xếp + ans
  • Lấy phần tử ra khỏi ngăn xếp
• Trả về ans

Ví dụ (C++):

Xem triển khai sau để 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; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << ob.decodeString("1[ba]2[na]"); 
    return 0;
}

Đầu vào

"1[ba]2[na]"

Đầu ra

"banana"