Lintcode - Expression Expand

Given an expressionsincludes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

Example

s =abc3[a]returnabcaaa
s =3[abc]returnabcabcabc
s =4[ac]dy, returnacacacacdy
s =3[2[ad]3[pf]]xyz, returnadadpfpfpfadadpfpfpfadadpfpfpfxyz

Analysis

Recursion solution is straightforward, the string can be partitioned into each '[' and ']'. Taking the last example for instance, 3[2[ad]3[pf]]xyz, can be partitioned into 3[2[ad]3[pf]] and xyz. And 3[2[ad]3[pf]] to be 2[ad] and 3[pf] inside 3[]. This solution involves the finding the matching index of the closing bracket.

The non-recursion solution involving using the stack. The stack needs to store Object type element, because it needs to store integer and strings. whenever the closing bracket is found. The stack is pop until a integer is found. This would be the pattern to be repeated. And then the integer is popped as a multiplier for the pattern.

Also the two solutions differ in when to partition or pop the stack. In recursion solution, the partition is triggered when '[' is encountered. In non-recursion solution, the stack is popped when ']' is encountered.

Solution 1: recursion solution

public String expressionExpand(String s) {
    StringBuilder result = new StringBuilder();
    if (s == null || s.length() == 0) {
        return result.toString();
    }

    int number = 0;
    int degree = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetter(c)){
            result.append(c);
        } else if (Character.isDigit(c)){
            number = (int) (number * Math.pow(10, degree) + (c - '0'));
            degree++;
        } else if (c == '[') {
            int indexOfMatchingClosingBracket = findMatchingClosingBraket(s, i);
            result.append(repeat(number, expressionExpand(s.substring(i + 1, indexOfMatchingClosingBracket))));
            i = indexOfMatchingClosingBracket;
            number = 0;
            degree = 0;
        }
    }
    return result.toString();
}

public int findMatchingClosingBraket(String str, int startIndex){
    int index = 0;
    int count = 0;
    for (int i = startIndex; i < str.length(); i++){
        if (str.charAt(i) == ']'){
            count--;
            if (count == 0){ 
                index = i; 
                break;
            }
        }
        if (str.charAt(i) == '['){
            count++;
        }            
    }

    return index;
}


public String repeat(int number, String str) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < number; i++) {
        result.append(str);
    }
    return result.toString();
}

Solution 2: Non-recursive solution

public String expressionExpand(String s) {
    StringBuilder result = new StringBuilder();
    if (s == null || s.length() == 0) {
        return result.toString();
    }

    Stack<Object> stack = new Stack<Object>();
    int number = 0;
    int degree = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetter(c)){
            stack.push(String.valueOf(c));
        } else if (Character.isDigit(c)){
            number = (int) (number * Math.pow(10, degree) + (c - '0'));
            degree++;
        } else if (c == '[') {
            stack.push(number);
            number = 0;
            degree = 0;
        } else if (c == ']'){
            String str = popStack(stack);
            Integer repeatNum = (Integer) stack.pop();
            stack.push(repeat(repeatNum, str));
        }
    }

    return popStack(stack);
}

public String popStack(Stack<Object> stack){
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty() && stack.peek() instanceof String){
        sb.insert(0, stack.pop());
    }
    return sb.toString();
}

public String repeat(int number, String str) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < number; i++) {
        result.append(str);
    }
    return result.toString();
}