Estruturas de Dados - A Pilha (Parte 2)

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
A Pilha - Continuação
(stack)
Aplicações mais complexas de 
pilhas
● As pilhas desempenham importante papel na 
avaliação de fórmulas. Observe as seguintes 
expressões:
– a + b
– a + b + c
– a + b * c
– (a + b) * c
● Embora seja expressões corriqueiras, existem 
várias convenções na avaliação delas.
Aplicações mais 
complexas
● A avaliação é da esquerda para a direita
● Os operadores * e / têm precedência com 
relação à + e -
● O uso de parênteses pode alterar a ordem de 
execução das operações
● Fica claro que a apresentação convencional, 
conhecida como representação in-fixa, não é a 
melhor para efeito de cálculo da expressão.
Aplicações mais 
complexas
● Alternativas para representar A + B:
– + A B ( pré-fixa )
– A B + ( pós-fixa )
● A segunda delas é também chamada Notação 
Polonesa, e é de particular interesse no 
processamento de linguagens.
Aplicações mais 
complexas
● Vamos examinar os passos para converter-se 
de notação infixa para pós-fixa
● Por exemplo: A + B * C =>
 A + (B * C) =>
 A + (B C *) =>
 A (B C *) + =>
 A B C * +
Aplicações mais 
complexas
● Na forma Polonesa não há necessidade de 
parênteses porque o operador a ser executado 
sempre aparece imediatamente após os seus 
operandos.
● Para resolver ``2 3 5 * +`` vamos lendo os 
operandos e guardando (em uma pilha), e 
quando aparece um operador, nós realizamos 
a operação, entre os dois operandos que 
apareceram imediatamente antes
Aplicações mais 
complexas
● Entrada: 2 3 5 * +
 ^
Pilha:
 Transfere 2 pra pilha
 2 
Aplicações mais 
complexas
● Entrada: 2 3 5 * +
 ^
Pilha:
 Transfere 3 pra pilha
 3
 2 
Aplicações mais 
complexas
● Entrada: 2 3 5 * +
 ^
Pilha:
 Transfere 5 pra pilha
 5
 3
 2 
Aplicações mais 
complexas
● Entrada: 2 3 5 * +
 ^
Pilha:
 Opera o topo -1 da 
 pilha com o topo e 
 guarda em topo -1
 15 (3*5)
 2 
Aplicações mais 
complexas
● Entrada: 2 3 5 * +
 ^
Pilha:
 Opera o topo -1 da 
 pilha com o topo e 
 guarda em topo -1
 (2+15)
 17 Pronto, o resultado 
 está na base da pilha
Aplicações mais 
complexas
● Portanto, se já temos a expressão na forma 
pós-fixa, é bastante fácil calcular o seu 
resultado.
● Assumindo que você já tenha os 
procedimentos para manipular a pilha, tais 
como os que já vimos aqui, o seguinte 
programa resolve uma expressão pós-fixa:
Aplicações mais 
complexas
● main (){
 char exp[EXPSZ];
 int i, op1,op2,result;
 char c;
 stack p;
 initstack (&p); /*inicializa o stack*/
 printf("Entre a expressão em polonesa
 com dígitos e operadores\n");
 scanf("%s",exp); /* Le a expressão */
Aplicações mais 
complexas
● Observações:
– int initstack(s) /* Inicia um stack vazio */
 stack *s; {
 s->top=-1;
}
– A expressão já estará na forma polonesa e 
deverá ter somente operandos de 1 dígitos e 
operadores +, -, * ou /, sem brancos 
separando, tal como, por exemplo:
 235*+
Aplicações mais 
complexas
● for(i=0;(i<strlen(exp));i++) { /* processa caractere a caractere */ 
 c=exp[i];
 if(isdigit(c)) push(&p,c-48); /* é um operando-> põe na pilha */
 else { /* é um operador */
 op2=pop(&p); /* tira o topo */
 op1=pop(&p); /* tira o topo -1 */
 switch (c) { /* opera... */
 case '+':result=op1+op2; break;
 case '-':result=op1-op2; break;
 case '*':result=op1*op2; break;
 case '/':result=op1/op2; break;
 }
 push(&p,result); /* colocar o resultado na pilha */
 }
 }
 printf("Resultado=%d\n",stacktop(&p));
 return;
Aplicações mais 
complexas
● O algoritmo funciona bem para 
expressões já na forma polonesa.
● Vamos ver agora um algoritmo para 
transformar uma forma in-fixa em pós-
fixa.
Aplicações mais 
complexas
● Vamos observar as expressões 
 
 A + B * C e ( A+B ) * C
e suas respectivas forma polonesas:
 ABC*+ e AB+C*
Aplicações mais 
complexas
● ABC*+ e AB+C*
● A primeira observação é que a ordem de 
aparição dos operandos é a mesma
● Na primeira, o símbolo A, ao ser lido, pode 
ser transferido para a saida. Já o + não 
pode, pois deve esperar a aparição do 
segundo operando, o B. Daí, ele precisa ser 
armazenado em algum lugar, para voltar 
depois...
Aplicações mais 
complexas
● O lugar indicado é uma pilha de 
operadores:
 +
● O símbolo B, ao aparecer, pode também ir 
direto para a saída, que fica assim:
 A B
Aplicações mais 
complexas
● O normal seria que o símbolo +, na pilha, 
viesse para a saída. Porém a entrada ainda 
não terminou, e é necessário ver o que vem 
a seguir, pois o símbolo + é de baixa 
precedência.
● O símbolo seguinte é o * , que vai para a 
pilha 
● O seguinte é o C, que vai
para a saída 
 *
 A B C +
Aplicações mais 
complexas
● A seguir, como a entrada acabou, os 
símbolos que ficaram na pilha devem 
ser transferidos para a saída, do topo 
para a base.
 
 
 A B C * +
Aplicações mais 
complexas
● No caso da expressão ( A + B ) * C
os parênteses mudam a prece-
dência
 +
 (
● O simbolo B, ao aparecer, pode também ir 
direto para a saída, que fica assim:
 A B
● Mas o ´´)´´ força a descida do +...
 A B + e a pilha fica vazia
Aplicações mais 
complexas
● O * aparece e vai para a pilha
e o C vai para a saída
 
 A B + C 
 *
● Como a entrada terminou, o que resta na 
pilha deverá ser transferido para a saída
 A B + C *
Aplicações mais 
complexas
● Observe o bloco principal de um programa que faz as 
duas etapas, a tradução da expressão infixa para a forma 
polonesa e a interpretação da última forma:
● Main( ) {
 char inf[EXPSZ]; /* para ler a expressão infixa */
 char pol[EXPSZ]; /* para obter a expressão pósfixa */
 while(1) {
 printf("Entre a expressão infixa com digitos e operadores\n");
 scanf("%s",inf); /* Le a expressão infixa */
 traduz(&inf,&pol); /* para traduzir a expressão */
 printf("forma polonesa:%s\n",pol); /* imprime a expr polonesa */
 calcula(&pol);/* calcula e imprime o resultado */
 }
 return;
}
Aplicações mais 
complexas
● traduz (sin,spos) /* traduz in-fixa c/ parents em pós-fixa */
 char sin[ ], spos[ ]; {
 stack ops; /* stack para operadores */
 char c; int i, j=0;
 initstack(&ops); /* inicia o stack ops vazio */
 for(i=0;(i<strlen(sin));i++) { /* pega caractere a caractere */ 
 c=sin[i];
 if(isdigit(c)) /* é um operando-> põe na saida */
 {spos[j++]=c; spos[j]='\0';} /* ver obs 1 adiante */
 else { /* é operador: ver obs 2 */
 while ((!empty(&ops)) && preced(stacktop(&ops),c)){
spos[j++]=pop(&ops); spos[j]='\0';
 }
 if ((empty(&ops))||(c!=')')) push(&ops,c); /*poe operador na pilha*/
 else pop(&ops); /* é (... ver obs 3 */
 }
 }
 while(!empty(&ops)) {spos[j++]=pop(&ops); spos[j]='\0';} /* obs 4 */
}
Aplicações mais 
complexas
● Obs 1 
 spos[j++]=c; spos[j]='\0' faz com que o caracter em c seja 
anexado à string de saída com um nulo ao final
● Obs 2
 se o caracter c não é dígito, então é operador – neste caso a pilha
 de operadores deverá ser examinada para decidir-se se o símbolo
 deve ser inserido na pilha, colocado na string de saída, ou mesmo 
 símbolos existentes na pilha devem vir para a saída
● Obs 3
 este caso só ocorre quando o símbolo da pilha é um ( , que deve
 ser descartado, pois não vai para a saída (porque?)
● Obs 4
 quando acaba a entrada, se houverem símbolos na pilha de 
 operadores, esses símbolos devem ser colocados na saída
Aplicações mais 
complexas
● Vamos examinar agora a implementação de 
precede:
● int preced(op1, op2) 
 char op1, op2; {
 if ((op2==')')&&(op1!='(')) return TRUE;
 if (op1=='(') return FALSE;
 if ((op2=='(')&&(op1!=')')) return FALSE;
 if (((op1=='*')||(op1=='/'))&&((op2=='+')||(op2=='-'))) return TRUE;
 if ((op1=='$')&&(op2!='$')) return TRUE;
 return FALSE; 
}
Aplicações mais complexas
● Quando um ´´(´´ é lido ele deve ser empilhado. Isso será 
garantido se preced (op, '(' ) for FALSE para op != ')' 
● Além disso, preced ( '(', op ) deve ser FALSE para qualquer 
operador op
● Fazendo-se preced ( op, ')' ) == TRUE garante-se que 
todos os elementos da pilha serão retirados até que um 
parenteses esquerdo seja encontrado. Então, preced ( ´(´ , 
´)´ ) também deve ser FALSE
Estude o algoritmo e suas condições cuidadosamente e 
faça os seus testes, para se convencer que funciona...
Implementação alternativa para 
pilha em C
● C é uma linguagem flexível que permite estruturas 
diversas para dados
● É possível usar-se as operações com endereços para 
implementar-se uma pilha. Considere as declarações:
#define TAM 10
int pilha[TAM] , *topo;
● A variável topo é um ponteiro, que pode ser usado para 
apontar para o topo da pilha. Para inicializar a pilha faça:
 topo = pilha-1; /* topo estará apontando para 
 abaixo da pilha vazia */
Implementação alternativa para 
pilha em C
● O procedimento push pode ser implementado assim:
push(int i)
{
 if(topo == (pilha+TAM-1)) {
 printf("Stack Overflow.\n");
 exit(1);
 }
 *(++topo) = i;
}
Implementação alternativa para 
pilha em C
● O procedimento pop pode ser implementado assim:
 
int pop()
{ if(topo == pilha-1) {
 printf("StackUnderflow.\n");
 exit(1);
 } else
 return (*topo--);
}
Implementação alternativa para 
pilha em C
● Um procedimento main() simples para demonstrar:
int main(void)
{
 int v;
 topo = pilha-1; /* topo aponta para abaixo da pilha */
 do {
 printf("Entre o valor (0 para desempilhar, -1 para parar): ");
 scanf("%d", &v);
 if(v > 0) push(v);
 else printf("valor no topo era %d\n", pop());
 } while(v != -1);
 return 0;
}
Implementação alternativa para 
pilha em C
● Está disponível para observação no Moodle um programa 
simples, chamado “pilhaaddr.c“, com procedimentos 
semelhantes ao mostrados anteriormente. Tal programa é 
pobre em termos de solução, já que os procedimentos assume 
sempre as mesmas estruturas de dados, e caso você tenha 
mais de uma pilha trabalhando simultaneamente, você terá 
que escrever outros procedimentos para a nova pilha.
Também está disponivel um programa mais complexo, que usa 
duas pilhas e procedimentos padrão, para o processamento de 
expressões aritméticas, fazendo a conversão para notação 
polonesa e posteriormente executando a expressão. O 
programa define procedimentos genéricos, porém também 
usando a abordagem de manipulação da pilha pelos endereços 
contíguos de um vetor. Seu nome é “calcaddr1.c“. Observe-o.
Implementação alternativa para 
pilha em C
● Esse novo programa utiliza uma estrutura para a pilha assim:
typedef struct { 
 int *top;
 int elem [STKSZ];
} stack;
● A inicialização do stack e o teste de vazio são assim:
void initstack (stack *s) { 
 s->top=s->elem-1;
}
int empty(stack *s) {
 return (s->top==s->elem-1);
}
Implementação alternativa para 
pilha em C
● O push e o pop são assim:
void push (stack *s, int x){
 if (s->top+1==s->elem+STKSZ) {
 printf("%s", "Stack overflow");
 exit(1);
 } else
 *(++s->top)= x;
 return;
}
int pop (stack *s){ 
 if (empty(s)) {
 printf("%s", "Stack underflow");
 exit(1);
 }
 else
 return (*s->top--);
}
Implementação alternativa para 
pilha em C
● Observe, portanto, o programa completo 
para avaliar essa nova abordagem para 
implementação de pilha.
Uso do GCC em Windows
● Neste curso sempre darei preferência ao uso de software 
livre de código aberto, focado em distribuições Linux
● Entretanto, existem alternativas de uso em outros 
sistemas operacionais. Para o Windows você pode, por 
exemplo, baixar o gcc junto com o CodeBlocks:
 http://superdowloads.uol.com.br/redir.cfm?softid=39561
● Ou com o Dev-C++:
 http://baixaki.ig.com.br/downloads/Dev-C-.htm
Uso do GCC em Windows
● O gcc compila programas padrão C ansi ou C++
● Existem algumas diferenças entre os dois padrões
● No Linux, quando você chama o gcc serão aceitos 
programas em C ou C++, com algumas restrições e 
warnings. Os programas em C, tal como fizemos, não 
serão compilados no C++, pois apresentarão alguns erros 
de sintaxe.
● Nas versões para Windows, geralmente o default é o C++
● Apresento a seguir uma versão do programa de cálculo 
que será aceito no gcc e no c++
Exercício
● Criar um programa que se valha de pilha para executar 
expressões na notação pré-fixa. Nas expressões dessa forma, 
os símbolos de operação vêm antes dos operadores. Por 
exemplo:
Infixa Pre-fixa
 1 1
 1 + 2 + 1 2
 1 + 2 * 3 + 1 * 2 3 
 (1 + 2 ) * 3 * + 1 2 3
Será possível a entrega até as 23 horas de domingo, dia 7/7. 
Podem fazer em duplas.