Aplicações de Pilhas
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Aplicações clássicas

Determinação de escopo de expressões

Conversão de expressões

Avaliação de expressões
Estrutura de Dados
2
Determinação de
Escopos em Expressões
Determinação de escopos em
expressões

Expressões matemáticas podem utilizar vários
parênteses agrupados:

6 – ( ( A + ( B + C ) ) ) / ( ( D – 3 * E ) + ( F * A + 10 ) )
Estrutura de Dados
4
Determinação de escopos em
expressões


Os parênteses devem ser corretamente
agrupados:
Expressões consideradas inválidas:



(D–E))
D+(E
Essas expressões também são inválidas:


)A/D(+E
( D + E) ) – (A + 2
Estrutura de Dados
5
Determinação de escopos em
expressões

Quando existirem expressões com parênteses
podemos verificar 2 (duas) condições:

Número de parênteses de abertura igual ao número
de parênteses de fechamento;

Um parêntese de fechamento é precedido pelo seu
respectivo parêntese de abertura.
Estrutura de Dados
6
Determinação de escopos em
expressões

Profundidade do agrupamento


Total de parênteses de abertura encontrados cujos
respectivos parênteses de fechamento ainda não
foram encontrados.
Diferença de parênteses

Total de parênteses de abertura subtraído do número
de parênteses de fechamento encontrados ao se
percorrer a expressão matemática da extremidade
esquerda até o ponto em análise.
Estrutura de Dados
7
Determinação de escopos em
expressões

Observações:

No final da expressão a diferença de parênteses
deve ser zero.

A diferença de parênteses em qualquer ponto da
expressão é sempre positiva.
Estrutura de Dados
8
Determinação de escopos em
expressões

Exemplos:
2 + ( ( A * C ) + ( ( D - E ) / ( B - 5 ) ) - 9 ) + 20
0 0 1 2 2 2 2 1 1 2 3 3 3 3 2 2 3 3 3 3 2 1 1 1 0 0 0
( ( F * D ) + 5
1 2 2 2 2 1 1 1
F - D )
0 0 0 -1
) D / E ) + ) E
-1 -1 -1 -1 -2 -2 -3 -3
( B / A ) ) ) - A + 2 * D ( (
1 1 1 1 0 -1 -2 -2 -2 -2 -2 -2 -2 -1 0
Estrutura de Dados
9
Determinação de escopos em
expressões

Obedecer as 2 (duas) condições é suficiente
para indicar se uma expressão é válida???


Número de parênteses de abertura igual ao número de parênteses de fechamento
Um parêntese de fechamento é precedido pelo seu respectivo parêntese de abertura

E se além de parênteses, existirem colchetes e
chaves???

Expressões inválidas:


[D–B)
{ [ A / 2} ] ou { F – 8) ] {
Estrutura de Dados
10
Algoritmo para trabalhar com os
outros identificadores
valido  “V”
inicializa(s) // faz a pilha s vazia
enquanto (não atingirmos o final da string) faça
leia o próximo caractere da string
se (caractere = “(” ou caractere = “[” ou caractere =“{” ) então
push(s, caractere)
fim_se
se (caractere = “)” ou caractere = “]” ou caractere =“}”) então
se (empty(s) = “V”) então
valido  “F”
senão
c = pop(s)
se (c não é o respectivo iniciador do caractere) então
valido  “F”
fim_se
fim_se
fim_se
fim_enquanto
se (empty (s)  “V” ) então
valido  “F”
fim_se
se (valido = “V” ) então
imprima “Expressão válida!”
senão
imprima “Expressão inválida!”
fim_se
Estrutura de Dados
11
Acompanhamento do Algoritmo

2+{[F*4]+[(A-B)/(C-2)]-3}+4
Estrutura de Dados
12
Acompanhamento do Algoritmo

2+{[F*4]+[(A-B)/(C-2)]-3}+4
Estrutura de Dados
13
Acompanhamento do Algoritmo

2+{[F*4]+[(A-B)/(C-2)]-3}+4
Estrutura de Dados
14
Acompanhamento do Algoritmo

2+{[F*4]+[(A-B)/(C-2)]-3}+4
Estrutura de Dados
15
Conversão e Avaliação
de Expressões
Convertendo e Analisando
Expressões

Tipos de Notações




Precedência de Operadores


Infixa
Pré-fixa (Notação Polonesa – NP)
Pós-fixa (Notação Polonesa Reversa – NPR)
A*B+C
≠
A *( B + C )
Exemplos de Expressões


A–B
A / ( B * ( C – D) + E)
A–B*C
((A / B) * (C – D ) + E)
Estrutura de Dados
17
Representação das Expressões
Representação Descrição
Exemplo
Infixa
Operador está entre os operandos
(A + B)
Pré-fixa
Operador precede os operandos
(+ AB)
Pós-fixa
Operador segue os operandos
(AB +)
Estrutura de Dados
18
Conversão: Regras Básicas
a) Suponha a expressão : A+B*C
b) Coloque parênteses para reforçar a
precedência: A+(B*C)
c) Converta a parte da multiplicação, obtendo:
A+(BC*)
d) Suponha que D seja igual a BC*: A+D
e) Resultando em : AD+
f) Realizando a devida substituição, ficamos com
a forma final pós-fixa igual à : ABC*+
Estrutura de Dados
19
Conversão: Notas

As regras são válidas para converter a notação
infixa para pós-fixa e também para a conversão
da notação infixa para pré-fixa

Muda-se apenas o posicionamento dos
operadores
Estrutura de Dados
20
Exemplos:
Notação Infixa para Pós-fixa
Notação Infixa
Notação Pós-fixa
A-B*C
ABC*-
A * (B - C)
ABC-*
(A - B) / (C + D)
AB-CD+/
(A - B) / (C + D) * E
AB-CD+/E*
A+B
A B+
A-B+C
AB-C+
(A + B) / (C – D)
A B + CD - /
A ^ B * C – D + E / F (G - H)
AB^C*D–EF/GH-/+
((A + B) * C – (D – E)) ^ (F - G)
AB+C*DE--FG-^
A + B / (C * D ^ E)
ABCDE^*/+
Estrutura de Dados
21
Exemplos:
Notação Infixa para Pré-fixa
Notação Infixa
Notação Pré-fixa
A*B
* AB
A-B+C
+ - ABC
(A - B) / ( C – D)
/ - AB - CD
A ^ B * C – D + E / F / (G - H)
+ - * ^ABCD //EF - GH
((A + B) * C – (D – E )) ^ (F - G)
^-+ABC-DE–FG
A + B / (C * D ^ E)
+A/B*C^DE
Estrutura de Dados
22
Algoritmo Utilizando Pilhas
Converter Infixa para Pós-fixa


1o. Passo: Colocar manualmente parênteses na
expressão
2o. Passo: Percorrer a expressão já com os
parênteses, da esquerda para a direita e, para cada
símbolo (caractere) encontrado ao longo da expressão,
tomar a seguinte decisão:




Se for parêntese de abertura, ignorá-lo;
Se for operando, copiá-lo para a expressão pós-fixa (saída
desejada);
Se for operador, colocá-lo na pilha;
Se for parêntese de fechamento, desempilhar o operador
presente no topo da pilha.
Estrutura de Dados
23
Algoritmo Utilizando Pilhas
Converter Infixa para Pós-fixa

Se no final a pilha não ficar vazia, é um sinal que
algo de errado ocorreu ao longo do processo de
conversão da notação infixa para pós-fixa

Vamos testar o funcionamento dos dois passos
anteriores, acompanhando a conversão da
seguinte expressão:
 A-B*C+D
Estrutura de Dados
24
Passo 1: Colocar Parênteses

Original:


A-B*C+D
Com os parênteses:

((A – (B * C)) + D)
Estrutura de Dados
25
Passo 2:
Estrutura de Dados
26
Algoritmo em Pseudocódigo
início
inicializa (s) //faz a pilha ficar vazia
para i  1 até n faça //n representa tam. da notação infixa
caso infixa[i] seja //infixa[i] string com notação infixa
“A” . . . “Z”: pos  pos + 1
npos[pos]  infixa[i]//npos pósfixa
“+”,”-“,”*”,”/”: push (s, infixa[i])
“)”:
pos  pos + 1
npos[pos]  pop[s]
fim_caso
fim_para
fim

Que tal exercitar o algoritmo anterior com (A + B) * C
que, na notação pós-fixa fica: A B + C *?
Estrutura de Dados
27
Algoritmo Genérico:
Conversão Infixa para Pós-fixa

Deve-se definir um algoritmo que determine
automaticamente a precedência:
função prioridade(op)
início
caso op seja
“(”
: prioridade
“+”, “-” : prioridade
“*”, “/” : prioridade
“^”
: prioridade
fim_caso
fim
Estrutura de Dados




1
2
3
4
28
Algoritmo Genérico:
Conversão Infixa para Pós-fixa

Passo 1:



Inicie com uma pilha vazia;
Realize uma varredura na expressão infixa, copiando
todos os operandos encontrados diretamente para a
expressão de saída.
Passo 2:

Ao encontrar um operador:


Enquanto a pilha não estiver vazia e houver no seu topo
um operador com prioridade maior ou igual ao
encontrado, desempilhe o operador e copie-o na saída;
Empilhe o operador encontrado;
Estrutura de Dados
29
Algoritmo Genérico:
Conversão Infixa para Pós-fixa

Passo 3:


Passo 4:


Ao encontrar um parêntese de abertura, empilhe-o;
Ao encontrar um parêntese de fechamento, remova
um símbolo da pilha e copie-o na saída. Repita esse
passo até que seja desempilhado o parêntese de
abertura correspondente
Passo 5:

Ao final da varredura, esvazie a pilha, movendo os
símbolos desempilhados para a saída. Pronto,
conseguimos obter como saída a notação pósfixa
para qualquer notação infixa entrada.
Estrutura de Dados
30
Funcionamento:
A/(B+C)*D
Estrutura de Dados
31
Algoritmo em Pseudocódigo
vetor npos[1...m]: armazena expressão posfixa
vetor infixa[1...m]: armazena expressão infixa
pos  0
início
inicializa(s)
para i  1 até n faça //onde n é o comprimento da notação infixa
caso infixa[i] seja
“A” . . .”Z”: pos  pos + 1
npos[pos]  infixa[i]
“+”, “-”, “*”,
“/”, “^”:pr  prioridade(infixa[i])
enquanto ((não pilhaVazia(s)) e (prioridade(elemtopo(s)) >= pr)) faça
pos  pos + 1
npos[pos]  pop(s)
fim_enquanto
push(s, infixa[i])
“(”: push(s, infixa[i])
“)”: x  pop(s)
enquanto x  “(” faça
pos  pos + 1
npos[pos]  x
x  pop(s)
fim_enquanto
fim_caso
fim_para
enquanto(não pilhaVazia(s)) faça
pos  pos + 1
npos[pos]  pop(s)
fim_enquanto
fim
32
Estrutura de Dados
Avaliando a forma Pós-fixa

Expressão Infixa:


Expressão Pós-fixa:



(A – B)*(C+D)/E
AB-CD+*E/
Uma vantagem da expressão pós-fixa é não necessitar
de parênteses para entendermos a precedência das
operações
Basta realizar as operações da esquerda para a direita
A
B
C
D
E
6
2
5
3
8
Estrutura de Dados
33
Algoritmo para Avaliar uma
Expressão Pós-fixa

Passo 1:


Iniciar uma pilha vazia.
Passo 2:

Varrer a expressão e, para cada símbolo encontrado
na expressão, fazemos:



Se for operando, então empilhar seu valor;
Se for operador, então desempilhar os dois últimos valores.
Em seguida efetuar a operação com eles. O resultado é
empilhado novamente na pilha.
Passo 3:

No final do processo, o resultado da avaliação estará
no topo da pilha.
Estrutura de Dados
34
Exemplo:
Estrutura de Dados
35
Exemplo – Continuação
Estrutura de Dados
36
Algoritmo em Pseudocódigo
início
inicializa(s)
para i  1 até n faça //n é o comprimento da notação Infixa
se infixa[i] = (é um operando de “A” até “Z”) então
push(s, val_infixa[i]) //valores da notação infixa
senão
se infixa[i] = (é um dos operadores +,-,*,/,^) então
y  pop(s)
X  pop(s)
caso infixa[i] seja
“+”: push(s, X+Y)
“-”: push(s, X-Y)
“*”: push(s, X*Y)
“/”: push(s, X/Y)
“^”: push(s, X^Y)
fim_caso
fim_se
fim_se
fim_para
resultado  pop(s)
fim
Estrutura de Dados
37