EXPRESSÕES
ARITMÉTICAS
Inhaúma Neves Ferraz
Departamento de Ciência da Computação
Universidade Federal Fluminense
[email protected]
Sumário
Definições
Avaliação de expressões
Transformação de expressões infixas em pós-fixas



Algoritmo com bastante abstração
Exemplo
Declaração de funções auxiliares
Avaliação de expressões pós-fixas


Algoritmo com bastante abstração
Exemplo
2
Definições
Uma expressão aritmética é composta de
operandos, operadores e delimitadores.
As operações são definidas por seus operadores. A
ordem de avaliação das operações depende dos
delimitadores e da prioridade dos operadores.
As expressões aritméticas podem ser representas
por 3 tipos de notação.



Infixa
Pré-fixa
Pós-fixa
3
Avaliação de expressões (1)
A avaliação de expressões na forma pós-fixa é
bastante simplificada por diversas razões:



Não há necessidade de emprego de delimitadores;
A prioridade dos operadores deixa de ser relevante;
As expressões podem ser analisadas fazendo uma
varredura do início para o final armazenando os
operandos em uma pilha, aplicando os operadores sobre
os elementos da pilha e empilhando os resultados das
operações efetuadas.
4
Avaliação de expressões (2)
A avaliação de expressões aritméticas pode
ser feita transformando as expressões
infixas, familiares aos seres humanos, em
expressões pós-fixas e, a seguir, avaliando o
resultado das expressões pós-fixas obtidas.
Para a transformação de expressões
aritméticas infixas em pós-fixas e sua
avaliação é conveniente definir diversas
funções auxiliares.
5
Transformação de expressões aritméticas
infixas em pós-fixas
Esta transformação será mostrada da
seguinte maneira:
Inicialmente será apresentado um algoritmo
com bastante abstração
 Será apresentado um exemplo
 Finalmente serão apresentadas as declarações
de funções utilizadas em um algoritmo com
pouca abstração (para implementação)

6
Transformação de expressões
infixas em pós-fixas
Conversão da forma infixa para pós-fixa
(algoritmo com bastante abstração)
A entrada é um vetor infixVect de tokens (strings) de uma expressão
infixa
A saída é um vetor postficVect de tokens (strings) que armazena a
expressão infixa correspondente
Utilizar uma pilha stackVector de tokens para armazenar operadores
Os tokens são operandos, operadores e delimitadores
O processamento consistem em uma repetição que analisa cada token de
entrada e gerencia a pilha e a transferência para a saída
A repetição continua enquanto não ocorrer erro e não terminar a
expressão infixa
Quando todos os tokens de infixVect tiverem sido processados,
repetidamente desempilhar um token de stackVect e adicioná-lo a
postfixVect até esvaziar stackVect
8
Conversão da forma infixa para pós-fixa
(passos da repetição)
Caso o token seja:
um operando

Incluí-lo no final do vetor postfixVect
um “(“

Empilhar o token x em stackVect
um “)”



Repetidamente desempilhar um token de stackVect e adicioná-lo ao vetor postfixVect até
encontrar “(“ no final da pilha stackVect
Desempilhar “(“ de stackVect
Se stackVect esvaziar antes de encontrar um “(“, a expressão de entrada não é válida.
um operador

Se stackVect estiver vazia ou o token de entrada tiver prioridade maior do que a
operador topo de pilha


Empilhar o token de entrada.
Caso contrário


desempilhar o token de stackVect, adicioná-lo ao vetor postfixVect
Repetir a comparação do token de entrada com o novo topo de pilha
9
Conversão da forma infixa para pós-fixa
infixVect
(a+b-c)*d–(e+f)
postfixVect
stackVect
10
Conversão da forma infixa para pós-fixa
infixVect
a+b-c)*d–(e+f)
postfixVect
(
stackVect
11
Conversão da forma infixa para pós-fixa
infixVect
+b-c)*d–(e+f)
postfixVect
a
(
stackVect
12
Conversão da forma infixa para pós-fixa
infixVect
b-c)*d–(e+f)
postfixVect
a
+
(
stackVect
13
Conversão da forma infixa para pós-fixa
infixVect
-c)*d–(e+f)
postfixVect
ab
+
(
stackVect
14
Conversão da forma infixa para pós-fixa
infixVect
c)*d–(e+f)
postfixVect
ab+
-
(
stackVect
15
Conversão da forma infixa para pós-fixa
infixVect
)*d–(e+f)
postfixVect
ab+c
-
(
stackVect
16
Conversão da forma infixa para pós-fixa
infixVect
*d–(e+f)
postfixVect
ab+c-
stackVect
17
Conversão da forma infixa para pós-fixa
infixVect
d–(e+f)
postfixVect
ab+c-
*
stackVect
18
Conversão da forma infixa para pós-fixa
infixVect
–(e+f)
postfixVect
ab+c-d
*
stackVect
19
Conversão da forma infixa para pós-fixa
infixVect
(e+f)
postfixVect
ab+c–d*
stackVect
20
Conversão da forma infixa para pós-fixa
infixVect
e+f)
postfixVect
ab+c–d*
(
stackVect
21
Conversão da forma infixa para pós-fixa
infixVect
+f)
postfixVect
ab+c–d*e
(
stackVect
22
Conversão da forma infixa para pós-fixa
infixVect
f)
postfixVect
+
ab+c–d*e
(
stackVect
23
Conversão da forma infixa para pós-fixa
infixVect
)
postfixVect
+
ab+c–d*ef
(
stackVect
24
Conversão da forma infixa para pós-fixa
infixVect
postfixVect
ab+c–d*ef+
stackVect
25
Conversão da forma infixa para pós-fixa
infixVect
postfixVect
ab+c–d*ef+-
stackVect
26
Conversão da forma infixa para pós-fixa
infixVect
(a+b*c)*d–(e+f)
postfixVect
stackVect
27
Conversão da forma infixa para pós-fixa
infixVect
a+b*c)*d–(e+f)
postfixVect
(
stackVect
28
Conversão da forma infixa para pós-fixa
infixVect
+b*c)*d–(e+f)
postfixVect
a
(
stackVect
29
Conversão da forma infixa para pós-fixa
infixVect
b*c)*d–(e+f)
postfixVect
a
+
(
stackVect
30
Conversão da forma infixa para pós-fixa
infixVect
*c)*d–(e+f)
postfixVect
ab
+
(
stackVect
31
Conversão da forma infixa para pós-fixa
infixVect
c)*d–(e+f)
postfixVect
*
ab
+
(
stackVect
32
Conversão da forma infixa para pós-fixa
infixVect
)*d–(e+f)
postfixVect
*
abc
+
(
stackVect
33
Conversão da forma infixa para pós-fixa
infixVect
)*d–(e+f)
postfixVect
abc*
+
(
stackVect
34
Conversão da forma infixa para pós-fixa
infixVect
*d–(e+f)
postfixVect
abc*+
stackVect
35
Conversão da forma infixa para pós-fixa
infixVect
d–(e+f)
postfixVect
abc*+
*
stackVect
36
Conversão da forma infixa para pós-fixa
infixVect
–(e+f)
postfixVect
abc*+d
*
stackVect
37
Conversão da forma infixa para pós-fixa
infixVect
(e+f)
postfixVect
abc*+d*
stackVect
38
Conversão da forma infixa para pós-fixa
infixVect
e+f)
postfixVect
abc*+d*
(
stackVect
39
Conversão da forma infixa para pós-fixa
infixVect
+f)
postfixVect
abc*+d*e
(
stackVect
40
Conversão da forma infixa para pós-fixa
infixVect
f)
postfixVect
+
abc*+d*e
(
stackVect
41
Conversão da forma infixa para pós-fixa
infixVect
)
postfixVect
+
abc*+d*ef
(
stackVect
42
Conversão da forma infixa para pós-fixa
infixVect
postfixVect
abc*+d*ef+
stackVect
43
Conversão da forma infixa para pós-fixa
infixVect
postfixVect
abc*+d*ef+-
stackVect
44
Funções auxiliares
Transformação de expressões aritméticas infixas em
pós-fixas







isoperand
isdigit
prio
expon
oper
orcd
postfix
Avaliação de expressões aritméticas pós-fixas

eval
45
Transformação de expressões aritméticas
infixas em pós-fixas (1)
isoperand

Recebe um caractere, ou “token”, e retorna
verdadeiro (TRUE) quando o caractere não for
+, -, *, /, , (, ).
isdigit

Recebe um caractere, ou “token”, e retorna
TRUE quando o “token” for numérico.
46
Transformação de expressões aritméticas
infixas em pós-fixas (2)
prio

Recebe um “token”, que seja operador e retorna




1 caso o operador seja + ou 2 caso o operador seja * ou /
3 caso o operador seja ^
0 em caso contrário
expon

Recebe dois reais e retorna o valor do primeiro real elevado
à potencia igual ao segundo real
oper

Recebe um “token” (operador) e dois reais (operandos) e
retorna o resultado da aplicação do operador aos dois
operandos
47
Transformação de expressões aritméticas
infixas em pós-fixas (3)
prcd

Recebe dois “tokens”, representando
operadores e retorna TRUE quando o primeiro
operador tem precedência sobre o segundo
operador ao aparecer à esquerda deste último
em uma expressão infixa sem parênteses. Casos
particulares ocorrem com o tratamento de
parênteses.
48
Transformação de expressões aritméticas
infixas em pós-fixas (4)
Regras de tratamento de precedência de parênteses
REGRA COMENTÁRIO
1
Qualquer operador que segue ‘(‘ é empilhado
2
‘(‘ só não seria empilhado se o topo da pilha
contivesse ‘)‘
3
Quando um ‘)’ encontra um ‘(‘ não há
desempilhamento. Ambos são descartados. Quando
um’)’ encontra qualquer outro operador existe
desempilhamento
4
‘)‘ encontrado na pilha, o que é absurdo. Retorna
valor indefinido
GERAL Regra válida para os demais operadores
Ao entrar um ‘)’ saem todos os elementos até encontrar um ‘(‘.
Ambos os delimitadores são descartados.
49
Transformação de expressões aritméticas
infixas em pós-fixas (5)
postfix
 Recebe dois strings. O primeiro string (de entrada) representa uma
expressão aritmética sob a forma infixa. O segundo string serve para
retornar uma expressão aritmética na forma pós-fixa.
 O string de entrada é varrido do início até o final.
 Se o token do string de entrada for um operando é imediatamente
copiado para o string de saída
 Se o token de entrada for um operador, enquanto houver operadores
empilhados com precedência maior do que o operador de entrada,
estes operadores que estavam empilhados são transferidos para a
expressão de saída
 O operador de entrada é empilhado.
 Ao término da varredura os operadores são desempilhados e copiados
para a expressão de saída
 Os delimitadores não são transferidos para o string de saída.
50
Avaliação de expressões aritméticas pósfixas
eval





Recebe um string que representa uma expressão infixa
e faz uma varredura do início para o final do string
Se o token corrente for um operando deve ser
empilhado sob a forma de real
Se o token corrente for um operador devem ser
desempilhados dois operandos sobre os quais o
operador vá atuar
O resultado da aplicação do operador aos operandos é
empilhado
Ao término da varredura do string a função retorna o
topo da pilha
51
Avaliação de expressões pósfixas
Avaliação de expressões aritméticas
pós-fixas
Esta avaliação será mostrada da seguinte
maneira:
Inicialmente será apresentado um algoritmo
com bastante abstração
 Será apresentado um exemplo

53
Avaliação de expressões aritméticas pós-fixas
Ler os tokens de um vetor de tokens (strings) postfixVect
contendo uma expressão pós-fixa
Quando o token for um operando
 Empilhá-lo em stackVect
Quando o token for um operador
 Desempilhar de stackVect dois operandos
 Aplicar o operador aos dois operandos desempilhados de
stackVect obtendo um valor (novo operando)
 Empilhar em stackVect o valor obtido da aplicação do
operador aos operandos desempilhados
Ao término da varredura do string de postfixVect a função
retorna o topo da pilha
54
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Situação inicial
stackVect
55
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Empilhado o operando a
a
stackVect
56
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Empilhado o operando b
b
a
stackVect
57
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Desempilhados operandos a e b
Operador + aplica-se a a e b
stackVect
58
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Empilhado o resultado a + b
a+b
stackVect
59
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Empilhado o operando c
c
a+b
stackVect
60
Avaliação de expressões pós-fixas
postfixVect
ab+c-d*ef+-
Desempilhados operandos (a + b) e c
Operador - aplica-se a (a + b) e c
stackVect
61
Avaliação de expressões pós-fixas
postfixVect
a b + c -d * e f + -
Empilhado o resultado (a + b - c)
a+b -c
stackVect
62
Avaliação de expressões pós-fixas
postfixVect
a b + c – d* e f + -
Empilhado o operando d
d
a+b -c
stackVect
63
Avaliação de expressões pós-fixas
postfixVect
a b + c – d *e f + -
Desempilhados (a+b-c) e d
Operador * aplica-se a (a+b-c) e d
stackVect
64
Avaliação de expressões pós-fixas
postfixVect
a b + c – d *e f + -
Empilhado o operando (a+b-c) * d
(a + b - c) * d
stackVect
65
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*ef+-
Empilhado o operando e
e
(a + b - c) * d
stackVect
66
Avaliação de expressões pós-fixas
postfixVect
a b + c – d * e f+ -
f
Empilhado o operando f
e
(a + b - c) * d
stackVect
67
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*e f+-
Desempilhados operandos e e f
Operador + aplica-se a e e f
(a + b - c) * d
stackVect
68
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*e f+-
Empilhado operando e + f
e+f
(a + b - c) * d
stackVect
69
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*e f+-
Desempilhados operandos (a+b-c)*d e (e+ f)
Operador - aplica-se a (a+b-c)*d e (e+ f)
stackVect
70
Avaliação de expressões pós-fixas
postfixVect
a b + c – d * e f +-
Empilhado (a + b - c) * d – (e + f)
(a + b - c) * d – (e + f)
stackVect
71
Avaliação de expressões pós-fixas
postfixVect
ab+c–d*e f+Saída obtida
Desempilhar (a + b - c) * d – (e + f)
stackVect
72