Um avaliador de expressões matemáticas em F# (usando Active Patterns)

Este post foi originalmente publicado em 2015 (infelizmente, a postagem original não está mais disponível)

Nesse post vamos implementar, passo-a-passo, um avaliador de expressões matemáticas em F#. Para isso, utilizaremos “Active Patterns” – um dos conceitos mais interessantes da linguagem.

Se não está familiarizado com o conceito de “Active Patterns” recomendo fortemente que leia a documentação antes de prosseguir.

Reconhecendo dígitos

Vamos começar a implementação de nosso avaliador de expressões por algo bastante trivial: reconhecer um dígito.

open System

let (|Digit|_|) = function
    | x::xs when Char.IsDigit(x) -> 
        Some(Char.GetNumericValue(x), xs)
    | _ -> None

"10" |> List.ofSeq |> (|Digit|_|)

O que fizemos? Criamos um “active pattern” que verifica se o primeiro caractere de uma lista de caracteres é um dígito. Em caso positivo, retorna uma tupla com a versão “numérica” e a lista dos caracteres que completam a cadeia.

Reconhecendo a parte inteira de um número

Agora que conseguimos reconhecer um dígito, já podemos reconhecer a parte inteira de um número.

let (|IntegerPart|_|) input = 
    match input with 
    | Digit(h, t) ->
        let rec loop acc = function 
            | Digit(x, xs) -> loop ((acc * 10.) + x) xs
            | xs -> Some(acc, xs)
        loop 0. input
    | _ -> None

"10" |> List.ofSeq |> (|IntegerPart|_|)
".34" |> List.ofSeq |> (|IntegerPart|_|)

Bacana! Começamos aqui a ver o poder dos “Active Patterns”. Começamos nossa implementação verificando se a lista de caracteres começa com um dígito. Em caso positivo, iniciamos um loop acumulando um “inteiro” enquanto forem encontrados outros dígitos.

Reconhecendo a parte fracionária de um número

Para reconhecer a parte fracionária usamos uma lógica bem semelhante.

let (|FractionalPart|_|) = function
    | '.'::t-> 
        let rec loop acc d = function 
            | Digit(x, xs) -> loop ((acc * 10.) + x) (d * 10.) xs
            | xs -> (acc/d, xs)
        Some(loop 0. 1. t)
    | _ -> None

"10" |> List.ofSeq |> (|FractionalPart|_|)
".34" |> List.ofSeq |> (|FractionalPart|_|)

A única diferença é que começamos verificando se o primeiro caractere é um ‘.’.

Reconhecendo números

Agora que já conseguimos reconhecer a parte inteira e a parte fracionária, vamos criar mais um “Active Pattern” para juntar as duas partes.

let (|Number|_|) = function
    | IntegerPart(i, FractionalPart(f, t)) -> Some(i+f, t)
    | IntegerPart(i, t) -> Some(i, t)
    | FractionalPart(f, t) -> Some(f, t)
    | _ -> None

"10" |> List.ofSeq |> (|Number|_|)
".35" |> List.ofSeq |> (|Number|_|)
"10.35" |> List.ofSeq |> (|Number|_|)

Um número é criado se a cadeia de caracteres 1) começar com uma parte inteira seguida de uma parte fracionária; 2) começar com uma parte inteira; 3) começar com uma parte fracionária.

Implementando a avaliação de expressões

Temos números. Agora chegou a hora de suportarmos operações matemáticas com eles.

Esse código é baseado no exemplo disponível no site F# News. Entretanto, um pouquinho aprimorado 😉

let evaluate expression = 
    let rec (|Expr|_|) = function
        | Mult(e, t) -> 
            let rec loop l = function 
                | '+'::Mult(r, t) -> loop (l + r) t
                | '-'::Mult(r, t) -> loop (l - r) t
                | [] -> Some(l, [])
                | _ -> None
            loop e t
        | _ -> None
    and (|Mult|_|) = function
        | '+'::Atom(e, t) -> Some(e, t)
        | '-'::Atom(e, t) -> Some(-e, t)
        | Atom(l, '*'::Mult(r, t)) -> Some(l * r, t)
        | Atom(l, '/'::Mult(r, t)) -> Some(l / r, t)
        | Atom(e, t) -> Some(e, t)
        | _ -> None
    and (|Atom|_|) = function
        | Number(e, t) -> Some(e, t)
        | '('::Expr(e, ')'::t) -> Some(e, t)
        | _ -> None

    expression |> List.ofSeq |> (|Expr|_|)

evaluate "2+2/2"

Lindo, não?!

Compartilhe este insight:

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Mais insights para o seu negócio

Veja mais alguns estudos e reflexões que podem gerar alguns insights para o seu negócio:

Comunidades técnicas são sistemas complexos! Assim, não podem ser transformadas de maneira prescritiva. Não é razoável esperar que os comportamentos...
Uma ou duas vezes por ano tenho a oportunidade de encontrar, pessoalmente, o Ayende (líder técnico do projeto do RavenDB)....
Last post, I asked an explanation about the execution result of the following code. using System; using System.Threading.Tasks; using static...
Nessa semana, em uma dessas conversas que valem a pena, surgiu uma breve discussão sobre um texto antigo de Rubem...
I’ve been spending some time learning from the “Designing Data-Intensive Applications” book. I am reading it for the third time,...
Nossos códigos precisam ser fáceis de compilar e testar. Para isso, nada melhor do que começarmos da forma certa, com...

Inscrição realizada com sucesso!

No dia da masterclass você receberá um e-mail com um link para acompanhar a aula ao vivo. Até lá!

A sua subscrição foi enviada com sucesso!

Aguarde, em breve entraremos em contato com você para lhe fornecer mais informações sobre como participar da mentoria.

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano anual do Clube de Estudos:

Crie sua conta

Preencha os dados para iniciar o seu cadastro no plano mensal do Clube de Estudos:

× Precisa de ajuda?