Configurar
PAI - Produzir, Aprender, InovarPAI: RecursosParceirosProjetoApoia Empreendedor seta para direitaCliente
Índice
Colabore Contato: carlosarrobaapoie.org | leandroarrobaapoie.org

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. Exemplo

Calcular 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 - BNF

expressao: OpUnario* (inteiro | '(' expressao ')') [OpBinario expressao]
11. Sintaxe - Expressão Regular

(OpUnario* (inteiro | '('expressao')')OpBinario)*OpUnario*(inteiro | '('expressao')')

12. Sintaxe - Diagrama Sintático

DojoExpressaoAritmetica.png
Diagrama Sintático - Exemplos e convenções

Arquivo origem: DojoExpressaoAritmetica.xml.