Pilhas C v7

Prévia do material em texto

1 
ESTRUTURAS DE DADOS 
► Pilhas 
(Linguagem C) 
Prof. Dr. Marcelo Duduchi 
Aux. Docente Lucio Nunes 
Estruturas de Dados 
 Ao implementarmos programas de computador 
estamos de certa forma tentando representar o 
mundo real pela computação; 
 Os dados a serem processados no computador 
representam uma abstração de parte da realidade na 
medida em que representam características 
selecionadas das entidades do mundo real; 
2 
Estruturas de Dados 
 A forma segundo a qual os bits são agrupados, interpretados e 
manipulados pelo computador normalmente não nos interessa 
quando a nossa preocupação maior é resolver um problema 
específico; 
 Felizmente, as linguagens atuais oferecem um conjunto básico de 
tipos de dados primitivos (inteiros, reais, caractere, booleano etc.) 
que podemos usar nas soluções de problemas; 
 Da mesma forma, temos mecanismos que permitem criar 
agrupamentos complexos de dados a partir desses tipos primitivos; 
3 
Estruturas de Dados 
 Para representar o mundo computacionalmente é necessário 
modelar; 
 É neste particular que o conceito de tipos abstratos de dados passa 
a ser muito importante para a computação; 
 Um tipo abstrato de dados é formado por: 
 Um conjunto de valores; 
 Uma série de funções que podem ser aplicadas a estes valores. 
 O modelo usado para representar a solução de uma classe de 
problemas podemos chamar de estrutura de dados; 
4 
Estruturas de Dados 
 O estudo das estruturas de dados envolve dois 
objetivos básicos: 
 Teórico: Identificar e desenvolver modelos, determinando 
que classes de problemas podem resolver; 
 Prático: Criar representações concretas dos objetivos e 
desenvolver sub-rotinas capazes de atuar como 
representações. 
5 
Listas Lineares 
 Uma lista é uma coleção de elementos do mesmo tipo 
dispostos linearmente que podem ou não seguir uma 
determinada organização; 
 Exemplo: [E
1
, E
2
, E
3
, ..., E
n
], onde n ≥ 0; 
 Uma lista de pagamentos pode ser constituída por: 
prestação do carro, cartão de crédito, conta de luz, 
condomínio, televisão a cabo e prestação do crediário; 
6 
2 
Listas Lineares 
 Para a representação de alguns modelos do 
mundo real é necessário limitar o funcionamento 
das listas lineares; 
 É neste contexto que surgem as listas lineares 
restritas. As mais utilizadas são: 
Pilhas e 
 Filas. 
7 
Pilhas 
 Uma lista linear onde tanto a entrada quanto a saída 
precisa ser feita pela mesma extremidade é conhecida 
como pilha; 
 Neste caso o último elemento que entrar é o primeiro a 
sair (Last In / First Out); 
 Existem duas funções que se aplicam a todas as pilhas: 
 PUSH: insere o item no topo da pilha; 
 POP: remove o item do topo da pilha. 
8 
Pilhas (modelo conceitual) 
9 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
A 
Pilhas (modelo conceitual) 
Push 
10 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
A 
Pilhas (modelo conceitual) 
11 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
B 
A 
Pilhas (modelo conceitual) 
Push 
12 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
A 
B 
3 
Pilhas (modelo conceitual) 
13 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
C 
A 
B 
Pilhas (modelo conceitual) 
Push 
14 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
A 
B 
C 
Pilhas (modelo conceitual) 
15 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
D 
A 
B 
C 
Pilhas (modelo conceitual) 
Push 
16 
 
 
 
 
 
Novos elementos são 
armazenados no topo 
da pilha. 
A 
B 
C 
D 
Pilhas (modelo conceitual) 
17 
 
 
 
 
 
A 
B 
C 
D Sequência armazenada 
em pilha. 
Pilhas (modelo conceitual) 
Pop 
18 
 
 
 
 
 
A 
B 
C 
D 
O último elemento que 
entrou será o primeiro a 
sair (LIFO). 
4 
Pilhas (modelo conceitual) 
Pop 
19 
 
 
 
 
 
A 
B 
C 
O último elemento que 
entrou será o primeiro a 
sair (LIFO). 
Pilhas (modelo conceitual) 
Pop 
20 
 
 
 
 
 
A 
B 
O último elemento que 
entrou será o primeiro a 
sair (LIFO). 
Pilhas (modelo conceitual) 
Pop 
21 
 
 
 
 
 
A 
O último elemento que 
entrou será o primeiro a 
sair (LIFO). 
Pilhas (representação gráfica) 
22 
 
 
 
 
 
 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
23 
 
 
 
 
 
push(pilha, 'D') 
 
 
 
 
 
Topo → 
D 
Pilhas (representação gráfica) 
24 
 
 
 
 
D 
 
 
 
 
Topo → 
5 
Pilhas (representação gráfica) 
25 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
D 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
26 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
pop(pilha) 
 
 
 
 
 
Topo → 
D 
Pilhas (representação gráfica) 
27 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
28 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
29 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
 
push(pilha, 'A') 
 
 
 
 
 
Topo → 
A 
Pilhas (representação gráfica) 
30 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
6 
Pilhas (representação gráfica) 
31 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
32 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
A 
push(pilha, 'V') 
 
 
 
 
Topo → 
V 
Pilhas (representação gráfica) 
33 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
34 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
35 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
 
A 
pop(pilha) 
 
 
 
 
Topo → 
V 
Pilhas (representação gráfica) 
36 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
7 
Pilhas (representação gráfica) 
37 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
38 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo →A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
A 
push(pilha, 'B') 
 
 
 
 
Topo → 
B 
Pilhas (representação gráfica) 
39 
 
 
 
 
D 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
V 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
40 
 
 
 
B 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
41 
 
 
 
B 
A 
push(pilha, 'G') 
 
 
 
Topo → 
G 
Pilhas (representação gráfica) 
42 
 
 
G 
B 
A 
 
 
Topo → 
8 
Pilhas (representação gráfica) 
43 
 
 
G 
B 
A 
 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
Pilhas (representação gráfica) 
44 
 
 
G 
B 
A 
 
 
Topo → 
 
 
G 
B 
A 
push(pilha, 'H') 
 
 
Topo → 
H 
Pilhas (representação gráfica) 
45 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
Pilhas (representação gráfica) 
46 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
Pilhas (representação gráfica) 
47 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
pop(pilha) 
 
 
Topo → 
H 
Pilhas (representação gráfica) 
48 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
9 
Pilhas (representação gráfica) 
49 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
Pilhas (representação gráfica) 
50 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
pop(pilha) 
 
 
 
Topo → 
G 
Pilhas (representação gráfica) 
51 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
52 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
Pilhas (representação gráfica) 
53 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
 
A 
pop(pilha) 
 
 
 
 
Topo → 
B 
Pilhas (representação gráfica) 
54 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
10 
Pilhas (representação gráfica) 
55 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
Pilhas (representação gráfica) 
56 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
 
pop(pilha) 
 
 
 
 
 
Topo → 
A 
Pilhas (representação gráfica) 
57 
 
 
G 
B 
A 
 
 
Topo → 
 
H 
G 
B 
A 
 
Topo → 
 
 
G 
B 
A 
 
 
Topo → 
 
 
 
B 
A 
 
 
 
Topo → 
 
 
 
 
A 
 
 
 
 
Topo → 
 
 
 
 
 
 
 
 
 
 
Topo → 
Pilhas (implementação) 
 Consideremos para a nossa implementação um grupo de 
operações: 
 create → inicializa a pilha 
 destroy → esvazia a pilha 
 isfull → verifica se está cheia 
 isempty → verifica se está vazia 
 push → insere um elemento 
 pop → retira um elemento 
 top → mostra o elemento do topo 
58 
Pilhas (definição da estrutura) 
59 
typedef struct pilha { 
 char vet[6]; 
 int topo; 
 } TPilha; 
TPilha 
vet topo 
0 1 2 3 4 5 
Pilhas (create, destroy, isfull e isempty) 
60 
void create(TPilha *p) { 
 p->topo = -1; 
} 
void destroy(TPilha *p) { 
 p->topo = -1; 
} 
int isfull(TPilha *p) { 
 if (p->topo == 5) 
 return 1; 
 else 
 return 0; 
} 
int isempty(TPilha *p) { 
 if (p->topo == -1) 
 return 1; 
 else 
 return 0; 
} 
11 
Pilhas (isfull e isempty) 
61 
int isfull(TPilha *p) { 
 return p->topo == 5; 
} 
int isempty(TPilha *p) { 
 return p->topo == -1; 
} 
char pop(TPilha *p) 
{ 
 char aux; 
 if (isempty(p)) { 
 printf("underflow\n"); 
 abort(); 
 } 
 aux = p->vet[p->topo]; 
 p->topo--; 
 return aux; 
} 
Pilhas (push e pop) 
62 
void push(TPilha *p, char x) 
{ 
 if (isfull(p) { 
 printf("overflow\n"); 
 abort(); 
 } 
 p->topo++; 
 p->vet[p->topo] = x; 
} 
Pilhas (top) 
63 
char top(TPilha *p) { 
 if (isempty(p)) { 
 printf("underflow\n"); 
 abort(); 
 } 
 return p->vet[p->topo]; 
} 
Pilhas (exemplo de utilização) 
64 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
 
 
 
Roma 
Pilhas (exemplo de utilização) 
65 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
 
 
R 
Roma 
Pilhas (exemplo de utilização) 
66 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
 
o 
R 
Roma 
12 
Pilhas (exemplo de utilização) 
67 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
m 
o 
R 
Roma 
Pilhas (exemplo de utilização) 
68 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
Roma 
 
a 
m 
o 
R 
Pilhas (exemplo de utilização) 
69 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
a 
m 
o 
R 
Pilhas (exemplo de utilização) 
70 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
m 
o 
R 
a 
Pilhas (exemplo de utilização) 
71 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p);} 
 
 
 
o 
R 
am 
Pilhas (exemplo de utilização) 
72 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
 
 
R 
amo 
13 
Pilhas (exemplo de utilização) 
73 
void inverte(char s[]) { 
 int i, tam; 
 TPilha p; 
 create(&p); 
 tam = strlen(s); 
 for (i = 0; i < tam; i++) 
 push(&p, s[i]); 
 for (i = 0; !isempty(&p); i++) 
 s[i] = pop(&p); 
} 
 
 
 
 
 
amoR 
Pilhas (aplicações) 
 Pilha de chamada de rotinas: 
Caso seja uma chamada, colocar o endereço da 
próxima instrução na pilha, executando a rotina 
chamada; 
Caso seja um “retorne”, retirar um endereço da 
pilha, passando a executá-lo. 
74 
Pilhas (aplicações) 
75 
INSTRUÇÃO ESTADO DA PILHA 
e0 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
76 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
77 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
78 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
14 
Pilhas (aplicações) 
79 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
80 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2, e6 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
81 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0, e2 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
82 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
83 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
84 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0, e3 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
15 
Pilhas (aplicações) 
85 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0 
e3: B( ); e0 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
86 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0 
e3: B( ); e0, e4 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
87 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0 
e3: B( ); e0, e4 
e7: Retorne; e0, e4 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
88 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0 
e3: B( ); e0, e4 
e7: Retorne; e0 
e4: Retorne; e0 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (aplicações) 
89 
INSTRUÇÃO ESTADO DA PILHA 
e0 
e1: A( ); e0, e2 
e5: B( ); e0, e2, e6 
e7: Retorne; e0, e2 
e6: Retorne; e0 
e2: C( ); e0, e3 
e8: Retorne; e0 
e3: B( ); e0, e4 
e7: Retorne; e0 
e4: Retorne; e0 
e0: [volta p/ S.O.] 
Rotina P 
 e1: A( ); 
 e2: C( ); 
 e3: B( ); 
 e4: Retorne; 
 
Rotina A 
 e5: B( ); 
 e6: Retorne; 
 
Rotina B 
 e7: Retorne; 
 
Rotina C 
 e8: Retorne; 
Pilhas (infixa -> posfixa) 
90 
Infixa 
(((3 − 1) + (2 ∗ 4))/5) 
Posfixa 
3 1 − 2 4 ∗ + 5 / 
16 
Pilhas (infixa -> posfixa) 
91 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
92 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
93 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
94 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
95 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Posfixa: 3 
Pilhas (infixa -> posfixa) 
96 
 
 
− 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
17 
Pilhas (infixa -> posfixa) 
97 
 
 
− 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
98 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 
( : ignore 
0…9 : anexe à string+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
99 
 
 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
100 
 
 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
101 
 
 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
102 
 
∗ 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
18 
Pilhas (infixa -> posfixa) 
103 
 
∗ 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
104 
 
 
+ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
105 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ + 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
106 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ + 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
107 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ + 5 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
Pilhas (infixa -> posfixa) 
108 
 
 
 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
( : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
) : desempilhe e anexe à string 
19 
Pilhas (infixa -> prefixa) 
109 
Infixa 
(((3 − 1) + (2 ∗ 4))/5) 
Prefixa 
/ + − 3 1 ∗ 2 4 5 
Pilhas (infixa -> prefixa) 
110 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
111 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
112 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
113 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
114 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
20 
Pilhas (infixa -> prefixa) 
115 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
116 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
117 
 
∗ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
118 
 
∗ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
119 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
120 
 
+ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
21 
Pilhas (infixa -> prefixa) 
121 
 
+ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
122 
 
+ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
123 
− 
+ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
124 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 3 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
− 
+ 
/ 
Pilhas (infixa -> prefixa) 
125 
 
+ 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 3 − 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
126 
 
 
/ 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 3 − + 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
22 
Pilhas (infixa -> prefixa) 
127 
 
 
 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: 5 4 2 ∗ 1 3 − + / 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (infixa -> prefixa) 
128 
 
 
 
 
 
 
 
 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
Prefixa: / + − 3 1 ∗ 2 4 5 
) : ignore 
0…9 : anexe à string 
+, -, *, /: empilhe 
( : desempilhe e anexe à string 
Pilhas (posfixa -> infixa) 
129 
Posfixa 
3 1 − 2 4 ∗ + 5 / 
Infixa 
(((3 − 1) + (2 ∗ 4))/5) 
Pilhas (posfixa -> infixa) 
130 
 
 
 
 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Infixa: 
Pilhas (posfixa -> infixa) 
131 
 
 
 
3 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
132 
 
 
1 
3 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
23 
Pilhas (posfixa -> infixa) 
133 
 
 
 
3 − 1 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
134 
 
 
2 
3 − 1 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
135 
 
4 
2 
3 − 1 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha;empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
136 
 
 
2 ∗ 4 
3 − 1 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
137 
 
 
 
((3 − 1) + (2 ∗ 4)) 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
138 
 
 
5 
((3 − 1) + (2 ∗ 4)) 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
24 
Pilhas (posfixa -> infixa) 
139 
 
 
 
(((3 − 1) + (2 ∗ 4))/5) 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (posfixa -> infixa) 
140 
 
 
 
 
 
Posfixa: 3 1 − 2 4 ∗ + 5 / 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
empilhe '(' + desempilha + 
[𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 𝑏 + ')' 
Pilhas (prefixa -> infixa) 
141 
Prefixa 
/ + − 3 1 ∗ 2 4 5 
Infixa 
(((3 − 1) + (2 ∗ 4))/5) 
Pilhas (prefixa -> infixa) 
142 
 
 
 
 
Prefixa: / + − 3 1 ∗ 2 4 5 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Infixa: 
Pilhas (prefixa -> infixa) 
143 
 
 
 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
144 
 
 
4 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
25 
Pilhas (prefixa -> infixa) 
145 
 
2 
4 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
146 
 
 
(2 ∗ 4) 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
147 
 
1 
(2 ∗ 4) 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
148 
3 
1 
(2 ∗ 4) 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
149 
 
(3 − 1) 
(2 ∗ 4) 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
150 
 
 
((3 − 1) + (2 ∗ 4)) 
5 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
26 
Pilhas (prefixa -> infixa) 
151 
 
 
 
(((3 − 1) + (2 ∗ 4))/5) 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
Pilhas (prefixa -> infixa) 
152 
Prefixa: / + − 3 1 ∗ 2 4 5 
Infixa: (((3 − 1) + (2 ∗ 4))/5) 
0…9 : empilhe 
+, -, *, /: empilhe '(' + 
desempilha + [𝑜𝑝𝑒𝑟𝑎𝑑𝑜𝑟] + 
desempilha + ')' 
153 
AVALIAÇÃO DE EXPRESSÃO 
POSFIXA 
 
3 1 − 2 4 ∗ + 5 / 
Pilhas (avaliação posfixa) 
154 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
 
 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
155 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
 
3 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
156 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
1 
3 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
27 
Pilhas (avaliação posfixa) 
157 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
 
2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
158 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
2 
2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
159 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 4 
2 
2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
160 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
8 
2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
161 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
 
10 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
162 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
5 
10 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
28 
Pilhas (avaliação posfixa) 
163 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 
 
2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
Pilhas (avaliação posfixa) 
164 
posfixa: 3 1 − 2 4 ∗ + 5 / 
Resultado: 2 
0…9 : empilhe 
+, -, *, /: 𝑏 recebe desempilha; 
 empilhe( 
 desempilha [𝑜𝑝𝑒𝑟𝑎çã𝑜] 𝑏) 
 
 
 
 
165 
AVALIAÇÃO DE EXPRESSÃO 
PREFIXA 
 
/ + − 3 1 ∗ 2 4 5 
Pilhas (avaliação prefixa) 
166 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
 
 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
Pilhas (avaliação prefixa) 
167 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
 
 
5 
Pilhas (avaliação prefixa) 
168 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
 
4 
5 
29 
Pilhas (avaliação prefixa) 
169 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
2 
4 
5 
Pilhas (avaliação prefixa) 
170 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
 
8 
5 
Pilhas (avaliação prefixa) 
171 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
1 
8 
5 
Pilhas (avaliação prefixa) 
172 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
3 
1 
8 
5 
Pilhas (avaliação prefixa) 
173 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
2 
8 
5 
Pilhas (avaliação prefixa) 
174 
prefixa:/ + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
 
10 
5 
30 
Pilhas (avaliação prefixa) 
175 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha) 
 
 
 
 
2 
Pilhas (avaliação prefixa) 
176 
prefixa: / + − 3 1 ∗ 2 4 5 
Resultado: 2 
0…9 : empilhe 
+, -, *, /: empilhe(desempilha 
 [𝑜𝑝𝑒𝑟𝑎çã𝑜] desempilha)