Usuários online

sexta-feira, 11 de novembro de 2011

Introdução a Algoritmos - Aula 11/11/2011 (Agenda com Struct)

Agenda com struct

Na aula de ontem introduzimos o conceito de estruturas e vetores de estruturas, bem como alguns comandos de leitura/escrita e manipulação de estruturas em C/C++.

Agora apresentamos uma agenda telefônica completa que usa struct para armazenar as informações de nome e telefone. De quebra, você ainda verá como pode ser feito um menu simples para uma aplicação em C/C++.

SUGESTÃO
Tente alterar a agenda acrescentando mais informações para serem armazenadas, como endereço, cidade, estado, cep, e-mail etc.

LEMBRETE
Esta agenda só funciona enquanto o programa está em execução (tudo está na memória e quando você sair do programa, tudo se perderá, portanto, não se empolgue em cadastrar todos os seus amigos).


#include <cstdlib>
#include <iostream>

using namespace std;

struct agenda {
    int cod;
    char nome[30];
    int tel;
    int vazio; //VAZIO = 0 e DISPONIVEL = 1.
} registros[100];

void cadastrar(int cod, int pos);
void consultar();
int verifica_pos();
void zerar();
int verifica_cod(int cod);
void excluir();

int main(int argc, char *argv[]) {
    zerar();
    int op=0,retorno,codaux,posicao;
    while(op!=4){
       printf("\n\n\t\t\t\t** AGENDA **\n\n\nMENU\n\n1 - Cadastrar\n2 - Consultar\n3 - Excluir\n4 - Sair\n\nOpcao:  ");
       scanf("%d",&op);
       fflush(stdin);
       switch(op) {
           case 1: {                  // CADASTRAR
                posicao=verifica_pos();
                if (posicao!=-1) {
                printf("\nEntre com o codigo desejado\n");
                scanf("%d",&codaux);fflush(stdin);
                   retorno=verifica_cod(codaux);
                   if (retorno==1)
                      cadastrar(codaux,posicao);
                   else
                      printf("\nCodigo ja existente\n");
                }
                else
                  printf("\nA agenda esta cheia\n");  
           break;
           }
         
           case 2: {                  // CONSULTAR
                consultar();
           break;  
           }
         
           case 3: {
                excluir();
           break;
           }
         
           case 4: {
                printf("\n\nTchau\n\n");
           break;
           }
       }
    }
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

void cadastrar(int cod, int pos) {
    pos=verifica_pos();
    registros[pos].cod=cod;
    printf("\nNome:\n");
    gets(registros[pos].nome);
    printf("\nTelefone\n");
    scanf("%d",&registros[pos].tel);
    registros[pos].vazio=1;
    printf("\nCadastro Realizado com Sucesso!\n\n");
}

void consultar() {
    int cont=0, cod;
    printf("\nEntre com o codigo\n");
    scanf("%d",&cod);
    while(cont<=100) {
        if (registros[cont].cod==cod) {
           if (registros[cont].vazio==1) {
              printf("\nNome: %s",registros[cont].nome);
              printf("\nTelefone: %d",registros[cont].tel);
              break;
           }
        }
        cont++;
        if (cont>100)
           printf("\nCodigo nao encontrado\n");
    }                        
}

int verifica_pos() {
    int cont=0;
    while (cont<=100) {
          if (registros[cont].vazio==0)
             return(cont);
          cont++;  
    }
    return(-1);
}

void zerar() {
    int cont;
    for (cont=0;cont<=100;cont++)
        registros[cont].vazio=0;
}

int verifica_cod(int cod) {
    int cont=0;
    while (cont<=100) {
       if (registros[cont].cod==cod)
          return(0);
       cont++;
    }
    return(1);
}

void excluir() {
    int cod, cont=0;
    printf("\nEntre com o codigo do registro que deseja excluir\n");
    scanf("%d",&cod);
   
    while (cont<=100) {
          if (registros[cont].cod==cod)
             if (registros[cont].vazio==1) {
                registros[cont].vazio=0;
                printf("\nExclusao feita com sucesso\n");
                break;
             }
          cont++;
          if (cont>100)
             printf("\nCodigo nao encontrado\n");
    }
}

Introdução a Algoritmos - Aula 11/11/2011 (Gerador de Valores por Extenso - Melhorias)

Gerador de Valores por Extenso - Melhorado

No gerador de valores por extenso anterior, ele só trabalhava com valores inteiros na faixa de 0 a 999. Nesta melhoria proposta, além de trabalhar com valores monetários, a faixa foi passada de inteiro para ponto decimal, assim podemos trabalhar com valores desde R$ 0,00 até R$ 999,99 reais. Além disso, foram corrigidos alguns erros de lógica encontrados no programa anterior. O erro de centenas inteiras, como 200, 300, ..., 900 foi corrigido (destacado em vermelho no código abaixo). Diversos comentários explicativos foram acrescidos ao código, para melhor entendimento.

Como esse é um programa didático, ele não tem muita precisão, já que usa o tipo double para o valor monetário e algumas operações aritméticas a fim de separar os valores da parte inteira e da parte centesimal. Infelizmente, por um problema de arredondamento e de precisão dos tipos float e double, às vezes o valor dos centavos fica diminuído de 1 centavo. Entretanto, volto a frisar, este é um programa didático e não profissional.  Nossa intenção é mostrar ao visitante o que o C/C++ pode fazer.

OBSERVAÇÃO
Não copie, cole e execute simplesmente o código. Procure executá-lo, testá-lo e ver o que ele pode fazer. Depois, tente ler o código e acompanhar o algoritmo, juntamente com os comentários, pois assim você poderá entender a lógica por trás da execução. Isso é de suma importância para o aprendizado de C/C++, bem como de qualquer linguagem de computador.



#include <cstdlib>
#include <iostream>

using namespace std;

char* extenso(int);

int main(int argc, char *argv[])
{
    double n;
    int v_reais;
    int v_centavos;

    printf("Forneca um numero entre 0 e 999.99: ");
    scanf("%lf", &n);

    // separamos o valor lido em reais e centavos
    v_reais = (int) n;
    v_centavos = (int) (n * 100) % 100;
   
    printf("%d \'real(is)\' %d \'centavo(s)\'\n\n", v_reais, v_centavos);
   
    // geramos o valor por extenso
    if(v_reais>0)
        printf("%s", extenso(v_reais));
    if(v_reais>1)
        printf(" reais");
    else
    if(v_reais==1) printf(" real");
    if((v_centavos>0) && (v_reais>0))
        printf(" e %s", extenso(v_centavos));
    else
    if(v_centavos>0)
        printf("%s", extenso(v_centavos));
    if(v_centavos>1)
        printf(" centavos");
    else
    if(v_centavos==1) printf(" centavo");
    printf("\n\n");
   
    //for(n=0;n<=999;n++) printf("%s  ", extenso(n));
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

char* extenso(int num) {
    char *unidades[10] = {
        "", "um", "dois", "tres", "quatro", "cinco", "seis", "sete", "oito",
        "nove"
    };
   
    char *dezenas[19] = {
        "", "dez", "vinte", "trinta", "quarenta", "cinquenta", "sessenta",
        "setenta", "oitenta", "noventa", "onze", "doze", "treze", "quatorze",
        "quinze", "dezesseis", "dezessete", "dezoito", "dezenove"
    };
   
    char *centenas[10] = {
        "", "cento", "duzentos", "trezentos", "quatrocentos", "quinhentos",
        "seiscentos", "setecentos", "oitocentos", "novecentos"
    };
   
    char* s;
    int u, d, c;
   
    s = (char *) calloc(200, sizeof(char));
   
    strcpy(s, ""); // variável inicia vazia
   
    u = num % 10; // unidade
    num = (num - u) / 10;
    d = num % 10; // dezena
    c = (num - d) / 10; // centena
   
    if((c == 1) && (d == 0) && (u == 0)) { // caso especial: valor igual a 100
        strcat(s, "cem"); // caso especial
        return s;
    }
    else
    if((c >= 1) && ((d != 0) || (u != 0))) { // valores entre 101 e 999
        strcat(s, centenas[c]);
        if(d > 0) strcat(s, " e ");
        strcat(s, dezenas[d]);
        if(u > 0) strcat(s, " e ");
        strcat(s, unidades[u]);
        return s;
    }
    else
    {
        if((c == 0) && (d > 0) && (u == 0)) { // valores como 10, 20, ..., 90 etc.
            strcat(s, dezenas[d]);
            if(u > 0) {
            strcat(s, " e ");
            strcat(s, unidades[u]);
        }
        return s;
    }
    else
    if((d > 0) && (d != 1) && (u > 0)) { // valores entre 21 e 99
        strcat(s, dezenas[d]);
        strcat(s, " e ");
        strcat(s, unidades[u]);
        return s;
    }
    else 
    if((c > 0) && (d == 0) && (u == 0)) { // caso especial: centenas redondas como 500, 600 etc.
        strcat(s, centenas[c]);
        return s;
    }
    else
    if((d == 1) && (u > 0)) {
        strcat(s, dezenas[d*10 + u - 1]); // caso especial: valores entre 11 e 19
        return s;
    }
    else
    {
        strcat(s, unidades[u]); // valores entre 0 e 9
        return s;
    }
    }
}

quinta-feira, 10 de novembro de 2011

Projeto RONDON - Ainda dá tempo


VAGAS LIMITADAS

O projeto RONDON teve sua inscrição prorrogada até amanhã, dia 11/11/2011, às 17 horas. Corram, pois só restam 2 (duas) vagas.

É uma grande oportunidade de crescimento e aquisição de conhecimentos 'in situ'.

Procure o CIEC.

quarta-feira, 9 de novembro de 2011

Sistemas de Apoio à Decisão - Aula 09/11/2011 (Decisão Multicritério)

Decisão Multicritério

A decisão multicritério envolve diversos métodos, estatísticos, matemáticos, computacionais etc. Um dos métodos que vamos ter a oportunidade de usar é o ELECTRE I. Também pode ser encontrado um exemplo de aplicação do método aqui. Uma breve definição do método também pode ser encontrada na wikipédia.

Vejamos alguns exemplos:
Agora alguns exercícios

1. Num concurso para uma empreitada pública foi deliberado pela respectiva Comissão de Avaliação que a decisão de adjudicação seria baseada em três critérios: preço, prazo e qualidade técnica da proposta.

a) Par a definição dos pesos d os critérios, a Comissão de Avaliação considerou os critérios “Custo” e “Qualidade Técnica” igualmente importantes e que o critério “Prazo” deveria ter metade da importância dos outros dois.

a1) Determine os valores a atribuir aos pesos dos critérios e que sejam consistentes com estes juízos.

a2) Critique (explicitando as reservas que julgue pertinentes) o processo ad optado para a atribuição dos pesos.

Apresentaram propostas 5 concorrentes, com custos e prazos que se indicam no quadro abaixo.



A Comissão de Avaliação avaliou a Qualidade Técnica das Propostas, numa escala de 0 (pior desempenho) a 100 (melhor desempenho) e decidiu adotar funções de valor lineares para os critérios “Custo ” e “Prazo”, de que resultou a matriz de avaliação local (segundo cada critério) que se apresenta abaixo.



Para o que se segue, admita que se adotaram os seguintes pesos dos critérios:
Custo: 0.375
Prazo: 0.375
Qualidade técnica: 0.25

b) Faça uma análise de dominância e extraia as conclusões que julgue pertinentes.

c) Faça uma proposta fundamentada de adjudicação.

d) Explicite a sua reserva mais significativa quanto à metodologia que adotou para selecionar a proposta vencedora.

e) Qual o preço máximo que deveria ter apresentado a proposta classificada em segundo lugar par a que passasse a vencedora (admitindo que se manteriam inalteradas as avaliações dos outros critérios)?



2. Um Município pretende avaliar quatro alternativas possíveis para a localização de um aterro sanitário. Estudos prévios permitiram agrupar os vários pontos de vista sugeridos pela Assembleia Municipal em três atributos:
C1 Investimento Inicial (em 106 euros)
C2 Custo de Exploração (em 103 euros)
C3 Impacto Ambiental (medido numa escala ordinal)

Obteve-se a seguinte matriz de avaliação local:


Foi ainda consultado um conjunto de peritos no sentido de definir uma função de valor para o critério C3, tendo sido possível concluir que à passagem de uma localização Má para uma localização Boa é atribuído o dobro do valor da passagem de uma localização Boa para outra Muito Boa. Para os outros critérios admitiram-se andamentos lineares para as funções de valor respectivas.
a) Existe alguma decisão dominada? Justifique a resposta.

b) Para apoiar o Município na escolha de uma das alternativas foi feito um inquérito à população que permitiu estabelecer a seguinte ordem de importância d os atributos:
C3 - Mais importante
C1 e C2 - Igualmente importantes

b1) Se atribuísse o peso 0.5 ao critério C3 diga qual a solução que recomendaria se utilizasse um método compensatório.

b2) Para fundamentar melhor a sua proposta à Assembleia Municipal efetue uma análise de sensibilidade ao peso atribuído ao critério C3.

c) Faça uma crítica ao processo de consulta para atribuição de pesos referido na alínea b.

terça-feira, 8 de novembro de 2011

Segurança da Informação - Aula 14/11/2011 (Prova - Valor 40 pontos)

Conforme havia prometido na sala de aula ontem, aqui está nosso primeiro exercício valendo nota. A data limite para postagem das respostas será na próxima segunda-feira, dia 14/11/2011. Estou ciente que a turma está querendo "enforcar" o dia 14, pois na terça-feira, dia 15/11/2011 será feriado. Entretanto, o prazo limite para resposta será até o final de nossa aula na segunda-feira, tendo ou não alunos presentes. Assim sendo, o formulário online para postagem das respostas será bloqueado exatamente ao final de nossa aula do dia 15, vindouro.

Clique em 1º TVC para baixar o teste. Dentro do teste há um link para o formulário de respostas online. Atenção ao responder e enviar o formulário com suas respostas, pois somente o primeiro envio será válido. Quaisquer envios posteriores não serão levados em consideração para nota.

Atenciosamente,

segunda-feira, 7 de novembro de 2011

Sistema de Apoio à Decisão - Aula 07/11/2011 (Teoria dos Jogos 2)


Teoria dos Jogos 2

Devido à interrupção no fornecimento de energia elétrica ocorrida no dia 31/10/2011 não tivemos aula. Assim, hoje, teremos o conteúdo que não pôde ser ministrado naquele dia.

Clique em Sistema de Apoio à Decisão - Aula 31/10/2011 (Teoria dos Jogos 2) para ver o conteúdo perdido.

Segurança da Informação - Aula 07/11/2011 (Intrusão, Vírus e Vermes)

Intrusão, Vírus e Vermes

Devido à interrupção no fornecimento de energia elétrica ocorrida no dia 31/10/2011 não tivemos aula. Assim, hoje, teremos o conteúdo que não pôde ser ministrado naquele dia.

Clique em Segurança da Informação - Aula 31/10/2011 (Intrusão, Vírus e Vermes) para ver o conteúdo perdido.

sábado, 5 de novembro de 2011

Matemática Computacional - Aula 04/11/2011 (Problemas do tipo Carteiro Chinês)

Problemas do tipo "Carteiro Chinês"
Em especial o "Problema do Carteiro Rural"

INTRODUÇÃO


O Problema do Carteiro Rural (PCR) (pesquise também em inglês por Rural Postman Problem) considera que o percurso deve ser garantido sobre um subconjunto de ligações do grafo, partindo e retornando de um vértice origem dado (Lenstra & Rinooy Kan, 1981; Christofides et al., 1984; Corberán, 1994; Corberán, 1998; Corberán et al., 2001; Nobert & Picard, 1996; Eiselt et al., 1995ii; Negreiros, 1996).



O problema de roteamento em arcos capacitados (Capacitated Arc Routing Problem - CARP) consiste em visitar um subconjunto de arestas do grafo que descreve o problema, atendendo às suas demandas.


Aplicações possíveis para o CARP são a coleta de lixo urbano e a inspeção de linhas de força.


O CARP é um problema NP-difícil, mesmo no caso onde existe apenas um veículo (chamado de Problema do Carteiro Rural).


Neste caso, o uso de meta-heurísticas surge como uma estratégia de solução eficiente.


Este artigo apresenta um algoritmo genético híbrido para o CARP, que é testado em instâncias disponíveis na literatura.


Os resultados obtidos até o momento demonstram a eficiência do algoritmo proposto quando comparado com limites inferiores descritos na literatura.  





LEITURA SUGERIDA


Antes de continuar, leia os artigo Um Algoritmo Evolutivo para o Problema de Roteamento em Arcos Capacitados, Problema de Roteamento de Veículos sobre Arcos e Um Modelo de Resolução Para o Problema de Roteirização em Arcos com Restrição de Capacidade, em especial a parte sobre Carteiro Rural (página 47, salvo engano).


Você também pode se interessar pela leitura do artigo A Genetic Algorithm for the Undirected Rural Postman Problem, naturalmente em inglês.


O excelente trabalho Algoritmos para Roteamento de Leituristas merece especial atenção para a explicação de diversas e complexas fórmulas.






PROBLEMAS



O roteamento de leituristas consiste em um problema importante de natureza prática, envolvendo grandes empresas fornecedoras de energia elétrica, água e gás, nas quais trabalhadores são incumbidos de registrar o consumo de cada cliente, dispersos geograficamente nas ruas e avenidas de uma localidade. Esse problema, de difícil tratamento e elevado número de restrições, prevê a elaboração de um conjunto de rotas abertas, pelas quais os leituristas devem percorrer, atendendo a demanda por serviço de leitura. Uma solução ótima para esse problema procura minimizar as seguintes propriedades: 

  • Número de leituristas necessários para atender toda demanda; 
  • O tempo de percurso, ou seja, o tempo utilizado pelo leiturista para se deslocar de uma região a outra sem realizar qualquer leitura; 
  • Violação da carga horária do leiturista.



A motivação desse trabalho provém da demanda por soluções computacionais para esse problema, sobretudo por parte das empresas que se utilizam desse serviço, em virtude de diversos fatores, como: 

  • Dificuldade de obter soluções manualmente; 
  • Reduzida qualidade das soluções atualmente colocadas em prática; 
  • Rápida mudança do cenário consumidor, sobretudo nas metrópoles, onde se verifica uma acentuada verticalização do espaço geográfico; 
  • Necessidade de obter soluções no curto prazo. 




O roteamento de leituristas envolve um conjunto de particularidades inerentes, por exemplo: modo como o serviço de leitura se realiza (U ou Z); presença de segmentos de rua que não requerem leitura; tolerâncias máxima e mínima de carga horária; diferença entre ler e percorrer um segmento de rua. 


A natureza desse problema permite generalizá-lo como um problema de roteamento em arcos que, por sua vez, consiste em determinar um subconjunto ordenado de arestas E’ sobre um grafo  G(V,E) (E’ ⊆ E), atendendo às restrições (de demanda, capacidade, dentre outras) e minimizando determinada função custo. Ao problema de roteamento em arcos encontra-se ligada uma vasta árvore de subproblemas, dos quais o mais conhecido é o Problema do Carteiro Chinês (CPP), o qual pode ser resolvido polinomialmente sobre um grafo não-direcionado.


Problema do Carteiro Chinês (CPP)


Um vídeo introdutório bem simplificado

Um vídeo mais elaborado e mais profundo




Se algumas arestas do grafo são requeridas, enquanto outras não, o problema passa a se denominar Problema do Carteiro Rural (RPP). Foi demonstrado que o RPP é NP-Completo, portanto difícil de obter soluções ótimas para instâncias suficientemente grandes. Se for adicionada ao RPP uma restrição de capacidade, torna-se ainda mais difícil resolvê-lo até a otimalidade. Verifica-se que o problema de roteamento de leituristas (visto anteriormente) é similar ao RPP capacitado. 


Foram constatadas duas heurísticas na literatura para roteamento de leituristas, que utilizam abordagens distintas, antagônicas inclusive, para tratar do problema. Esses algoritmos foram desenvolvidos para resolver os problemas locais nos quais estavam inseridos, logo são dotados de características específicas não compartilhadas. Nesse trabalho esses algoritmos foram denominados RFCS1 (“route first, cluster second”) e CFRS1 (“cluster first, route second”).


Você ainda pode ler (em inglês) o documento Chinese Postman Problem que explica de maneira lúdica o problema do carteiro chinês. Também pode visitar o link http://eie507.eie.polyu.edu.hk/ss-submission/B7a/. O arquivo PDF The directed Chinese Postman Problem contém alguma implementação em linguagem C++.








PROBLEMA PROPOSTO


Resolver o seguinte problema do carteiro chinês


Sortear n pontos, no mínimo 4 e no máximo 10, num plano XY, de forma que os pontos tenham distâncias variadas entre si. Depois, ligar os n pontos aos outros n - 1 pontos, com k arestas (k aleatoriamente definido entre 1 e n - 1).


Determinar a menor distância total para cobrir com um passeio (ou tour) todos os arcos do grafo assim determinado. Obviamente, o circuito (ou ciclo) euleriano, quando existente no grafo, é a solução do carteiro chinês.






SOLUÇÃO


A ideia para a solução do problema proposto é o desenvolvimento de um software (em alguma linguagem visual, como o Visual Studio C#) para a solução e apresentação gráfica dos passos em busca da solução para o problema do Carteiro Chinês.

sexta-feira, 4 de novembro de 2011

Introdução a Algoritmos - Aula 04/11/2011 (Gerador de Valores por Extenso)

Gerador de Valores por Extenso

Estudar um gerador de valor por extenso é muito interessante. Podemos aprender como trabalhar com ponteiros em C/C++, usar funções para string, estruturas de decisão aninhadas, vetores de strings, e é claro, lógica computacional.

O presente gerador é bem simples e trabalha somente com números inteiros e com valores no intervalo 0 a 999. Entretanto, geradores assim são muito usados no comércio para gerar valores de notas fiscais, portanto, se quisermos um gerador profissional ele deverá trabalhar com valores que contenham centavos e com uma faixa de valores bem maior, como R$ 9.999.999.999,99 (nove bilhões e novecentos e noventa e nove milhões e novecentos e noventa e nove mil e novecentos e noventa e nove reais e noventa e nove centavos... ufa!).

Vamos ao código:


#include <cstdlib>
#include <iostream>

using namespace std;

char* extenso(int);

int main(int argc, char *argv[])
{
    int n;

    printf("Forneca um numero entre 0 e 999: ");
    scanf("%d", &n);
    printf("\n\nValor por extenso = %s\n\n", extenso(n));
 
    //for(n=0;n<=999;n++) printf("%s  ", extenso(n));
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

char* extenso(int num) {
    char *unidades[10] = {
        "", "um", "dois", "tres", "quatro", "cinco", "seis", "sete", "oito",
        "nove"
    };
 
    char *dezenas[19] = {
        "", "dez", "vinte", "trinta", "quarenta", "cinquenta", "sessenta",
        "setenta", "oitenta", "noventa", "onze", "doze", "treze", "quatorze",
        "quinze", "dezesseis", "dezessete", "dezoito", "dezenove"
    };
 
    char *centenas[10] = {
        "", "cento", "duzentos", "trezentos", "quatrocentos", "quinhentos",
        "seiscentos", "setecentos", "oitocentos", "novecentos"
    };

    char* s;
    int u, d, c;
 
    s = (char *) calloc(200, sizeof(char));
 
    strcpy(s, ""); // variável inicia vazia
 
    u = num % 10;         // unidade
    num = (num - u) / 10;
    d = num % 10;         // dezena
    c = (num - d) / 10;   // centena
 
    if((c == 1) && (d == 0) & (u == 0)) {
        strcat(s, "cem"); // caso especial
        return s;
    }
    else
    if((c >= 1) && ((d != 0) || (u != 0))) {
        strcat(s, centenas[c]);
        if(d > 0) strcat(s, " e ");
        strcat(s, dezenas[d]);
        if(u > 0) strcat(s, " e ");
        strcat(s, unidades[u]);
        return s;
    }
    else
    {
        if((d > 0) && (u == 0)) {
            strcat(s, dezenas[d]);
            if(u > 0) {
                strcat(s, " e ");
                strcat(s, unidades[u]);
            }
            return s;
        }
        else
        if((d > 0) && (u > 0)) {
            strcat(s, dezenas[d]);
            strcat(s, " e ");
            strcat(s, unidades[u]);
            return s;
        }
        else
        if((d == 1) && (u > 0)) {
            strcat(s, dezenas[d*10 + u - 1]); // caso especial
            return s;
        }
        else
        {
            strcat(s, unidades[u]);
            return s;
        }
    }
}

quinta-feira, 3 de novembro de 2011

Introdução a Algoritmos - Aula 03/11/2011 (Analisador de Expressões)

Analisador de Expressões Descendente

Um analisador de expressões é um excelente código para estudarmos diversas funções que trabalham com string e chamadas de função em C/C++. O código abaixo é de um analisador simples, capaz de trabalhar com os seguintes operadores aritméticos:

  • + adição -- por exemplo, 2+4
  • - subtração -- por exemplo, 2-4
  • * multiplicação -- por exemplo, 2*4
  • / divisão -- por exemplo, 2/4
  • ^ exponenciação -- por exemplo, 2^4
  • % módulo (resto da divisão) -- por exemplo, 2%4
  • ( e ) parênteses -- por exemplo, 2+(4-3)

Divirta-se primeiro com o código, que roda perfeito no Dev-C++ e depois tente entender como funciona um Analisador de Expressões Descendente. Em outra oportunidade, melhoraremos o código e acrescentaremos novas funcionalidades, como a possibilidade de usar variáveis e acréscimos de funções como logaritmos, senos, cossenos etc.

Bom estudo!

#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>

#define DELIMITADOR 1
#define VARIAVEL 2
#define NUMERO 3

char *prog;
char token[80];
char tok_type;
           
void eval_exp(double *answer);
void eval_exp2(double *answer);
void eval_exp3(double *answer);
void eval_exp4(double *answer);
void eval_exp5(double *answer);
void eval_exp6(double *answer);
void atom(double *answer);
void get_token(void);
void putback(void);
void unary(char o, double *r);
void serror(int error);
int isdelim(char c);

void eval_exp(double *answer)
{
   get_token();
   if(!token)
   {
      serror(2);
      return;
   }
   eval_exp2(answer);
}

void eval_exp2(double *answer)
{
   register char op;
   double temp;

   eval_exp3(answer);
   while ( (op = *token) == '+' || op == '-')
   {
      get_token();
      eval_exp3(&temp);
      switch(op) {
         case '-':
            *answer = *answer - temp;
            break;
         case '+' :
            *answer = *answer + temp;
            break;
      }
   }
}

void eval_exp3(double *answer)
{
   register char op;
   double temp;

   eval_exp4(answer);

   while ((op=*token) == '%' || op == '/' || op =='*')
   {
      get_token();
      eval_exp4(&temp);
      switch (op) {
         case '*':
            *answer = *answer * temp;
            break;
         case '/':
            *answer = *answer / temp;
            break;

         case '%':
            *answer = (int)*answer % (int)temp;
            break;
      }
   }
}

void eval_exp4(double *answer)
{
   double temp, ex;
   register int t;

   eval_exp5(answer);
   if (*token=='^') {
      get_token();
      eval_exp4(&temp);
      ex = *answer;
      if (temp==0.0) {
         *answer = 1.0;
         return;
      }
      for (t=(int)temp-1;t>0;--t) *answer = (*answer) * (double)ex;
   }
}

void eval_exp5(double *answer)
{
   register char op;
   op = 0;
   if ((tok_type == DELIMITADOR) && *token=='+' || *token=='-') {
      op = *token;
      get_token();
   }
   eval_exp6(answer);
   if (op=='-') *answer = -(*answer);
}

void eval_exp6(double *answer)
{
   if ((*token=='(')) {
      get_token();
      eval_exp2(answer);
      if (*token != ')')
         serror(1);
      get_token();
   }
   else
      atom(answer);
}
void atom(double *answer)
{
   if (tok_type == NUMERO) {
      *answer = atof(token);
      get_token();
      return;
   }
   serror(0);
}

void putback()
{
 char *t;
 t = token;
 for (;*t;t++) prog--;
}

void serror(int error)
{
   static char *e[] = {"erro de sintaxe",
                       "falta parenteses",
                       "nenhuma expressao presente"
                      };
   printf("%s\n", e[error]);
}

void get_token(void)
{
   register char *temp;
   tok_type = 0;
   temp = token;
   *temp = '\0';
   if (!*prog) return;
   while (isspace(*prog)) ++prog;
   if (strchr("+-*/%^=()", *prog)) {
      tok_type = DELIMITADOR;
      *temp++ = *prog++;
   }
   else if (isdigit(*prog)) {
        while (!isdelim(*prog)) *temp++ = *prog++;
        tok_type = NUMERO;
   }
   *temp = '\0';
}

int isdelim(char c)
{

   if (strchr(" +-*/%^=()", c) || c==9 || c=='\r' || c==0) {
      return 1;
   }
   return 0;
}

main(void)
{
   double answer;
   char *p;

   p = (char *) calloc(100, sizeof(p));
   prog = (char *) calloc(100, sizeof(prog));
 
   if (!p) {
      printf("falha na execucao\n");
      exit(1);
   }

   printf("Entre com uma expressao usando: +, -, *, /, %, ^, ( ou ). Por exemplo: 2+3-4*5/2^10 e tecle ENTER\n\n");
   do {
      printf("> ");
      scanf("%s", prog);
      if (!*prog) break;
      eval_exp(&answer);
      printf(">> %.15f\n\n", answer);
   } while (!*p);
}

LinkWithin

Related Posts Plugin for WordPress, Blogger...

NOSSO OBJETIVO

OBJETIVO

Este blog será usado para divulgação de minhas ideias, notícias sobre tecnologia, disponibilização de links para download de materiais diversos (incluindo materiais didáticos -- que poderão ser usados em minhas aulas e/ou cursos). Gostaria de DEIXAR BEM CLARO que quaisquer materiais disponibilizados através deste blog são, tão somente, para acompanhamento de aulas e/ou cursos, e não constituem de modo algum, aulas na modalidade "ensino à distância" (EAD). Alunos têm total acesso aos materiais disponíveis, mas somente como tutoriais passo a passo. Apostilas disponibilizadas através deste blog não são materiais obrigatórios em disciplinas cursadas ou cursos ministrados.

RESPONSABILIDADE

O autor deste blog não é responsável pelo mau uso, intencional ou não, de qualquer código de programa disponibilizado aqui. Os códigos de programas disponíveis neste blog para download é e serão sempre, e tão somente, para uso didático durante o aprendizado. Seja bem-vindo.