Expressão Aritmética

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:

- (negativo)
* (multiplicação) / (divisão)
+ (soma) - (subtração)

2. Solução Calcular Expressão (ExpressaoAritmetica) => valor

[] => Lista de Tokens
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

EstadoInicial => estado
existe entrada e não deu erro: repete

PegarTipoToken (ExpressaoAritmetica, TipoToken, Lista de Tokens) => entrada, Lista de Tokens, ExpressaoAritmetica
Autômato de Expressão Aritmética (entrada, estado) => estado

return estado pertence a EstadosFinais

4. Aplicar Regras Aplicar Regras (Lista de Tokens, Lista de Regras) => valor

0 => regra
repetir enquanto regra < número de regras na Lista de Regras

Aplicar Lista de Regras (regra) desde o início da Lista de Tokens
conseguiu aplicar regra? 0 => regra: regra + 1 => regra

return valor

5. Dados para Analisar Sintaxe

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

- e estado = 0: 0, 2
inteiro: 1, 0
(: 2, 1
): 3, 1
*: 4, 3
/: 4, 3
+: 4, 4
-: 4, 4

Lista de Tokens: token, Tipo de Token, prioridade

6. Dados para Aplicar Regras Lista de Regras

-unário inteiro: Lista de Tokens [-1 * inteiro] => Lista de Tokens [-unário, inteiro]
(inteiro): Lista de Tokens [inteiro] => Lista de Tokens ['(', inteiro, ')']
inteiro operador prioridade = 3 inteiro: Lista de Tokens [operação entre os inteiros] => Lista de Tokens [inteiro, operador prioridade = 3, inteiro]
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

Analisar Sintaxe gera Lista de Tokens
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
Gerada pelo componente Analisar Sintaxe	regra 0	regra 3	regra 1	regra 2	regra 1	regra 2	regra 3
34, 1, 0 +, 4, 4 (, 2, 1 (, 2, 1 3, 1, 0 +, 4, 4 7, 1, 0 ), 3, 1 *, 4, 3 -, 0, 2 6, 1, 0 ), 3, 1 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 (, 2, 1 (, 2, 1 3, 1, 0 +, 4, 4 7, 1, 0 ), 3, 1 *, 4, 3 -6, 1, 0 ), 3, 1 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 (, 2, 1 (, 2, 1 10, 1, 0 ), 3, 1 *, 4, 3 -6, 1, 0 ), 3, 1 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 (, 2, 1 10, 1, 0 *, 4, 3 -6, 1, 0 ), 3, 1 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 (, 2, 1 -60, 1, 0 ), 3, 1 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 -60, 1, 0 /, 4, 3 4, 1, 0	34, 1, 0 +, 4, 4 -15, 1, 0	19, 1, 0

9. Sintaxe - Autômato Finito

	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]