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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างสแต็คว่างหนึ่งอัน ตั้งค่า i :=0
• ในขณะที่ฉัน <ขนาดของสตริง
  • ถ้า s[i] คือ ']'
    • res :=ลบองค์ประกอบออกจากสแต็กและรับเฉพาะสตริงที่อยู่ภายในวงเล็บเหลี่ยม
    • n :=0
    • ในขณะที่สแต็กไม่ว่างเปล่า และด้านบนสแต็กเป็นอักขระตัวเลขหนึ่งตัว จากนั้นปรับตัวเลขและสร้างจำนวนเต็มจริงเป็น n
    • สำหรับ j ในช่วง 1 ถึง n
      • สำหรับ x ในช่วง 0 ถึงขนาดของ res
        • แทรก res[x] ลงในสแต็ก
  • มิฉะนั้นให้แทรก s[i] ลงในสแต็ก
  • เพิ่ม i ขึ้น 1
• ans :=สตริงว่าง
• ในขณะที่สแต็กไม่ว่างเปล่า
  • ans :=สแต็คองค์ประกอบด้านบน + 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;
   }
};
main(){
   Solution ob;
   cout << ob.decodeString("1[ba]2[na]");
}

อินพุต

"1[ba]2[na]"

ผลลัพธ์

"banana"