A full Dance Dance Revolution system has dances requiring a player to step on two different arrows at the same tune (using both feet), and requiring several steps per beat (corresponding to eighth and sixteenth notes). For this project, we will assume something simpler: All dances require stepping on at most one arrow per beat. A step is either a tap. where the player steps on the arrow and then lifts the foot on the same beat, or a freeze, where the player steps on the arrow on one beat, and then keeps it there, lifting it off at a later beat. We have acquired some Dance Dance Revolution software that will display on a screen the sequence of arrows for a dance. The software requires as input a string of characters: each character is an instruction for what to display for one beat of the song. The characters are: 1. d. u. or r. meaning to display an arrow indicating that the dancer should tap the left. down. up. or right arrow on the dance pad. L. D. u. or R. meaning to display an symbol indicating that the dancer should freeze a foot on the left. down. up. or right arrow on the dance pad.., meaning to display nothing for this beat, indicating that the dancer is not required to step anywhere for this beat. (Notice that the instructions uuud and uuud are different. The first means "tap the up arrow for each of the first three beats, then tap the down arrow", while the second means "put your foot on the up arrow on the first beat, hold it there until you lift it off on the thud beat, then tap the down arrow".) Now for the bad news: The artists who design the dances are used to expressing them a different way. For them, a dance is expressed as a string like u//d/3r///d/. where a slash terminates every beat. This means "For the first beat, tap up. Nothing is required for the second beat. For the thud beat, tap down. Starting on the fourth beat, freeze on the right arrow for three beats (the fourth, fifth, and sixth). For the seventh beat, tap down." Your assignment is essentially to convert a dance from the artists' representation to the sequence of instructions the Dance Dance Revolution software wants. For example, the dance u//d/3r///d/should be converted to the instructions u. dRRRd. Let's define the syntax of the artists' dance strings you are to convert. A direction is one of these eight letters: L1DdUuRr. A digit is one of the ten digit characters 0 through 9. A beat is any one of the followmg: a slash (/) a direction followed by a slash A a digit followed by a direction followed by a slash two digits followed by a direction followed by a slash A syntactically correct dance is a sequence of zero or more beats. Here are some examples of syntactically correct dances: the empty string has zero beats Here are the semantics of a syntactically correct dance, expressed as how the dance is converted to instructions for the Dance Dance Revolution software: Each beat will convert to one instruction character. Although the case of an instruction letter matters in the instruction string (distinguishing a tap from a freeze), the case of a letter in the syntactically correct dance string is irrelevant. Beats are converted as follows: If no freeze is in effect, a beat consisting of only a slash is converted to. (i.e.. a period). If no freeze is in effect, a beat consisting of a direction followed by a slash is converted to the lower case version of the direction letter. If a beat consists of one or two digits followed by a direction followed by a slash, the digit(s) are interpreted as a decimal number denoting the number of beats a freeze is to be in effect, starting with the current beat. Each beat for which a freeze is in effect is converted to the upper case version of the direction letter that started the freeze. As examples, the dance u/u/u/D/converts to the instructions uuud, the dance 3u///D/converts to uuud, and the dance u//d/3r///d/converts to u.dRRRd. If we are to successfully convert a syntactically correct dance, it must meet a few additional constraints that go beyond its just being syntactically valid. (This is akin to a sentence like "The orange truth ate moonbeams." being syntactically correct English, but meaningless, since it violates semantic constraints like the fact that truth has no color, truth can't eat. and moonbeams can't be eaten.) In particular, although dances like 3r/u/d/and 5r//and 0r/are syntactically correct, once we try to interpret then first beats as freezes, they violate our concept of what a freeze should mean. Therefore, we introduce one more concept: A dance is convertible if the following conditions all hold: The dance is syntactically correct. For all beats for which a freeze is in effect, except the first, the beat consists only of a slash. (Thus, d/3 r///is convertible, but d/3r//u/is not: If we're dancing with only one foot and our foot is frozen to the right arrow, it can't also tap any arrow.) All beats for which a freeze is in effect must be in the dance: in other words, the dance string can't end prematurely. (Thus. d/3r///is convertible, but d/3r//is not.) For this project, you will implement the following two functions, using the exact function names, parameter types, and return types shown in this specification. (The parameter names may be different if you wish.) This function returns true if its parameter is a syntactically correct dance, and false otherwise. If the parameter dance is convertible, the function sets instructions to the converted form of the dance, leaves badBeat unchanged, and returns 0. In all other cases, the function leaves instructions unchanged. If dance is not syntactically correct, the function leaves badBeat unchanged and returns 1. If dance is syntactically correct but ends prematurely. badBeat is set to one more than the number of beats in the string, and the function returns 2. If dance is syntactically correct but a beat specifies a freeze of length less than 2. badBeat is set to the number of that beat (where the first beat of the whole dance is number 1. etc.), and the function returns 3. If dance is syntactically correct but while a freeze is in effect, a beat not consisting of only a slash is present. badBeat is set to the number of that beat, and the function returns 4. If the dance is syntactically correct but not convertible for more than one reason, report the leftmost occurring problem. (For example, if dance is 3r//u/ed//2u/. set badBeat to 3 and return 4. In a case like 3r//ed/. you must set badBeat to 3. but it's your choice whether you return 3 (length of a freeze must be at least 2) or 4 (third beat must consist of only a slash), smce neither error occurs earlier than the other.) A full Dance Dance Revolution system has dances requiring a player to step on two different arrows at the same tune (using both feet), and requiring several steps per beat (corresponding to eighth and sixteenth notes). For this project, we will assume something simpler: All dances require stepping on at most one arrow per beat. A step is either a tap. where the player steps on the arrow and then lifts the foot on the same beat, or a freeze, where the player steps on the arrow on one beat, and then keeps it there, lifting it off at a later beat. We have acquired some Dance Dance Revolution software that will display on a screen the sequence of arrows for a dance. The software requires as input a string of characters: each character is an instruction for what to display for one beat of the song. The characters are: 1. d. u. or r. meaning to display an arrow indicating that the dancer should tap the left. down. up. or right arrow on the dance pad. L. D. u. or R. meaning to display an symbol indicating that the dancer should freeze a foot on the left. down. up. or right arrow on the dance pad.., meaning to display nothing for this beat, indicating that the dancer is not required to step anywhere for this beat. (Notice that the instructions uuud and uuud are different. The first means "tap the up arrow for each of the first three beats, then tap the down arrow", while the second means "put your foot on the up arrow on the first beat, hold it there until you lift it off on the thud beat, then tap the down arrow".) Now for the bad news: The artists who design the dances are used to expressing them a different way. For them, a dance is expressed as a string like u//d/3r///d/. where a slash terminates every beat. This means "For the first beat, tap up. Nothing is required for the second beat. For the thud beat, tap down. Starting on the fourth beat, freeze on the right arrow for three beats (the fourth, fifth, and sixth). For the seventh beat, tap down." Your assignment is essentially to convert a dance from the artists' representation to the sequence of instructions the Dance Dance Revolution software wants. For example, the dance u//d/3r///d/should be converted to the instructions u. dRRRd. Let's define the syntax of the artists' dance strings you are to convert. A direction is one of these eight letters: L1DdUuRr. A digit is one of the ten digit characters 0 through 9. A beat is any one of the followmg: a slash (/) a direction followed by a slash A a digit followed by a direction followed by a slash two digits followed by a direction followed by a slash A syntactically correct dance is a sequence of zero or more beats. Here are some examples of syntactically correct dances: the empty string has zero beats Here are the semantics of a syntactically correct dance, expressed as how the dance is converted to instructions for the Dance Dance Revolution software: Each beat will convert to one instruction character. Although the case of an instruction letter matters in the instruction string (distinguishing a tap from a freeze), the case of a letter in the syntactically correct dance string is irrelevant. Beats are converted as follows: If no freeze is in effect, a beat consisting of only a slash is converted to. (i.e.. a period). If no freeze is in effect, a beat consisting of a direction followed by a slash is converted to the lower case version of the direction letter. If a beat consists of one or two digits followed by a direction followed by a slash, the digit(s) are interpreted as a decimal number denoting the number of beats a freeze is to be in effect, starting with the current beat. Each beat for which a freeze is in effect is converted to the upper case version of the direction letter that started the freeze. As examples, the dance u/u/u/D/converts to the instructions uuud, the dance 3u///D/converts to uuud, and the dance u//d/3r///d/converts to u.dRRRd. If we are to successfully convert a syntactically correct dance, it must meet a few additional constraints that go beyond its just being syntactically valid. (This is akin to a sentence like "The orange truth ate moonbeams." being syntactically correct English, but meaningless, since it violates semantic constraints like the fact that truth has no color, truth can't eat. and moonbeams can't be eaten.) In particular, although dances like 3r/u/d/and 5r//and 0r/are syntactically correct, once we try to interpret then first beats as freezes, they violate our concept of what a freeze should mean. Therefore, we introduce one more concept: A dance is convertible if the following conditions all hold: The dance is syntactically correct. For all beats for which a freeze is in effect, except the first, the beat consists only of a slash. (Thus, d/3 r///is convertible, but d/3r//u/is not: If we're dancing with only one foot and our foot is frozen to the right arrow, it can't also tap any arrow.) All beats for which a freeze is in effect must be in the dance: in other words, the dance string can't end prematurely. (Thus. d/3r///is convertible, but d/3r//is not.) For this project, you will implement the following two functions, using the exact function names, parameter types, and return types shown in this specification. (The parameter names may be different if you wish.) This function returns true if its parameter is a syntactically correct dance, and false otherwise. If the parameter dance is convertible, the function sets instructions to the converted form of the dance, leaves badBeat unchanged, and returns 0. In all other cases, the function leaves instructions unchanged. If dance is not syntactically correct, the function leaves badBeat unchanged and returns 1. If dance is syntactically correct but ends prematurely. badBeat is set to one more than the number of beats in the string, and the function returns 2. If dance is syntactically correct but a beat specifies a freeze of length less than 2. badBeat is set to the number of that beat (where the first beat of the whole dance is number 1. etc.), and the function returns 3. If dance is syntactically correct but while a freeze is in effect, a beat not consisting of only a slash is present. badBeat is set to the number of that beat, and the function returns 4. If the dance is syntactically correct but not convertible for more than one reason, report the leftmost occurring problem. (For example, if dance is 3r//u/ed//2u/. set badBeat to 3 and return 4. In a case like 3r//ed/. you must set badBeat to 3. but it's your choice whether you return 3 (length of a freeze must be at least 2) or 4 (third beat must consist of only a slash), smce neither error occurs earlier than the other.)