TopCoder problem "CommentNest" used in SRM 268 (Division I Level Three)



Problem Statement

    A C-style multi-line comment (MLC) starts with /* and ends with the first following */ but is unwieldy because it doesn't allow nesting of other multi-line comments. We want to redefine MLC so that, instead of ending with the first following */, it ends with */ such that the intervening characters contain only properly nested /* */ pairs.

More formally we can define an MLC as follows:

  • A <Nester> is a string, possibly empty, that contains no "/*" and no "*/" OR a Nester consists of three concatenated strings, <Nester> <MLC> <Nester>
  • An <MLC> is a string that consists of three concatenated substrings, "/*" + <Nester> + "*/" (Notice that a <Nester> can be an empty string).
We want to pre-process a program by removing all its MLC's. We will use the usual lexical conflict resolution scheme -- always choose and remove the MLC that starts earliest in the program. If several start at the same position, choose and remove the longest of them. Continue starting at the first character after the MLC until the whole file has been parsed.

Create a class CommentNest that contains a method whatsLeft that takes a String[] lines (the lines of a program) as input and returns the number of characters that remain after the MLC's are removed. Each element of lines (including the last) is followed by an end-of-line character; the return should count both the remaining characters from lines and the remaining end-of-line characters.

 

Definition

    
Class:CommentNest
Method:whatsLeft
Parameters:String[]
Returns:int
Method signature:int whatsLeft(String[] lines)
(be sure your method is public)
    
 

Constraints

-lines contains between 1 and 20 elements, inclusive.
-Each element of lines contains between 0 and 50 characters, inclusive.
-Each character in each element of lines is either '/', '*', or a lowercase letter ('a'-'z').
 

Examples

0)
    
{"abc","def"}
Returns: 8
Nothing is removed. There are 6 characters plus 2 end-of-lines.
1)
    
{"a//bc/*/d",  "", "x/*/b"}
Returns: 7
/*/d@@x/*/ is an MLC (where @ denotes end-of-line), since /d@@x/ is a Nester. That leaves 6 characters from the lines plus 1 end-of-line character.
2)
    
{"a/***b///**/*/"} 
Returns: 2
/***b///**/*/ is an MLC, since its **b///**/ is a Nester since it consists of **b// + /**/ + <empty> which is Nester MLC Nester.
3)
    
{"/*/*/abc//*xyz*/*" }
Returns: 6
/*/*/ is an MLC. No longer MLC starts with the first /*. Continuing, we look for an MLC that starts at the a, at the b, at the c, at the /. When we get to the next /, we find /*xyz*/ is the longest MLC that starts there. We continue at the final * which cannot begin a comment. After all the comments we found have been removed, we are left with abc/ and *@ which is a total of 6 characters.
4)
    
{"/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*", "/*abc*/"}
Returns: 3
The MLC that starts at the first character includes all but the final * from the first line. It contains the character '/' nested 12 deep in comments.
5)
    
{"*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/",
 "*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/"}
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8001&pm=3925

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Recursion, String Parsing