java - 递归字符串解压

Question

我正在尝试解压缩如下所示的字符串:

输入:4(ab)

输出:abababab

输入:11ab

输出:aaaaaaaaaaab

输入:2(3b3(ab))

输出:bbbabababbbbababab

上面的例子都使用下面的递归方法正确地出现了，但是当我输入如下内容时出现问题:

输入:4(ab)a

预期输出:ababababa

输入:2(3b3(ab))a

预期输出:bbbabababbbbbbababa

我意识到问题出现在返回语句“重复返回”的地方。在其当前状态下，递归会继续进行，直到它到达输入字符串的末尾，即使在结束括号之后也是如此。基本上我不知道如何让它在到达结束括号时中断，然后如果还有任何剩余则继续。在 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

使用元组作为递归的返回值，除了累加的字符串外，还提供右括号的索引:

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('');
}