ContextFreeGrammars2 | Topcoder Archive

Problem Statement

A context free grammar is a set of words represented by a set of derivation rules, each written as
<nonterminal> ::= <expression>
where <nonterminal> is a symbol, and <expression> is a non-empty sequence of symbols (terminals and/or nonterminals) that represents a possible substitution for <nonterminal>. Symbols that never appear on the left side of a rule are called terminals.

If you have several rules for the same nonterminal:
<nonterminal> ::= <expr₀>
<nonterminal> ::= <expr₁>
...
<nonterminal> ::= <expr_n>
it is also possible to write them in a single line, separated by pipes:
<nonterminal> ::= <expr₀> | <expr₁> | ... | <expr_n>

In this problem we will use uppercase letters exclusively for nonterminals and lowercase letters exclusively for terminals. Also, for simplicity, all derivation rules for the same nonterminal will appear in a single line.

Given a specificacion as described above, the set of words that can be derived from a given nonterminal is the set of finite sequences of terminals (lowercase letters) that are the result of iteratively applying rules replacing a nonterminal for the right side of one of its rules. Note that words do not contain nonterminals (uppercase letters).

For example, this specification:
A ::= BD
B ::= bB | b | Bb
D ::= dD | d

we can derive from B the set of words that have one or more b's (b, bb, bbb, etc), from D the set of words that have one or more d's (d, dd, ddd, etc), and from A the set of words that have one or more b's followed by one or more d's (bd, bbd, bddd, bbbddd, etc.).

In this problem you are asked to evaluate the set of words that can be derived from each nonterminal.

You are given the set of rules as a String[], where each element is formatted as described above. Return a String[] with the same number of elements of rules, where element i represents the evaluation of the set of words that can be derived from the nonterminal whose rule is given in element i of rules. If the set of words is empty, the evaluation should be "EMPTY" (quotes for clarity), otherwise it should be "X - Y" (quotes for clarity) where X and Y should be replaced for the minimum and maximum length of a word in the set, respectively, without leading zeroes. If there is no maximum length word, replace Y with a single asterisk ('*'). If X and/or Y would be replaced by an integer greater than 1000000000 (10^9), replace it by ">1000000000" (quotes for clarity) instead. See examples for further clarification.

Definition

Class:: ContextFreeGrammars2
Method:: eval
Parameters:: String[]
Returns:: String[]
Method signature:: String[] eval(String[] rules)
(be sure your method is public)

Constraints

rules will contain between 1 and 26 elements, inclusive.
Each element of rules will contain between 7 and 50 characters, inclusive.
Each element of rules will start with an uppercase letter, followed by " ::= ", followed by a list of one or more expressions separated by " | ", where each expression is a non-empty sequence of lowercase and uppercase letters ('a'-'z' and 'A'-'Z').
The first character of any two elements of rules will be distinct.

Examples

{"A ::= BD",
 "B ::= bB | b | Bb",
 "D ::= dD | d"}

Returns: {"2 - *", "1 - *", "1 - *" }

The example in the problem statement.

{"A ::= BCD | BD | BC | AC | A | BtopcoderB",
 "B ::= b | bCcd | D",
 "D ::= Da"}

Returns: {"10 - 10", "1 - 1", "EMPTY" }

Non-terminals may be used only on the right side of rules.

{"A ::= BBBBBBBBBB", 
 "B ::= CCCCCCCCCC", 
 "C ::= DDDDDDDDDD", 
 "D ::= EEEEEEEEEE",
 "E ::= FFFFFFFFFF",
 "F ::= GGGGGGGGGG",
 "G ::= HHHHHHHHHH",
 "H ::= IIIIIIIIII",
 "I ::= JJJJJJJJJJ",
 "J ::= jjjjjjjjjj",
 "Z ::= B | Bc",
 "X ::= ABCDEFGHIJ | XX"}

Returns: {">1000000000 - >1000000000", "1000000000 - 1000000000", "100000000 - 100000000", "10000000 - 10000000", "1000000 - 1000000", "100000 - 100000", "10000 - 10000", "1000 - 1000", "100 - 100", "10 - 10", "1000000000 - >1000000000", ">1000000000 - *" }

Watch the format.

{"A ::= TOPCODEROPEN", 
 "T ::= O", "O ::= P", "P ::= C", "C ::= D", "D ::= E", "E ::= R", "R ::= N",
 "N ::= topcoderopen"}

Returns: {"144 - 144", "12 - 12", "12 - 12", "12 - 12", "12 - 12", "12 - 12", "12 - 12", "12 - 12", "12 - 12" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.