Wiki**3

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.

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)

Saída correspondente

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

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.

%option 8bit noyywrap yylineno
%{
#include <iostream>
#include <string>
#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;
  }
}