TopCoder problem "BlockCounter" used in TCCC07 Qual 2 (Division I Level Three)



Problem Statement

    

You are given a compressed word that is in one of the following three forms:

  1. A single character 'A' or 'B'. In this case, the uncompressed word is equal to the compressed one.
  2. A string formatted as "ST" (quotes for clarity), where S and T are each compressed words. To uncompress a word of this form, uncompress S and T and return their concatenation.
  3. A string formatted as "(X,S)" (quotes for clarity), where X is a digit between 1 and 9, inclusive, and S is a compressed word. To uncompress a word of this form, uncompress S and return the concatenation of X copies of that uncompressed word.

For example, "(2,A(3,AB))" uncompresses to "AABABABAABABAB", and "A(2,B)" uncompresses to "ABB". The latter example is uncompressed as follows:

  1. "A(2,B)" is in form 2, where S = "A" and T= "(2,B)". S is in form 1 so it's already uncompressed. Next, we uncompress T.
  2. "(2,B)" is in form 3, where X = 2 and S = "B". S is in form 1 so it's already uncompressed. We concatenate 2 copies of it to get "BB".
  3. We concatenate S and T from step 1 to get "ABB".

A maximal continuous sequence of the same letter in a word is called a block. For example, "AABAAABBBAA" contains 5 blocks: AA, B, AAA, BBB, and AA.

You are given a compressed word. Return the number of blocks in the uncompressed form of the word.

 

Definition

    
Class:BlockCounter
Method:countBlocks
Parameters:String
Returns:long
Method signature:long countBlocks(String word)
(be sure your method is public)
    
 

Constraints

-word will contain between 1 and 50 characters, inclusive.
-word will contain only parenthesis '(', ')', digits '1'-'9', letters 'A' and 'B' and commas ','.
-word will be formatted as described in the problems statement.
 

Examples

0)
    
"(2,A(3,AB))"
Returns: 12
The example from the problem statement.
1)
    
"A(1,A)A(5,AAA)"
Returns: 1
In this case the word uncompresses to a string of 18 'A'-s.
2)
    
"ABA(2,ABA)(3,ABA)"
Returns: 13
3)
    
"(3,(2,(1,AB)))B"
Returns: 12

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6381

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10881&pm=6381

Writer:

andrewzta

Testers:

PabloGilberto , vorthys , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, String Parsing