Рекурсивной строка декомпрессия

Question

Я пытаюсь распаковывать строки, которые выглядят следующим образом:

Входной сигнал: 4 (аb)

Выход: abababab

Вход: 11ab

Выход: aaaaaaaaaaab

Ввод: 2 (3b3 (ab))

Выход: bbbabababbb bababab

Приведенные выше примеры все приходит правильно используя рекурсивный метод ниже, но возникают проблемы, когда я вход что-то вроде:

Входной сигнал: 4 (аb) а

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

Input : 2 (3B3 (аЬ)) а

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

Я понимаю, что проблемы возникают, когда в го e return statement "return repeat". В текущем состоянии рекурсия продолжается до тех пор, пока она не попадет в конец входной строки даже после окончания круглой скобки. В основном я не знаю, как заставить его сломаться, если достигнет конечной круглой скобки, а затем продолжить, если что-то осталось. В 2 (3b3 (ab)) a оно должно возвращать 2 * (3b3 (ab)) + a, и теперь оно возвращает 2 * (3b3 (ab)) a. Любая помощь очень ценится, так как я не могу обдумать ее.

public static String decompress(String compressedText) throws Exception 
{ 
    //BASE CASE 
    if(compressedText.length() == 1) 
    { 
     if(compressedText.charAt(0) == ')') 
     { 
      System.out.println("1: " + compressedText); 
      return ""; 
     } 
     else 
     { 
      System.out.println("2: " + compressedText); 
      return compressedText; 
     } 

    } 
    //END BASECASE 


    if(compressedText.charAt(0) == '(') 
    { 
     System.out.println("3: " + compressedText); 
     return decompress(compressedText.substring(1));   
    } 


    //IF DOUBLE DIGIT 
    if(Character.isDigit(compressedText.charAt(0)) == true && Character.isDigit(compressedText.charAt(1)) == true) 
    { 
     if(compressedText.charAt(3) != '(') 
     { 
      System.out.println("4: " + compressedText); 
      int i = Integer.parseInt(compressedText.substring(0,2)); 
      String repeated = new String(new char[i]).replace("\0", compressedText.substring(2,3)); 
      return repeated + decompress(compressedText.substring(3)); 
     } 
     else 
     { 
      System.out.println("5: " + compressedText); 
      int i = Integer.parseInt(compressedText.substring(0,2)); 
      String repeated = new String(new char[i]).replace("\0", decompress(compressedText.substring(2))); 
      return repeated; 
     } 

    } 
    //END DOUBLE DIGIT 



    //IF SINGLE DIGIT 
    if (Character.isDigit(compressedText.charAt(0)) == true) 
    { 
     if(compressedText.charAt(1) !='(') 
     { 
      System.out.println("6: " + compressedText); 
      int i = Integer.parseInt(compressedText.substring(0,1)); 
      String repeated = new String(new char[i]).replace("\0", compressedText.substring(1,2)); 
      return repeated + decompress(compressedText.substring(2)); 
     } 
     else 
     { 
      System.out.println("7: " + compressedText); 
      int i = Integer.parseInt(compressedText.substring(0,1)); 
      String repeated = new String(new char[i]).replace("\0", decompress(compressedText.substring(1))); 
      return repeated; 
     } 

    } 
    //END SINGLE DIGIT 

    //IF RIGHT PARENTHESIS 
    if (compressedText.charAt(0) == ')') 
    { 
     if (compressedText.charAt(1) != ')') 
     { 
      System.out.println("8: " + compressedText); 
      return ""; 
     } 
     else 
     { 
      System.out.println("9: " + compressedText); 
      return decompress(compressedText.substring(1)); 

     } 

    } 
    //END 

     System.out.println("10: " + compressedText); 
     return compressedText.charAt(0)+decompress(compressedText.substring(1)); 

} 

Answer 1

Одна вещь, которую я заметил, что вы «потерять» последнее «а», когда вы вернетесь "" после вывода "8:". В этом положении нужно также обрабатывать конечные символы, однако вы не можете просто вернуть их туда - ни прямо, ни путем их распаковки, - потому что это приведет к bbbabaabaababbbabaabaaba.

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

Тем не менее, я подумал о том, как бы решить эту проблему сжатия и разработал два нерекурсивных решения. Возможно, они помогут вам улучшить ваше решение. Замечание: мои решения предполагают, что строка хорошо сформирована, то есть у нее нет несогласованных скобок и т. Д. (Я использовал функцию повтора, которую я поставил в конце своего ответа.)

Первое решение использует регулярное выражение, которое выполняет поиск цифр и следующей части (либо одного символа, либо части, заключенной в скобки, которая не содержит самих скобок). Таким образом, скобки и однократные декомпрессии обрабатываются изнутри наружу.

public static String decompressWithRegex(String s) { 
    if ((s == null) || (s.length() == 0)) { 
     return s; 
    } 
    // pattern for finding number with either bracket-enclosed, char-only part or single char 
    Pattern p = Pattern.compile("(\\d+)((?:[^\\d\\(\\)]{1})|(?:\\([^\\d\\(\\)]+\\)))"); 
    String tmp = s; 
    Matcher m = p.matcher(tmp); 
    // start searching 
    while (m.find(0)) { 
     // first capture group returns count 
     int count = Integer.parseInt(m.group(1)); 
     // second group is string to repeat (if it's bracket-enclosed, then remove brackets) 
     String what = m.group(2).replace("(", "").replace(")", ""); 
     // build replacement part 
     String replacePart = repeat(what, count); 
     // replace it 
     tmp = m.replaceFirst(replacePart); 
     // reset matcher (source of matcher is now the new string) 
     m.reset(tmp); 
    } 
    return tmp; 
} 

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

• любого число, которое не следует кронштейн огороженной части может быть непосредственно распакованные на месте, что делается первым
• кронштейна -enclosed часть обрабатывается путем нахождения первой закрывающей скобки
• затем оттуда обратно, чтобы начать открывающую скобку ищется
• это получает вас часть повторить
• слева от открывающей скобки должна быть числом, которое затем обыскали d разобран
• теперь, когда у нас есть вся информация, запасная часть построена и поставить в нужном месте
• , то следующий закрывающая скобка ищется, если есть, и это обрабатывается, как описано выше
• если нет закрывающей скобки, строка распакованы

Код:

public static String decompressWithSearching(String s) { 
    if ((s == null) || (s.length() == 0)) { 
     return s; 
    } 
    // replace non-groups first 
    for (int i = s.length() - 1; i >= 0; i--) { 
     // find digit that is not followed by bracket 
     if (Character.isDigit(s.charAt(i)) && s.charAt(i + 1) != '(') { 
      // string to repeat is right behind the digit 
      String part = s.substring(i + 1, i + 2); 
      // find complete digit 
      String countStr = ""; 
      int j = i; 
      for (; j >= 0 && Character.isDigit(s.charAt(j)); j--) { 
       countStr = s.charAt(j) + countStr; 
      } 
      int count = Integer.parseInt(countStr); 
      // build replacement part 
      String replacePart = repeat(part, count); 
      // replace part 
      s = s.substring(0, j + 1) + replacePart + s.substring(i + 2); 
     } 
    } 

    // replace nested parts 
    int closing; 
    while ((closing = s.indexOf(')')) > -1) { 
     // find matching opening bracket 
     int opening = s.lastIndexOf('(', closing); 
     // text between is to be repeated 
     String what = s.substring(opening + 1,closing); 
     // find complete digit 
     String countStr = ""; 
     int numPartIndex = opening - 1; 
     while (numPartIndex >= 0 && Character.isDigit(s.charAt(numPartIndex))) { 
      countStr = s.charAt(numPartIndex) + countStr; 
      numPartIndex--; 
     } 
     int count = Integer.parseInt(countStr); 
     // build replacement part 
     String replacePart = repeat(what, count); 
     // replace part 
     s = s.substring(0, numPartIndex + 1) + replacePart + s.substring(closing + 1); 
    } 

    return s; 
} 

Служебный метод для повторения строки:

public static String repeat(String what, int times) { 
    if ((times <= 0) || (what == null) || (what.length() == 0)) { 
     return ""; 
    } 
    StringBuilder buffer = new StringBuilder(times * what.length()); 
    for (int i = 0; i < times; i++) { 
     buffer.append(what); 
    } 
    return buffer.toString(); 
} 

Answer 2

Используйте кортеж для возвращаемого значения рекурсии, который обеспечивает индекс закрывающей скобки в дополнении к накопленной строке:

index 0 1 2 3 4 5 6 7 8 9 10 
str 2 (3 b 3 (a b)) a 

    f(0) 

    => 2 * f(1)[0] add f(f(1)[1] + 1) // f(1)[1] is the closing index 

    f(1) => 3 * b + 3 * f(5)[0] add f(f(5)[1] + 1) 

    => f(5) returns (ab,8) 

    f(1) => bbb + ababab add f(9) // str[9] is closing parenthesis 

    => f(1) returns (bbbababab,9) 

    => 2 * bbbababab add f(10) 

    => bbbabababbbbabababa 

JavaScript-код:

var example = '2(3b3(ab)2(cd3(fg)))ab2(gh2(xz))'; 
 

 
console.log(example); 
 
console.log(decompress(example)); 
 

 
function decompress(s){ 
 

 
    // returns tuple [accumulator, index of closing parenthesis] 
 
    function f(i){ 
 
    
 
    var accum = '', 
 
     mult = '', 
 
     curr = ''; 
 
     
 
    // accumulate all parenthetical groups in this level 
 
    while (i !== s.length){ 
 

 
     // closing parenthesis 
 
     if (s[i] === ')'){ 
 
     
 
     // add the last decompression 
 
     if (curr !== ''){ 
 
      accum += customReplicate(curr,mult); 
 
     } 
 
     
 
     // exit this call 
 
     return [accum,i]; 
 
     } 
 
      
 
     // character is a digit 
 
     if (!isNaN(parseInt(s[i]))){ 
 
     
 
     // add previous decompression 
 
     if (curr !== ''){ 
 
      accum += customReplicate(curr,mult); 
 
      
 
      curr = ''; 
 
      mult = s[i]; 
 
      
 
     } else { 
 
      mult += s[i]; 
 
     } 
 
     
 
     i++; 
 
     
 
     // character is a character 
 
     } else if (s[i] !== '('){ 
 
     
 
     curr += s[i]; 
 
     i++; 
 
     
 
     // parenthetical group 
 
     } else if (s[i] === '('){ 
 
     
 
     // recursive call 
 
     [tempAccum,index] = f(i + 1); 
 

 
     accum += customReplicate(tempAccum,mult); 
 
     mult = ''; 
 
     i = index + 1; 
 
     } 
 
    } 
 
    
 
    return accum + customReplicate(curr,mult); 
 
    } 
 
    
 
    // initialize the recursion 
 
    return f(0); 
 
} 
 

 
function customReplicate(str,times){ 
 
    return new Array(times === '' ? 1 : parseInt(times)) 
 
       .fill(str).join(''); 
 
}

Answer 3

Я понимаю, что это вопрос Java, но я обычно пишу небольшой Ruby c ode, чтобы протестировать идею перед ее внедрением в Java. Если это интересует никого, вот мой код:

def decompress(str) 
    str.gsub!(/(\d+)([a-z])/i){$2*$1.to_i}  # Replace every subtring like "3b" and "11a". 
    while str.include?('(') do 
    str.sub!(/(\d+)\(([a-z]+)\)/){$2*$1.to_i} # Replace the first inner group found 
    end 
    str 
end 

puts decompress("4(ab)")  == "abababab" 
puts decompress("11ab")  == "aaaaaaaaaaab" 
puts decompress("2(3b3(ab))") == "bbbabababbbbababab" 
puts decompress("4(ab)a")  == "ababababa" 
puts decompress("2(3b3(ab))a") == "bbbabababbbbabababa" 
#=> true, true, true, true, true 

@jCoder писал почти точно то же самое в своем первом примере, так что не нужно изобретать велосипед!