Connection Status:
Competition Arena > CommentNest

CommentNest

SRM 268 · 2005-10-18 · by dgoodman

SRM 268 · 2005-10-18 · by dgoodman · Recursion, String Parsing
Class Name: CommentNest
Return Type: int
Method Name: whatsLeft
Arg Types: (vector<string>)
Problem Statement

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.

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// + /**/ + 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.

7)
{"/*/*/"}
Returns: 1

/*/*/ is a comment so after it is removed all that remains is the newline.

9)
{"/*/*/","/*/bc/*/d"}
Returns: 2

It is still true that /*/*/ is a comment, but there is now a longer one that starts at the same position: /*/*/@/*/bc/*/ is a comment because the sequence /*/@/*/ is a nested comment. This leaves d and the final newline after the comments are removed.

Submissions are judged against all 74 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CommentNest with a public method int whatsLeft(vector<string> lines) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous