Revision as of 16:53, 6 April 2015

The Problem (in Portuguese)

Crie um analisador lexical (especificação para a ferramenta Flex) que aceite uma lista de faixas musicais, contendo os respectivos títulos, artistas (intérpretes, compositores, etc.), durações e anotações (comentários) e que indique qual o número de faixas com mais de 3 minutos, para cada artista presente na colecção. Algumas linhas começam com espaços brancos e correspondem a comentários do dono da colecção relativamente à faixa anterior e devem ser ignoradas.

Cada uma das linhas com informação tem os seguintes campos (separados por um ou mais caracteres de tabulação):

• 1º e 2º campos (cadeias de caracteres): respectivamente, nome do intérprete e nome da faixa: iniciados por um número ou por uma letra, podem conter números ou letras, _ (sublinhado), - (hífen), : (“dois pontos”), e espaços brancos; se um nome estiver entre aspas, pode conter qualquer carácter, excepto a mudança de linha (aspas no interior da cadeia de caracteres são representadas por \").
• 3º campo: duração (formato minuto:segundo – minuto: mín. 2 algarismos, segundo: sempre 2 algarismos). Exemplos: 8923:35, 123:56, 20:22, 2:30, 0:27.

o resto da linha corresponde a anotações (comentários)

Codifique todas as funções auxiliares. Pode utilizar estruturas de dados C++ e da STL (e.g. std::string, std::vector, std::map, etc.). Por simplicidade, considere os caracteres acentuados iguais aos não acentuados.

Exemplo de entrada

Download this example: Playlist.txt.

<text> Lady Gaga Bad Romance 5:08 http://www.youtube.com/watch?v=qrO4YZeyl0I Lady Gaga Telephone 9:31 Kill Bill Current 93 All The Pretty Little Horses 02:38 Nick Cave sings Antonín Dvořák "Symphony No. 9 in E Minor, Op. 95" 41:00 Wikipedia: http://en.wikipedia.org/wiki/Symphony_No._9_(Dvořák) Petrucci Music Library: http://imslp.org/wiki/Symphony_No.9,_Op.95_(Dvořák,_Antonín) Current 93 When the May Rain Comes 3:25 Current 93 Falling 4:22 feat. Björk The Killers Spaceman 4:46 it's all in your mind The Killers Human 4:10 The Killers All The Pretty Faces 4:47 The Killers "Mr. Brightside" 3:46 Yet another... David Bowie Space Oddity 3:48 The original Major Tom Peter Schilling Major Tom 2:50 David Bowie's space oddity some years later Shiny Toy Guns Major Tom 4:11 Is time kind to Major Tom? This is a 2009 cover of the 1983 song (which was inspired by the original from 1969) </text>

Saída correspondente

<text> Lady Gaga 2 Current 93 2 Antonín Dvořák 1 The Killers 4 David Bowie 1 Shiny Toy Guns 1 </text>

Solution

The main idea is to locate the artist names, then the number of minutes. The task is made ambiguous because several characters have multiple functions at different stages in the processing of a given line:

• Numbers and spaces are part of names in artist and track names
• Any character can be in a name if delimited (with double quotes) names are used
• Field delimiters are also used to mark comments

The solution below contains code to track all the above situations.

Download this code: Playlist.l.

<text> %option 8bit noyywrap yylineno %{

1. include <iostream>
2. include <string>
3. include <map>

static std::map<std::string, int> counts; static std::string artist; inline void yyerror(const char *msg) { std::cout << msg << std::endl; } %}

NAME alnum:[- _:[:alnum:]]* MINUTES digit:+ COMMENT ^[ \t]+.*$

%x X_ARTIST X_TITLE X_STRING X_MINUTES

%% {COMMENT}  ; /* ignore */

^{NAME} artist = yytext; BEGIN(X_TITLE);

^\" artist = ""; BEGIN(X_ARTIST); <X_ARTIST>\" BEGIN(X_TITLE); <X_ARTIST>\\\" artist += '"'; <X_ARTIST>. artist += *yytext; <X_ARTIST>\n yyerror("should not happen!");

<X_TITLE>{NAME} BEGIN(X_MINUTES); /* not needed: ignore */

<X_TITLE>\" BEGIN(X_STRING); <X_STRING>\" BEGIN(X_MINUTES); <X_STRING>.|\\\"  ; /* not needed: ignore */ <X_STRING>\n yyerror("should not happen!");

<X_MINUTES>{MINUTES} {

                                 int minutes = strtol(yytext, NULL, 10);
                                 if (minutes > 2) counts[artist]++;
                               }

<X_MINUTES>":".*$ BEGIN(INITIAL);

<X_TITLE,X_MINUTES>\t+  ; <INITIAL,X_TITLE,X_MINUTES>. yyerror("should not happen!"); \n  ; /* ignore */ %%

int main() {

 yylex();
 for (std::map<std::string, int>::iterator it = counts.begin();
      it != counts.end(); it++) {
   std::cout << it->first << " " << it->second << std::endl;
 }

} </text>