Dekomprimieren Sie eine Zeichenfolge mit verschachtelten Strings

Question

Die Zuweisung besteht darin, eine Zeichenfolge zu dekomprimieren. Insbesondere muss der Code für 3 Samples funktionieren, wie im Bild dargestellt.

Mein Code hier funktioniert in den ersten 2 der Proben. Ich bin jedoch nicht in der Lage, die 3. Probe zu erstellen. Wahrscheinlich habe ich das Konzept der Rekursion wahrscheinlich nicht verstanden. Kannst du mir helfen?

import java.util.Scanner; 

public class Compression4 { 

public static void main(String[] args) 
{ 
    Scanner in = new Scanner(System.in); 
    String input=in.next(); 
    System.out.println(uncompress(input)); 

} 
public static boolean flag = true; 

public static String uncompress(String compressedText) 
{ 
    return uncompress(compressedText, "", ""); 
} 
public static String getMultiple(String x, int N) { 
    if (N == 0) return ""; 

    return ""+x+getMultiple(x,N-1); 
} 
public static String uncompress(String text, String count, String output) 
{ 
    if (text.equals("")) 
    { 
     return output; 
    } 
    if(text.charAt(0) == '(') 
    {  
     int FirstIndex = text.indexOf("(")+1; 
     String inner = text.substring(FirstIndex, text.lastIndexOf(")")); 
     //System.out.println(inner); 
     flag = false; 
     return uncompress (inner, count, output); 

    } 
    else if (Character.isLetter(text.charAt(0))) 
    { 
     //letter case - need to take the count we have accrued, parse it into an integer and add to output 
     if (flag==true) 
     { 
       //System.out.println(count);// * text.charAt(0); 

       String s = String.valueOf(text.charAt(0)); 
       output += getMultiple(s,Integer.parseInt(count));       
       count ="1"; 
     }   
     else 
     { 
      //System.out.println(count);// * text.charAt(0); 
      output += getMultiple(text,Integer.parseInt(count)); 
      //System.out.println("output: "+output); 
      count="0"; 
     } 

    } 

    else if(Character.isDigit(text.charAt(0))) 
    { 
     //digit case - need to add to the count but keep as a string because must be parsed later 
     if(flag) 
      count += (""+text.charAt(0)); 
     else 
     { 
      count = "0"; 
      count += (""+text.charAt(0)); 

     } 

    } 

    //parse the *remainder* of the string, one character at a time, so pass in the substring(1) 

    return uncompress(text.substring(1), count, output); 

     } 
} 

Answer 1

Sorry für den langen Code, aber es ist einfacher, mit Code als mit Worten zu erklären.

Premise:

• Ich denke, das Problem als Dolmetscher einer Sprache eine Zeichenfolge zu machen
• die Sprache ist einfach und funktional so rekursive Interpretation möglich

Algorithmus Phasen:

• Zuerst: den Ausdruck tokenisieren (um auf einer höheren Ebene von abstr Aktion)
• Zweitens: analysiert den Ausdruck in Token aufgeteilt nur

Rekursion: die Logik auf der Syntax der Sprache basiert. Leitkonzepte einer Rekursion:

• die Basis Fälle und die rekursiven Fällen
• der Zustand notwendig auf eine einzelne Rekursion (lokale Variablen der Rekursion, diejenigen übergeben als Parameter an die rekursive Methode)
• der Zustand für die Rekursion alle (globale Variablen der Rekursion, die in einer bestimmten Rekursion gelesen/geschrieben werden)

Ich habe viele Kommentare gemacht, um zu erklären, was der Algorithmus tut. Wenn es nicht klar ist, kann ich es besser erklären.

import java.util.ArrayList; 
import java.util.List; 

public class TestStringDecompression { 

    // simpleExpr examples: a | b | 123a | 123b | 123(a) | 123(ab) | 123(ba) | (ab) | (ba) 
    // 11ab = aaaaaaaaaaab = = expression = simpleExpr simpleExpr = 11a b 
    // 4(ab) = abababab = expression = simpleExpr = 4(ab) 
    // 2(3b3(ab)) = bbbabababbbbababab = expression = compositeExpr = 2 (simpleExpr simpleExpr) = 2 (3b 3(ab)) 

    public static void main(String[] args) { 
     System.out.println(new StringInflater().inflate("11ab")); 
     System.out.println(new StringInflater().inflate("4(ab)")); 
     System.out.println(new StringInflater().inflate("2(3b3(ab))")); 
    } 

    public static class StringInflater { 

     // This store the position of the last parsed token 
     private int posLastParsedToken = 0; 

     public String inflate(String expression) { 
      return parse(tokenize(expression), 0, false); 
     } 

     /** 
     * Language tokens: 
     * <ul> 
     * <li>literals: 
     * <ul> 
     * <li>intLiteral = [0-9]*</li> 
     * <li>charLiteral = [ab]</li> 
     * </ul> 
     * </li> 
     * <li>separators: 
     * <ul> 
     * <li>leftParen = '('</li> 
     * <li>rightParen = ')'</li> 
     * </ul> 
     * </li> 
     * </ul> 
     */ 
     private Object[] tokenize(String expression) { 
      List<Object> tokens = new ArrayList<Object>(); 
      int i = 0; 
      while (i < expression.length()) { 
       if ('0' <= expression.charAt(i) && expression.charAt(i) <= '9') { 
        String number = ""; 
        while ('0' <= expression.charAt(i) && expression.charAt(i) <= '9' && i < expression.length()) { 
         number += expression.charAt(i++); 
        } 
        tokens.add(Integer.valueOf(number)); 
       } else { 
        tokens.add(expression.charAt(i++)); 
       } 
      } 
      return tokens.toArray(new Object[tokens.size()]); 
     } 

     /** 
     * Language syntax: 
     * <ul> 
     * <li>simpleExpr = [intLiteral] charLiteral | [intLiteral] leftParen charLiteral+ rightParen</li> 
     * <li>compositeExpr = [intLiteral] leftParen (simpleExpr | compositeExpr)+ rightParen</li> 
     * <li>expression = (simpleExpr | compositeExpr)+</li> 
     * </ul> 
     */ 
     private String parse(Object[] tokens, int pos, boolean nested) { 
      posLastParsedToken = pos; 
      String result = ""; 
      if (tokens[pos] instanceof Integer) { 
       /** it's a intLiteral */ 
       // get quantifier value 
       int repetition = (int) tokens[pos]; 
       // lookahead for (
       if (tokens[pos + 1].equals("(")) { 
        // composite repetition, it could be: 
        // simpleExpr: "[intLiteral] leftParen charLiteral+ rightParen" 
        // compositeExpr: "[intLiteral] leftParen (simpleExpr | compositeExpr)+ rightParen" 
        result = parse(tokens, pos + 1, true); 
       } else { 
        // simple repetition, it could be: 
        // simpleExpr: [intLiteral] charLiteral 
        result = parse(tokens, pos + 1, false); 
       } 
       result = repeat(result, repetition); 
       // evaluate the rest of the expression because syntax allows it 
       if (posLastParsedToken + 1 == tokens.length) { 
        // end of the expression 
        return result; 
       } else { 
        // there are other simpleExpr or compositeExpr to parse 
        return result + parse(tokens, posLastParsedToken + 1, false); 
       } 
      } else if (tokens[pos].equals('(')) { 
       /** it's a leftParen */ 
       // an open paren means what follow this token is considered nested (useful for string to treat as char sequence) 
       return parse(tokens, pos + 1, true); 
      } else if (tokens[pos].equals(')')) { 
       /** it's a rightParen */ 
       // a closed paren, nothing to render 
       return ""; 
      } else { 
       /** it's a charLiteral */ 
       if (nested) { 
        // it's nested between paren, so more parsing is requested to consume next charLiteral or next simpleExpr or compositeExpr 
        return tokens[pos] + parse(tokens, pos + 1, nested); 
       } else { 
        // it's not nested between paren, return charLiteral as is 
        return "" + tokens[pos]; 
       } 
      } 
     } 

     private String repeat(String s, int repetition) { 
      StringBuilder result = new StringBuilder(); 
      for (int i = 0; i < repetition; i++) { 
       result.append(s); 
      } 
      return result.toString(); 
     } 

    } 

}