fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class Solution {
  6.  
  7. public:
  8.     string decodeString(const string &s) {
  9.  
  10.         stack<char> stk;
  11.  
  12.         bool hasBracket = false;
  13.         for (char i: s) {
  14.             if (i == '[') hasBracket = true;
  15.             stk.push(i);
  16.         }
  17.  
  18.         if (!hasBracket) return s;
  19.  
  20.         bool empty_stk_flag = false;
  21.  
  22.         while (!empty_stk_flag) {
  23.  
  24.             string non_repeated_str;
  25.  
  26.             while (!stk.empty() && stk.top() != ']') {
  27.                 non_repeated_str.push_back(stk.top());
  28.                 stk.pop();
  29.             }
  30.  
  31.             reverse(non_repeated_str.begin(), non_repeated_str.end());
  32.  
  33.             vector<string> tokens_between_brackets;
  34.  
  35.             while (!stk.empty()) {
  36.                 if (stk.top() == ']') {
  37.                     stk.pop();
  38.  
  39.                     string token;
  40.                     while (!stk.empty() && stk.top() != ']' && stk.top() != '[') {
  41.                         token += stk.top();
  42.                         stk.pop();
  43.                     }
  44.  
  45.                     reverse(token.begin(), token.end());
  46.                     tokens_between_brackets.push_back(token);
  47.                 } else {
  48.                     int last_index = (int) tokens_between_brackets.size() - 1;
  49.                     if (last_index >= 0) {
  50.  
  51.                         for (char j: tokens_between_brackets[last_index]) {
  52.  
  53.                             stk.push(j);
  54.                         }
  55.  
  56.                         if (!tokens_between_brackets.empty()) {
  57.                             tokens_between_brackets.pop_back();
  58.                         }
  59.  
  60.                     }
  61.                     break;
  62.                 }
  63.             }
  64.  
  65.             reverse(tokens_between_brackets.begin(), tokens_between_brackets.end());
  66.  
  67.             string repeated_token;
  68.  
  69.             while (!stk.empty() && stk.top() != '[') {
  70.                 repeated_token.push_back(stk.top());
  71.                 stk.pop();
  72.             }
  73.  
  74.             reverse(repeated_token.begin(), repeated_token.end());
  75.  
  76.             if (!stk.empty())
  77.                 stk.pop();  //pop '['
  78.  
  79.             string repeat_number_str;
  80.  
  81.             while (!stk.empty() && isdigit(stk.top())) {
  82.                 repeat_number_str += stk.top();
  83.                 stk.pop();
  84.             }
  85.  
  86.             reverse(repeat_number_str.begin(), repeat_number_str.end());
  87.  
  88.             int repeat_number = stoi(repeat_number_str);
  89.  
  90.             string remaining;
  91.             while (!stk.empty() && stk.top() != ']' && stk.top() != '[') {
  92.                 remaining += stk.top();
  93.                 stk.pop();
  94.             }
  95.  
  96.             if (stk.empty())
  97.                 empty_stk_flag = true;
  98.  
  99.             reverse(remaining.begin(), remaining.end());
  100.  
  101.             for (char i: remaining) {
  102.                 stk.push(i);
  103.             }
  104.  
  105.             for (int i = 0; i < repeat_number; ++i) {
  106.                 for (char j: repeated_token) {
  107.                     stk.push(j);
  108.                 }
  109.             }
  110.  
  111.             for (const auto &j: tokens_between_brackets) {
  112.                 for (auto k: j) {
  113.                     stk.push(k);
  114.                 }
  115.                 stk.push(']');
  116.             }
  117.  
  118.             for (char i: non_repeated_str) {
  119.                 stk.push(i);
  120.             }
  121.         }
  122.  
  123.  
  124.         char result[stk.size() + 1];
  125.         result[stk.size()] = '\0';
  126.         int i = stk.size() - 1;
  127.  
  128.         while (!stk.empty()) {
  129.             result[i--] = stk.top();
  130.             stk.pop();
  131.         }
  132.  
  133.         return result;
  134.     }
  135. };
  136.  
  137. int main() {
  138.     auto result = Solution().decodeString("1[a2[c2[d]j]ii]");
  139.  
  140.     for (char i : result) {
  141.         cout << i  ;
  142.     }
  143.     cout << endl << "expected: acddjcddjii" << endl;
  144. }
  145.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
acddjcddjii
expected: acddjcddjii
https://ideone.com/iAjZP7
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!