java - 解压缩具有更多嵌套字符串的字符串

Question

赋值包括解压一个字符串。特别是，代码必须适用于图中所示的 3 个样本。

我的代码适用于前两个示例。但是，我无法提出第三个样本。可能我不明白递归的概念。你能帮帮我吗？

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

抱歉，代码很长，但用代码比用文字更容易解释。

前提:

• 我把这个问题看作是一种语言的解释器来呈现一个字符串
• 语言简单实用，因此可以进行递归解释

算法阶段:

• 首先:标记表达式(在更高的抽象层次上工作)
• 第二步:解析刚刚标记化的表达式

递归:逻辑基于语言的语法。递归的关键概念:

• 基本案例和递归案例
• 单个递归所需的状态(递归的局部变量，那些作为参数传递给递归方法的变量)
• 所有递归的状态(递归的全局变量，那些在某些特定递归中读/写的变量)

我做了很多评论来解释算法的作用。如果不清楚，我可以更好地解释。

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

    }

}