C++에서 문자열 디코딩

인코딩된 문자열이 있다고 가정합니다. 디코딩된 문자열을 반환해야 합니다. 인코딩 규칙은 다음과 같습니다. k[encoded_string], 이는 대괄호 안의 encode_string이 정확히 k번 반복되는 위치를 나타냅니다. 원래 데이터에는 숫자가 포함되어 있지 않고 숫자는 반복되는 숫자 k에만 해당한다고 가정할 수 있습니다. 따라서 입력이 "1[ba]2[na]"와 같으면 출력은 "banana"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 빈 스택을 만들고 i :=0으로 설정
• while i <문자열의 크기
  • s[i]가 ']'인 경우
    • res :=스택에서 요소를 삭제하고 대괄호 안에 있는 문자열만 가져옵니다.
    • n :=0
    • 스택이 비어 있지 않고 스택 맨 위가 하나의 숫자 문자인 동안 숫자를 수용하고 실제 정수를 n으로 형성합니다.
    • 1 ~ n
      범위의 j에 대해
      • 0 범위에서 res
        크기까지 x의 경우
        • 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"