Decompress a string with more nested strings

Question

The assignment consists in decompress a string. In particular, the code has to work for 3 samples as illustrated in the picture.

My code here works in the first 2 of the samples. However, I am not able to come up with the 3rd sample. Probably I did not understand probably the concept of recursion. Can you help me?

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 for the long code but it's more easy to explain with code than with words.

Premise:

• I think to the problem as an interpreter of a language to render a string
• the language is simple and functional so recursive interpretation is possible

Algorithm phases:

• First: tokenize the expression (to work at an higher level of abstraction)
• Second: parse the expression just tokenized

Recursion: the logic is based on the syntax of the language. Key concepts of a recursion:

• the base cases and the recursive cases
• the state necessary to a single recursion (local variables of recursion, those passed as parameters to the recursive method)
• the state for the all recursion (global variables of recursion, those read/write in some specific recursion)

I've made many comments to explain what the algorithm is doing. If it's not clear I can explain it better.

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

    }

}