Dojo #34: Expressão Aritmética Exemplo de uso de Autômato Finito para o Kata Expressão Aritmética realizado em 23 de setembro de 2009 na Reunião #34 do Dojo Rio
1. Problema

Calcular Expressão Aritmética

Calcular fazendo operações de soma, subtração, multiplicação e divisão de números inteiros, incluindo negativos e podendo usar parênteses. Para calcular o valor da expressão o parênteses tem maior prioridade que qualquer operação.


As operações obedecem as seguintes prioridades:
  1. - (negativo)
  2. * (multiplicação) / (divisão)
  3. + (soma) - (subtração)
2. Solução Calcular Expressão (ExpressaoAritmetica) => valor
  1. [] => Lista de Tokens
  2. Analisar Sintaxe (ExpressaoAritmetica, Autômato de Expressão Aritmética, EstadoInicial, EstadosFinais, TipoToken): Aplicar Regras (Lista de Tokens, Lista de Regras) => valor
3. Analisar Sintaxe

Analisar Sintaxe (ExpressaoAritmetica, Autômato de Expressão Aritmética, EstadoInicial, EstadosFinais, TipoToken) => Lista de Tokens

  1. EstadoInicial => estado
  2. existe entrada e não deu erro: repete
    1. PegarTipoToken (ExpressaoAritmetica, TipoToken, Lista de Tokens) => entrada, Lista de Tokens, ExpressaoAritmetica 
    2. Autômato de Expressão Aritmética (entrada, estado) => estado
  3. return estado pertence a EstadosFinais
4. Aplicar Regras Aplicar Regras (Lista de Tokens, Lista de Regras) => valor
  1. 0 => regra
  2. repetir enquanto regra < número de regras na Lista de Regras
    1. Aplicar Lista de Regras (regra) desde o início da Lista de Tokens
    2. conseguiu aplicar regra? 0 => regra: regra + 1 => regra
  3. return valor
5. Dados para Analisar Sintaxe
DojoExpressaoAritmeticaAF.png 0 => EstadoInicial
[1] => EstadosFinais

Autômato de Expressão Aritmética (entrada, estado) => estado
0, 0 : 0
0, 1 : 1
0, 2 :

2, Analisar Sintaxe (ExpressaoAritmetica, Autômato de Expressão Aritmética, EstadoInicial, EstadosFinais, TipoToken)

1, 4 : 0
2, 3 : 1, return
TipoToken (token) => tipo, prioridade
  1. - e estado = 0: 0, 2
  2. inteiro: 1, 0
  3. (: 2, 1
  4. ): 3, 1
  5. *: 4, 3
  6. /: 4, 3
  7. +: 4, 4
  8. -: 4, 4
Lista de Tokens: token, Tipo de Token, prioridade
6. Dados para Aplicar Regras Lista de Regras
  1. -unário inteiro: Lista de Tokens [-1 * inteiro]  => Lista de Tokens [-unário, inteiro] 
  2. (inteiro): Lista de Tokens [inteiro]  => Lista de Tokens ['(', inteiro, ')']
  3. inteiro operador prioridade = 3 inteiro: Lista de Tokens [operação entre os inteiros]  => Lista de Tokens [inteiro, operador prioridade = 3, inteiro] 
  4. inteiro operador prioridade = 4 inteiro: Lista de Tokens [operação entre os inteiros]  => Lista de Tokens [inteiro, operador prioridade = 4, inteiro] 

Lista de Tokens: token, Tipo de Token, prioridade
7. ExemploCalcular Expressão ("34 + ((3 + 7) * -6) / 4") => 19
  1. Analisar Sintaxe gera Lista de Tokens
  2. se não houver erro, calcular Expressão Aritmética (Avaliar Regras)
8. Solução do Exemplo

Dada a expressão aritmética "34 + ((3 + 7) * -6) / 4",
Analisar Sintaxe gera a Lista de Token abaixo e
Aplicar Regras gera valor final.


Lista de Tokens: token, Tipo de Token, prioridade
Gerada pelo
componente
Analisar Sintaxe
Transformações da Lista de Tokens pelo componente Aplicar Regras
regra 0 regra 3 regra 1 regra 2 regra 1 regra 2 regra 3
  1. 34, 1, 0
  2. +,  4, 4
  3. (, 2, 1
  4. (, 2, 1
  5. 3, 1, 0
  6. +,  4, 4
  7. 7, 1, 0
  8. ), 3, 1
  9. *,  4, 3
  10. -, 0, 2
  11. 6, 1, 0
  12. ), 3, 1
  13. /, 4, 3
  14. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. (, 2, 1
  4. (, 2, 1
  5. 3, 1, 0
  6. +,  4, 4
  7. 7, 1, 0
  8. ), 3, 1
  9. *, 4, 3
  10. -6, 1, 0
  11. ), 3, 1
  12. /, 4, 3
  13. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. (, 2, 1
  4. (, 2, 1
  5. 10, 1, 0
  6. ), 3, 1
  7. *, 4, 3
  8. -6, 1, 0
  9. ), 3, 1
  10. /, 4, 3
  11. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. (, 2, 1
  4. 10, 1, 0
  5. *, 4, 3
  6. -6, 1, 0
  7. ), 3, 1
  8. /, 4, 3
  9. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. (, 2, 1
  4. -60, 1, 0
  5. ), 3, 1
  6. /, 4, 3
  7. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. -60, 1, 0
  4. /, 4, 3
  5. 4, 1, 0
  1. 34, 1, 0
  2. +,  4, 4
  3. -15, 1, 0
  1. 19, 1, 0
9. Sintaxe - Autômato Finito
DojoExpressaoAritmeticaAF.png Símbolo Significado
círculo estado
círculo duplo estado final
seta só com destino estado inicial
seta entre estados transição
texto na seta entrada: TipoEntrada [/ ação]
10. Sintaxe - BNFexpressao: OpUnario* (inteiro | '(' expressao ')') [OpBinario expressao]
11. Sintaxe - Expressão Regular(OpUnario* (inteiro | '('expressao')')OpBinario)*OpUnario*(inteiro | '('expressao')')
12. Sintaxe - Diagrama SintáticoDojoExpressaoAritmetica.png
Diagrama Sintático - Exemplos e convenções
Arquivo origem: DojoExpressaoAritmetica.xml.
Dojo #34: Expressão Aritmética {12} Problema Solução Analisar Sintaxe Aplicar Regras Dados para Analisar Sintaxe Dados para Aplicar Regras Exemplo Solução do Exemplo Sintaxe - Autômato Finito Sintaxe - BNF Sintaxe - Expressão Regular Sintaxe - Diagrama Sintático
Índice Local {9}
Projeto Apoie {6} Projeto Apoie Projeto PAS Serviço Web Relacionamentos entre Personagens
Base de Conhecimento {5} Conhecimento Dado Informação consolidada Página Pronta - site apoie.org Pulo do Gato
Contato Projeto Apoie
Linguagem {5}
Javascript {3} Referências e Ferramentas Sintaxe Cheat Sheet
Erlang Quick Sort
LDC {2} LDC LDC - Sintaxe
Definição {9} Erlang Python 3.0 Ruby 1.9.1 - Sintaxe Ruby 1.9.1 - Léxico Shell Lua PHP XML Lazy BNF
If
Dojo {4} Coding Dojo Coding Dojo - Formatos
Soluções Coding Dojo {6} Dojo #34: Expressão Aritmética Dojo #33: Impedimento Dojo #32: Sequência Numérica Dojo #31: Tráfego Dojo #29: Boliche Dojo #28: Jogo da Vida
Dojo Rio
Qualidade {2}
5W {3} 5W2H 5W1H 5W2H - 5W1H - Modelo
PDCA
Componente {5} Componente ExibirLinguagem.htm Gerar Páginas Lista Tabela de Decisões
Paletas {10} Paleta - Mais utilizadas Paleta - Apoie Paleta - Apresentação e Componentes Paleta - Diagramas Paleta - Diagrama Sintático Paleta - Dojo Paleta - Logos Paleta - Projetos Paleta - Setas Paleta - Tecnologia
Evento {4} Pendência Estados de Componentes Scrum Prioridade
Método {5} Oficina Serviço Web Warnier/Orr Basics Apresentar Problema Resolvido Simples x Complexo
Imposto de Renda