TopcoderArchiveVisit Topcoder
Archive
Algorithm problem

Nestings

Problem statement, definition, constraints, and public examples.

Problem Statement

Many different technical languages use nestings to convey some sort of meaning. Mathematics uses parentheses and brackets very often in expressions to group values. Your method will test whether a given nesting is valid, and if it is, how deep it goes.
To be valid, a nesting must obey the following criteria (quotes for clarity):
1) Every left marker has a CORRECTLY matching right marker (i.e. every '[' has a ']'; described in table below)
2) Nestings cannot be interwoven. (e.g. "{[}]" is not a valid nesting since {} and [] are interwoven) In other words, a right marker must be CORRECTLY matched by the left marker immediately preceding it, which has not already been matched.
3) Every nesting marker in the string must delimit a nesting. All other characters must be letters. For example, "{[}" isn't valid since '[' is a marker that does not delimit a nesting. "asdJLBasdf" is valid since letters can exist anywhere in the string.
The CORRECTLY matched nesting markers are:
Left         Right
<             >
(             )
[             ]
{             }
/*            */
If there is an invalid nesting your method will return -1. Otherwise you will return the deepest nesting level in the input. For example:
Nesting-wise explanations will use numbers to depict nesting depths throughout the given strings.
nested = "" no nestings so deepest nesting level is 0
nested = "<(A)(b)>" nesting-wise this looks like <1(2)1(2)1> so the deepest level would be 2
nested = "<()()>" nesting-wise this looks like <1(2)1(2)1> so the deepest level would be 2
nested = "(/*/)" is invalid(-1) since /* is a valid left marker but the / left over is not a valid marker
nested = "(*)" is invalid(-1) since * is not a letter and it isn't used as part of a nesting marker
As seen in examples above, the nesting depth at any point in a string measures how many sets of markers you are between. If the nesting is valid, your method returns the highest nesting depth occuring in the input string.

Create a class Nestings that contains the method howDeep, which takes a String nested, and returns an int describing the deepest nesting level or -1 if it is invalid.

Definition

Class:
Nestings
Method:
howDeep
Parameters:
String
Returns:
int
Method signature:
int howDeep(String nested)
(be sure your method is public)

Constraints

  • nested will have a length between 0 and 50 inclusive
  • nested will only contain letters (A-Z,a-z) or characters from: "<>(){}/*[]" (quotes for clarity)

Examples

  1. ""
    Returns: 0
    This example is given above.
  2. "<(A)(b)>"
    Returns: 2
    This example is given above.
  3. "(/*/)"
    Returns: -1
  4. "<<<</**/asdf>>>>"
    Returns: 5
  5. "abcd(A(B(C(D)C)B)A)abcd"
    Returns: 4
  6. "([)]"
    Returns: -1
    No interwoven nesting markers allowed.
  7. "([{/**/}])"
    Returns: 4
  8. "("
    Returns: -1
  9. "]["
    Returns: -1
Back to all problems