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