TCHS-9-500

Problem Statement

A simple way to compress a string is to encode repeated consecutive substrings as a counter followed by the substring. For example, if X represents a substring, and the string contains a sequence "XX...X", we can compress the sequence as "[DX]", where D is the number of times X is repeated (D is a single digit, i.e., 1 <= D <= 9). X itself might contain some compressed substrings as well. For example, the string "CABABABABABABC" can be compressed as "C[6AB]C" or "C[2[3AB]]C". You are given a String toUncompress. Uncompress toUncompress and return the result. The uncompressed string will contain only uppercase letters ('A'-'Z').

Definition

Class:	SimpleCompressor
Method:	uncompress
Parameters:	String
Returns:	String
Method signature:	String uncompress(String toUncompress)
(be sure your method is public)

Constraints

-

The return value will contain between 1 and 1000 characters, inclusive.

-

The return value will contain only uppercase letters ('A'-'Z').

-

toUncompress will contain between 1 and 50 characters, inclusive.

-

toUncompress will contain only uppercase letters ('A'-'Z'), digits ('1'-'9'), and brackets ('[' and ']').

-

toUncompress will be a properly compressed string.

-

In each occurrence of "[DX]", D will be a single digit, between 1 and 9, inclusive.

-

In each occurrence of "[DX]", X will be a non-empty string.

Examples

0)

"C[6AB]C"

Returns: "CABABABABABABC"

1)

"C[2[3AB]]C"

Returns: "CABABABABABABC"

2)

"CO[1N]TEST"

Returns: "CONTEST"

3)

"[2[2AB]]"

Returns: "ABABABAB"

4)

"AAAAAAAAAAAAAAAAAAAAA"

Returns: "AAAAAAAAAAAAAAAAAAAAA"

import java.util.*;

public class SimpleCompressor {

	public String uncompress(String s) {
		Stack<Integer> opens = new Stack<Integer>();
		for (int m = 0; s.indexOf('[') >= 0; ) {
			for (int j = m; j < s.length(); j++) {
				if (s.charAt(j) == '[')
					opens.push(j);
				else if (s.charAt(j) == ']') {
					int i = opens.pop();
					StringBuilder buf = new StringBuilder();
					buf.append(s.substring(0, i));
					for (int k = 0; k < s.charAt(i + 1) - '0'; k++)
						buf.append(s.substring(i + 2, j));
					m = buf.length();
					buf.append(s.substring(j + 1));
					s = buf.toString();
					break;
				}
			}
		}
		return s;
	}

}