递归字符串解压缩

Question

我正在尝试解压看起来如下的字符串：

输入：4(ab)

输出：abababab

输入：11ab

输出：aaaaaaaaaaab

输入：2(3b3(ab))

输出：bbbabababbbbababab

上述示例都可以使用以下递归方法正确地输出，但是当我输入像这样的内容时会出现问题：

输入：4(ab)a

期望输出：ababababa

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

期望输出：bbbabababbbbabababa

我意识到问题出现在"return repeated"语句中。在当前状态下，递归将继续进行，直到达到输入字符串的末尾，即使是在结束括号之后。基本上，如果达到结束括号，我不知道如何让它停止并继续处理剩余部分。在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));

}

- APL888

---

2(3b3(ab))a 的预期输出是 bbbabababbbbabababa。 - Eric Duminil

有趣的问题。您可以使用递归下降解析器和一点BNF语法。然后，您可以在约10分钟内完成代码。 - Tony Ennis

好的，添加了JavaScript代码示例。 - גלעד ברקן

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

- גלעד ברקן

---

我认为我理解了这个逻辑，但我的Java知识不足以实现它。我尝试添加一个for循环，当遇到一个数字后跟括号时“向前查看”。返回包含在括号内的压缩部分+接下来的任何内容。 类似于： return repeated（直到“））”）+ compressedtext（“））”之后的所有内容）。问题在于，当输入是上面代码中使用的字符串时，“））”出现两次...... 所以我的问题是如何实现这个？谢谢答案！ - APL888

@APL888 谢谢您的评论。我不熟悉Java，让我看看能否编写一个JavaScript版本，这应该不会有太大区别，然后再回复您。 - גלעד ברקן

Answer 2

我注意到的一件事是，在输出"8:"后，当你返回""时，你丢失了最后一个"a"。在那个位置上，尾随字符也应该被处理，但是你不能简单地在那里直接或通过解压它们来返回它们，因为这会导致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;
}

第二种解决方案不使用正则表达式。相反，它做出了一些关于如何处理解压缩的假设：

- 任何没有跟随括号包围部分的数字都可以直接原地解压缩，这是首先完成的 - 括号包围部分通过找到第一个闭合括号来处理 - 然后从那里回到开头搜索开放括号 - 这样就得到了要重复的部分 - 在开放括号的左侧应该有一个数字，然后对其进行搜索和解析 - 现在我们有了所有的信息，构建替换部分并将其放在正确的位置 - 然后搜索下一个闭合括号（如果有），并像上面那样处理 - 如果没有闭合括号，则解压缩字符串

代码：

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

- jCoder

---

很好。我真的很喜欢第一个示例。 - Eric Duminil

Answer 3

我知道这是一个Java问题，但通常在实现之前，我会编写一小段Ruby代码来测试想法。如果有人感兴趣，这是我的代码：

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在他的第一个例子中几乎完全写了同样的东西，所以没有必要重新发明轮子！

- Eric Duminil