As expressões matemáticas são constituídas essencialmente por uma combinação finita de símbolos sujeita a um determinado conjunto de regras. As mais frequentes envolvem símbolos que representam determinados objectos matemáticos combinados com certos operadores e delimitadores. Por exemplo, em aritmética é frequente encontrarem-se expressões como "1+2^2*3-4*(1+2)". Esta expressão avalia-se em 1. De facto, em primeiro lugar é avaliada a expressão que se encontra delimitada por parêntesis, vindo "1+2^2*3-4*3". De seguida, avalia-se a potência "2^2", vindo "1+4*3-4*3", e depois processam-se as multiplicações, advindo "1+12-12". Após serem avaliadas as somas segue-se o resultado. Em teoria de conjuntos, são consideradas expressões como "{1,4} uni {1,2} int ({2,3} uni {3,4})" na qual os operadores uniint representam respectivamente as operações de união e intersecção de conjuntos, respectivamente.

Em termos algorítmicos, a avaliação de expressões aritméticas não difere muito da avaliação de expressões sobre conjuntos. Em ambas estão definidos os objectos, os operadores e os delimitadores. Os operadores, como + * ou uniint são classificados de acordo com a sua precedência durante a avaliação da expressão onde surgem. Por exemplo, numa expressão aritmética, o operador * é avaliado antes de se proceder à avaliação do operador +. Por seu turno, as sub-expressões que se encontram delimitadas têm precedência sobre todas as outras sub-expressões. Para além da precedência, os operadores classificam-se ainda como sendo unários caso operem sobre um argumento apenas e binários caso sejam aplicados sobre dois operadores. Em aritmética, por exemplo, o operador "-" na expressão "2-1" constitui um operador binário porque actua sobre os argumentos 12. Por outro lado, na expressão "-(1+2)" representa um operador unário que actua sobre o resultado da operações entre parêntesis.

Ambos os tipos de expressão atrás apresentados admitem uma descrição genérica com base nas seguintes produções gramaticais:

E := P
P := F1
P := uopi0 F1
P := P bopi0 F1
F1 := F2
F1 := uopi1 F2
F1 := F1 bopi1 F2.
...
Fk := Fk+1
Fk := bopik Fk+1
Fk := Fk bopik Fk+1
Fm := (E)
Fm := Term

Aqui E consiste no símbolo não terminal que representa a expressão, P e Fk onde k varia desde 1 até à quantidade de precedências m são símbolos não terminais que constituem os argumentos dos operadores, uopik corresponde aos operadores unários e bopik aos operadores binários de precedência k. O símbolo terminal é, portanto, Term. Durante a avaliação das expressões, os símbolos não terminais irão conter os valores correspondentes às respectivas sub-expressões.

Por exemplo, uma expressão simples que envolva os operadores +, -, *, / para as operações habituais, - para o operador unário correspondente à troca de sinal e ^ para a potenciação é construída com base nas seguintes regras:

E := P
P := F1
P := -F1
P := P + F1
P := P - F1
F1 := F2
F1 := F1 * F2
F1 := F1 / F2
F2 := F3
F2 := F2 ^F3
F3 := (E)
F3 := n

onde n corresponde a um número inteiro sem sinal e consiste no único símbolo terminal para além dos parêntesis e operadores. Estas são suficientes para produzir a expressão "1+2^2*3-4*(1+2)". De facto, a aplicação sucessiva da quarta regra permite concluir que "P := P+F1-F1" e, aplicando a primeira e a segunda regras, vem "E := F1+F1-F1". Como "F1 := F2", "F2 := F3" e "F3 := n" então também "F1 := n" e, particularmente, "F1 := 1". Como consequência, "E := 1+F1+F1". Por outro lado, as regras 6 e 7 permitem escrever "F1 := F2*F2". Mas também "F2 := F3 := 1" e portanto "F2 := 3". Então é verdade que "F1 := F2*3" e "E := 1+F2*3-F2*F2". Como "F2" é um símbolo não terminal, o processo continua até ser obtida a expressão.

Por outro lado, a expressão "--3" não é válida uma vez que "E := P := -F1" e as produções que regem a substituição de F1 não contêm o símbolo terminal -. De modo a obter o valor numérico de uma expressão, é suficiente aplicar o processo descrito no parágrafo anterior substituindo cada símbolo terminal pelo resultado da aplicação do operador encontrado a cada um dos argumentos.

Ver exemplos em Interpretador de expressões matemáticas (continuação).

Last edited Jul 3, 2014 at 9:56 PM by SergioMarques, version 8

Comments

No comments yet.