I need to decode a string recursively encoded as count followed by substring

An encoded string (s) is given, the task is to decode it. The pattern in which the strings are encoded is as follows.

Examples:

Input : str[] = "1[b]" Output : b

Input : str[] = "2[ab] Output : abab

Input : str[] = "2[a2[b]]" Output : abbabb

Input : str[] = "3[b2[ca]]" Output : bcacabcacabcaca

Below is the code I tried to achieve the same. All I know is it can be solved using two stacks.

public class Main {
    public static void main(String[] args) {
        Stack<Interger> s1 = new Stack();
        Stack<String> s2 = new Stack();
        String result = "";
        for(int i = 0; i < args.length; i  ){
            if(Interger.parseInt(args[i]) == 0){
                s1.push(args[i]);
            }
            if(args[i] == 0){
                if(args[i] == ']'){
                   result = s2.pop();
                }
                if(args[i] == '['){
                    continue;
                }
                s2.push(args[i])
            }
        }
    }
}

Can anyone help me what is the efficient way to write code in order to get the expected output?

CodePudding user response：

The idea is to use two stacks, one for integers and another for characters. Now, traverse the string,

1. Whenever we encounter any number, push it into the integer stack and in case of any alphabet (a to z) or open bracket (‘[‘), push it onto the character stack.
2. Whenever any close bracket (‘]’) is encounter pop the character from the character stack until open bracket (‘[‘) is not found in the character stack. Also, pop the top element from the integer stack, say n. Now make a string repeating the popped character n number of time. Now, push all character of the string in the stack.

Below is the implementation of this approach

        import java.util.Stack;
 
      class Test
      {
        // Returns decoded string for 'str'
        static String decode(String str)
        {
        Stack<Integer> integerstack = new Stack<>();
        Stack<Character> stringstack = new Stack<>();
        String temp = "", result = "";
      
        // Traversing the string
        for (int i = 0; i < str.length(); i  )
        {
            int count = 0;
      
            // If number, convert it into number
            // and push it into integerstack.
            if (Character.isDigit(str.charAt(i)))
            {
                while (Character.isDigit(str.charAt(i)))
                {
                    count = count * 10   str.charAt(i) - '0';
                    i  ;
                }
      
                i--;
                integerstack.push(count);
            }
      
            // If closing bracket ']', pop element until
            // '[' opening bracket is not found in the
            // character stack.
            else if (str.charAt(i) == ']')
            {
                temp = "";
                count = 0;
      
                if (!integerstack.isEmpty())
                {
                    count = integerstack.peek();
                    integerstack.pop();
                }
      
                while (!stringstack.isEmpty() && stringstack.peek()!='[' )
                {
                    temp = stringstack.peek()   temp;
                    stringstack.pop();
                }
      
                if (!stringstack.empty() && stringstack.peek() == '[')
                    stringstack.pop();
      
                // Repeating the popped string 'temo' count
                // number of times.
                for (int j = 0; j < count; j  )
                    result = result   temp;
      
                // Push it in the character stack.
                for (int j = 0; j < result.length(); j  )
                    stringstack.push(result.charAt(j));
      
                result = "";
            }
      
            // If '[' opening bracket, push it into character stack.
            else if (str.charAt(i) == '[')
            {
                if (Character.isDigit(str.charAt(i-1)))
                    stringstack.push(str.charAt(i));
      
                else
                {
                    stringstack.push(str.charAt(i));
                    integerstack.push(1);
                }
            }
      
            else
                stringstack.push(str.charAt(i));
        }
      
        // Pop all the element, make a string and return.
        while (!stringstack.isEmpty())
        {
            result = stringstack.peek()   result;
            stringstack.pop();
        }
      
        return result;
    }
 
    // Driver method
    public static void main(String args[])
    {
        String str = "3[b2[ca]]";
        System.out.println(decode(str));
     } 
    }

Output: bcacabcacabcaca

CodePudding user response：

How to decode a string recursively

You need to define a base case and recursive case:

• Base case - the given string doesn't contain square brackets [], therefore no need to process it. The return value is the given string itself.

• Recursive case - we need to determine the indices of opening [ and closing brackets ] and based on that contract a new string.

That's how it could be implemented:

public static String decode(String str) {
    int startOfBrackets = str.indexOf('[');
    
    if (startOfBrackets == -1) { // base case there's no square brackets in the string
        return str;
    }

    int startOfDigits = getFirstDigitsPosition(str);
    int repeatNum = Integer.parseInt(str.substring(startOfDigits, startOfBrackets));
    
    return str.substring(0, startOfDigits)  
        decode(str.substring(startOfBrackets   1, str.length() - 1)).repeat(repeatNum);
}

public static final Pattern SINGLE_DIGIT = Pattern.compile("\\d");

public static int getFirstDigitsPosition(String str) {
    Matcher matcher = SINGLE_DIGIT.matcher(str);
    if (matcher.find()) {
        return matcher.start();
    }
    return -1;
}

main()

public static void main(String[] args) {
    System.out.println(decode("1[b]"));
    System.out.println(decode("2[ab]"));
    System.out.println(decode("2[a2[b]]"));
    System.out.println(decode("3[b2[ca]]"));
}

Output:

abab
abbabb
bcacabcacabcaca