Aplicações de Pilhas Marco Antonio Montebello Júnior [email protected] Estrutura de Dados

Aplicações de Pilhas

Marco Antonio Montebello Jú[email protected]

Estrutura de Dados

Estrutura de Dados 2

Aplicações clássicas

Determinação de escopo de expressões

Conversão de expressões

Avaliação de expressões

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 ) )



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



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.



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.



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.


Determinação de escopos em expressões Exemplos:

2 + ( ( A * C ) + ( ( D - E ) / ( B - 5 ) ) - 9 ) + 200 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 ) + 51 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



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) ] {


Algoritmo para trabalhar com os outros identificadoresvalido “V”inicializa(s) // faz a pilha s vaziaenquanto (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_sefim_enquantose (empty (s) “V” ) então valido “F”fim_sese (valido = “V” ) então imprima “Expressão válida!”senão imprima “Expressão inválida!”fim_se


Acompanhamento do Algoritmo

2 + { [ F * 4 ] + [ ( A - B ) / ( C - 2 ) ] - 3 } + 4



2 + { [ F * 4 ] + [ ( A - B ) / ( C - 2 ) ] - 3 } + 4



2 + { [ F * 4 ] + [ ( A - B ) / ( C - 2 ) ] - 3 } + 4



2 + { [ F * 4 ] + [ ( A - B ) / ( C - 2 ) ] - 3 } + 4

Conversão e Avaliação de Expressões


Convertendo e Analisando Expressões

Tipos de Notações Infixa Pré-fixa (Notação Polonesa – NP) Pós-fixa (Notação Polonesa Reversa – NPR)

Precedência de Operadores A * B + C ≠ A *( B + C )

Exemplos de Expressões A – B A – B * C A / ( B * ( C – D) + E) ((A / B) * (C – D ) + E)


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 +)


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*+


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


Exemplos:Notação Infixa para Pós-fixa

Notação Infixa Notação Pós-fixa

A - B * C A B C * -

A * (B - C) A B C - *

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

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

A + B A B+

A - B + C A B - C +

(A + B) / (C – D) A B + CD - /

A ^ B * C – D + E / F (G - H) A B ^ C * D – E F / G H - / +

((A + B) * C – (D – E)) ^ (F - G) A B + C * D E - - F G - ^

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


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) ^ - + A B C - D E – F G

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


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.


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


Passo 1: Colocar Parênteses

Original: A - B * C + D

Com os parênteses: ((A – (B * C)) + D)


Passo 2:


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_parafim

Que tal exercitar o algoritmo anterior com (A + B) * C que, na notação pós-fixa fica: A B + C *?


switch

(Opera

dor)

{

case

'{': r

eturn

1;

ca

se '['

: retu

rn 2;

ca

se '('

: retu

rn 3;

ca

se '+'

: retu

rn 4;

ca

se '-'

: retu

rn 4;

ca

se '*'

: retu

rn 5;

ca

se '/'

: retu

rn 5;

ca

se '^'

: retu

rn 6;

de

fault:

retur

n 0;

}

Algoritmo Genérico:Conversão Infixa para Pós-fixa

função prioridade(op)início caso op seja “(” : prioridade 1 “+”, “-” : prioridade 2 “*”, “/” : prioridade 3 “^” : prioridade 4 fim_casofim

Deve-se definir um algoritmo que determine automaticamente a precedência:


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;


Algoritmo Genérico:Conversão Infixa para Pós-fixa Passo 3:

Ao encontrar um parêntese de abertura, empilhe-o; Passo 4:

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.


Funcionamento:A / ( B + C ) * D


Algoritmo em Pseudocódigovetor npos[1...m]: armazena expressão posfixavetor infixa[1...m]: armazena expressão infixapos 0iní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_enquantofim


Avaliando a forma Pós-fixa

Expressão Infixa: (A – B)*(C+D)/E

Expressão Pós-fixa: 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


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.


Exemplo:


Exemplo – Continuação


Algoritmo em Pseudocódigoiní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

Documents

Aplicações de Pilhas Marco Antonio Montebello Júnior [email protected] Estrutura de Dados