Как работает рекурсия при распаковке строки RLE с (встроенными) паразитами?

Question

Мне нужно написать код, который распаковывает строки RLE, например

2a4b -> aabbbb

2 (a2 (bc) 4d) -> abcbcddddabcbcdddd

2 (a) 2 (b) -> aabb

Сейчас мой код по большей части правильно распаковывается, но у меня все еще есть некоторые проблемы с паратезами, которые я не могу решить.

У меня есть цикл for, который проходит через строку и проверяет каждый символ.

если символ является '(':

            String substring = decompress(sequence.substring(i+1));

            if (count == 0) {
                count = 1;
            }
            while (count >0){
                reststring.append(substring);
                count--;
                number_count = 0;
            }

            string.append(reststring);

            int counting_open = 0;
            int counting_closed = 0;
            int count_loops = 0;

            for(int j = i; j<sequence.length(); j++){
                if(sequence.charAt(j) == '(') {
                    counting_open += 1;
                }

                else if(sequence.charAt(j) == ')'){
                    break;
                }
            }

            for(int j = i; j<sequence.length(); j++){
                count_loops +=1;
                if(sequence.charAt(j) == ')') {
                    counting_closed += 1;
                    if(counting_open == counting_closed){
                        i = j;
                        break;
                    }
                }

                else if (count_loops == sequence.length()-1){
                    return string.toString();
                }
            }

Он по-прежнему работает со строками, такими как:

2 (2 (ab) ef2 (hi)) или 2 (ab2 (c) e)

Теперь моя проблема связана с такими строками, как:

* * 3 тысячи двадцать-одиной (2a3 (аb) 2 (ба) 2b) * * 1 022

Ожидаемый результат: aaabababbababbaaabababbababbaaabababbababb

Мой вывод: aaabababbababbaaabababbababbaaabababbababbbb

2b повторяется после того, как распаковка уже должна быть сделана, и я не знаю, как правильно решить эту проблему, не вызывая проблему в другом месте.

Можно ли решить это задание таким образом, или я должен начать все заново с другого подхода?

Answer 1

Ваш код не рекурсивный из того, что я вижу.
Я написал некоторый псевдокод, поэтому не ожидайте, что он будет работать идеально, но вот как это должно выглядеть IMO:

String recursive(String s) {
  String result = "";
  for (int i = 0; i < s.length; i++) {
    char c = s.charAt(i);
    if (Character.isDigit(c)) {
      // Search for the closing parantheses index
      int endIndex = getSubStringIndex(s, i);
      String subStringResult = recursive(s.substring(i + 1, endIndex));
      // Multiply the result of recursive substring
      for (int repeatIndex = 0; repeatIndex < Character.getNumericValue(c); repeatIndex++) {
        result += subStringResult;
      }
      i = endIndex;
    } 
    else {
      result += c;
    }
  }
  return result;
}



// From index should be the position of '(' character
int getSubStringIndex(String s, int fromIndex) {
  int index = fromIndex + 1;
  int newOpeningCounter = 0;
  // Search for the index 
  while (index < s.length()) {
    char c = s.charAt(index);
    if (c == '(') {
      newOpeningCounter++;
    }
    else if (c == ')') {
       // If there aren't any new opening parantheses, exit the while
       if (newOpeningCounter == 0) {
          return index;
       }
       // Else the the ')' we found is matching another new '(' we found in the way
       // So we decrease the counter to show the parantheses are closed
       else {
          newOpeningCounter--;
       }
    }

     index++;
  }

   // TODO: handle error
   return null;
}

обратите внимание на вызов метода recursive внутри себя, что делает код рекурсивным