Aplicação: Avaliador de Expressões Aritméticas

   

         Você já se fez esta pergunta: Como é possível o computador entender e avaliar as expressões digitadas pelo usuário? (Guarde esta pergunta, ela nos conduzirá até o final desta seção).

         A aplicação que apresentamos aqui exemplifica esta importante utilização de pilhas: a avaliação de expressões.

         Queremos, desde já, salientar que este assunto a “Avaliação de Expressões” é por si só um importante tópico da Ciência da Computação e nossa preocupação é, acima de tudo, com a manipulação das pilhas dentro da avaliação de expressões.

 

Código fonte da Aplicação: calc.pas

 

Índice Prático

 

Forma das Expressões [Topo]

 

         No intuito de simplificar nossa aplicação e proporcionar um melhor entendimento da mesma, utilizaremos em nossas expressões apenas os seguintes elementos:

Sendo assim, a expressão: A/(B*(C-D)+E), por exemplo, será válida em nossa aplicação, tendo em vista que esta obedece aos critérios dispostos acima.

 

Dificuldade de Avaliar uma Expressão [Topo]

  

Observando a pergunta que nos foi feita no início da seção, percebemos que para solucioná-la devemos responder a outra pergunta: Quais são as dificuldades na avaliação de uma expressão?

De princípio, dada uma expressão aritmética sabemos que não podemos simplesmente percorrer sua extensão e calcular o resultado, devemos atentar para os parênteses e a prioridade dos operadores. Vejamos as expressões abaixo:

         Assim concluímos que dois fatores contribuem para dificultar a avaliação da expressão:

 

Notação Polonesa [Topo]

   

Percebendo estas dificuldades, o lógico polonês Jan Lukasiewicz, desenvolveu novas formas de representar expressões, onde não existem prioridades e nem a necessidades de parênteses.

De forma resumida, podemos dizer que o lógico polonês criou três formas de representarmos uma expressão de acordo com a posição do operador em relação aos operandos:

Particularmente para o uso em algoritmos computacionais, a notação polonesa reversa tem se mostrado mais eficiente.

A vantagem em se usar a notação polonesa reversa é que, como cada operador aparece imediatamente após os valores que ele deve operar, a ordem em que ele aparece é também a ordem em que deve ser efetuado. Além disto, não existe a necessidade de se usar nenhum parêntese.

Veja abaixo um quadro que compara algumas expressões em cada uma das formas:

 

Notação Infixa

Notação Posfixa

A+B*C

ABC*+

A*(B+C)

ABC+*

(A+B)/(C-D)

AB+CD-/

(A+B)/(C-D)*E

AB+CD-/E*

       

Aplicação

         A partir daqui iremos nos prender a aplicação em si, mostrando cada uma das partes que a compõe.

 

1. Objetivo da Aplicação [Topo]

 

Esta aplicação tem por objetivo o cálculo de expressões a partir da entrada:

 

2. Bibliotecas [Topo]

  

Nesta aplicação utilizamos as bibliotecas crt, pilhachr e pilhspf. A primeira já é bem conhecida, as outras duas tratam-se de duas pilhas sendo que a primeira é de elementos do tipo caracter e a outra é de reais.

 

3. Tipos e Variáveis [Topo]

 

Foi declarado apenas um novo tipo, que foi chamado valores. Este é, na verdade, um vetor de reais onde seus índices são na verdade as letras do alfabeto de A a Z, ele armazenará o conteúdo da variável de acordo com o seu identificador (A a Z).

As variáveis globais declaradas são: o ‘e’ que é a string que armazenará a expressão de entrada; e o ‘v’ que é a variável do tipo valores.

 

4. Rotinas

  

Neste tópico iremos comentar as funções e os procedimentos que compõe a aplicação. Ressaltamos que na verdade estas rotinas é que permitem a realização do objetivo da aplicação, e o corpo do programa não passa de uma interface para manipulação das mesmas.

 

4.1  Função Avalpar [Topo]

 

         Função que avalia se os parênteses na expressão estão corretos, ou seja, se o número de parênteses que abrem é o mesmo dos que fecham, se a posição relativa entre eles está certa. Seu retorno é do tipo lógico (true ou false).

         Veja que para a função esta expressão “((()))” é válida, visto que o número de parênteses e suas posições relativas são corretas. Se ao contrário tivéssemos “(A+B)*C)” ou “)A+B(*C”, a função acusaria falso devido a estas expressões não cumprirem as normas pedidas.

         A idéia principal desta função é aceitar que a expressão é válida e assim procurar uma forma de invalidá-la. Para isto foi utilizada uma pilha de caracteres. Algoritmo funciona da seguinte maneira:

         Após estes passos podemos dizer se a expressão é ou não é válida com relação aos parênteses.

 

 

4.2  Função Avalop [Topo]

  

Esta outra função verifica se o número de operandos (noperando) e o número de operadores (noperador) estão corretos. Seu retorno é do tipo lógico.

Para esta função são inválidas as expressões: “A-B+”, “A+*”, “A/BC”, entre outras. O que podemos perceber comparando estas expressões inválidas com as expressões válidas (“A+B/C”), é que as últimas possuem o número operandos exatamente igual ao número de operadores mais um (noperandos = noperadores +1).

Sendo assim, a expressão age da seguinte maneira:

Após isto a função retorna o valor true ou false.

   

 

4.3 Função Prio [Topo]

   

Esta é uma sub-função que se encontra dentro da função Inparapos, seu objetivo é retornar apenas um valor de 1 a 3, que refletem a prioridade dos operadores através da seguinte classificação:

 

4.4 Função INparaPOS [Topo]

  

Esta é a função que receberá uma expressão da notação infixa e retornará a mesma na notação polonesa reversa (posfixa). Para que isto ocorra é necessário a utilização de uma pilha de caracteres.

O algoritmo da função funciona da seguinte forma:

Após isto tudo, devolvemos a expressão.

 

 

4.5 Procedimento Atribui [Topo]

  

Este procedimento serve apenas para que determinemos valores às variáveis utilizadas em nossa expressão, portanto não se faz importante que percamos tempo explicando seu funcionamento.

O que é importante ressaltarmos aqui é o fato de não termos utilizado os valores na expressão de forma direta, ou seja, nós optamos pela utilização de variáveis. Isto se deve ao fato de que se colocássemos os valores direto na expressão, nossos algoritmos de conversão, de validação e até de cálculo da expressão teriam de ser muito mais intrincados.

Imagine, por exemplo, a expressão “25+10”, como nosso algoritmo verifica caracter a caracter, teríamos de arranjar um modo de encarar ‘2’ e ‘5’ como ‘25’, o mesmo vale para o ‘10’, só este problema já nos basta para percebermos que a utilização de variáveis é muito mais simples. 

 

 

4.6 Função Avalia [Topo]

   

Esta é a função que realmente resolve o problema que nos foi proposto desde o início: a avaliação da expressão, ou seja, sua tarefa é retornar o valor da expressão. Para realizar este feito utilizamos uma pilha de reais.

Abaixo veremos o algoritmo empregado para a resolução do problema:

    

Compiladores, Interpretadores e a Avaliação de Expressões [Topo]

  

Agora podemos perceber a importância da conversão da notação da expressão, já que isto nos auxiliou muito na hora de calcularmos o seu valor, tendo em vista que não nos preocupamos com a precedência dos operadores e com a utilização dos parênteses.

Este fato nos leva a pensar: e se quiséssemos calcular na forma infixa, seria possível?

A resposta é sim, seria possível. Mas o código teria de ser um pouco mais complicado, já que deveria prever a prioridade dos operadores e as implicações da utilização dos parênteses.

O fato de convertermos ou não a expressão é, por exemplo, uma diferença existente entre compiladores e interpretadores.

Em compiladores é mais interessante que a expressão seja convertida para a forma posfixa, pois, como podemos gerar código para posterior utilização, é interessante que o algoritmo de cálculo seja o mais simples possível e, neste caso, o cálculo na forma posfixa nos serve bem.

Em interpretadores já não é tão interessante que utilizemos esta conversão, porque ela demandaria mais tempo na avaliação das expressões, já que seria mais um passo para que a execução ocorresse. Assim um algoritmo mais complexo seria mais eficiente.

Ressaltamos que as comparações acima não são leis imutáveis, na verdade elas variam muito de acordo com a arquitetura do computador, com o projeto do compilador/interpretador e até com a linguagem que vai se utilizar deste processador de linguagem.

 

[Retornar para Atividades]  [Topo]