java - 递归字符串解压缩

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

输入:4(ab)

输出:abababab

输入:11ab

输出:aaaaaaaaaaab

输入:2(3b3(ab))

输出:bbbabababbbbabababbab

上面的示例全部使用下面的递归方法正确显示，但是当我输入类似内容时会出现问题:

输入:4(ab)a

预期产量:ababababa

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

预期产量:bbbabababbbbababaaba

我意识到在return语句“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));

}

最佳答案

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

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