DerivationDisplay

SRM 234 · 2005-03-16 · by AdminBrett

SRM 234 · 2005-03-16 · by AdminBrett · String Parsing

Show categories

Class Name: DerivationDisplay

Return Type: String[]

Method Name: getDerivation

Arg Types: (string)

Problem Statement

  S ::= T | bUa
  T ::= aTb | A | B
  U ::= aU | bU | a | b
  A ::= aA | a
  B ::= bB | b

Displayed above is a Context-Free Grammar (CFG). You begin with the string (quotes for clarity) "S", and apply replacement rules until your resulting string no longer contains any capital letters. The first line above says that S can be replaced with T or bUa. The other lines are similar. You will return a sequence of strings, beginning with "S" and ending with input, where each successive sequence element results from applying one of the replacement rules above. For example, if input is "aaabb" then you will return

 {"S","T","aTb","aaTbb","aaAbb","aaabb"}

Constraints

input will contain between 1 and 50 characters inclusive.
Each character in input will be 'a' or 'b'.
There will be exactly one solution.

Examples

"baabba"
Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

"aaabb"
Returns: {"S", "T", "aTb", "aaTbb", "aaAbb", "aaabb" }

The example above.

"bbba"
Returns: {"S", "bUa", "bbUa", "bbba" }

In the first step, S must be replaced with bUa in order to derive this string. Then the 2 inner b's are added.

"baabba"
Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

"a"
Returns: {"S", "T", "A", "a" }

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

Coding Area

Language: C++17 · define a public class DerivationDisplay with a public method vector<string> getDerivation(string input) · 36 test cases · 2 s / 256 MB per case