ถอดรหัสสตริงใน C++

สมมติว่าเรามีสตริงที่เข้ารหัสแล้ว เราต้องคืนค่าสตริงที่ถอดรหัสแล้ว กฎการเข้ารหัสคือ: k[encoded_string] ซึ่งบ่งชี้ว่า encoded_string ภายในวงเล็บเหลี่ยมจะถูกทำซ้ำทั้งหมด k ครั้ง เราสามารถสมมติได้ว่าข้อมูลต้นฉบับไม่มีตัวเลข และตัวเลขใช้เฉพาะสำหรับตัวเลขซ้ำ k เท่านั้น ดังนั้น หากอินพุตเป็น "1[ba]2[na]" ผลลัพธ์จะเป็น "banana"

ขั้นตอนการแก้ปัญหา

• สร้างสแต็กว่างหนึ่งอัน ตั้งค่า i := 0
• while i < ขนาดของสตริง
  • ถ้า s[i] เป็น ']'
    • res := ลบองค์ประกอบจากสแต็กและนำเฉพาะสตริงที่อยู่ภายในวงเล็บเหลี่ยม
    • n := 0
    • while สแต็กไม่ว่าง และค่าบนสุดของสแต็กเป็นตัวเลข ให้รวมตัวเลขเพื่อสร้างจำนวนเต็มจริงเป็น n
    • for j ในช่วง 1 ถึง n
      • for x ในช่วง 0 ถึงขนาดของ res
        • แทรก res[x] ลงในสแต็ก
  • อื่นๆ ให้แทรก s[i] ลงในสแต็ก
  • เพิ่ม i ขึ้น 1
• ans := สตริงว่าง
• while สแต็กไม่ว่าง
  • ans := องค์ประกอบบนสุดของสแต็ก + ans
  • pop จากสแต็ก
• คืนค่า 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; 
    } 
}; 

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

อินพุต

"1[ba]2[na]"

เอาต์พุต

"banana"