Pilhas

Este é um resumo de parte do capítulo 4 (Abstract Data Types) do livro do Sedgewick. Esse capítulo usa o exemplo das pilhas (= stacks) para introduzir o conceito de tipo abstrato de dados. No presente resumo, vamos examinar apenas alguns exemplos concretos de aplicação de pilhas.

Esse material também aparece na seção 8.1, p.327, do livro do Roberts.

Pilhas e o cálculo do valor de uma expressão posfixa

Este é um resumo da seção 4.3 (Examples of Stack ADT Clients) do livro do Sedgewick.

Na notação infixa usual, os operadores são escritos entre os operandos. Na notação posfixa, os operadores são escritos depois dos operandos. Exemplo:

 

infixa	posfixa
5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 )	5 9 8 + 4 6 * * 7 + *

O programa abaixo calcula e imprime o valor de uma expressão posfixa que envolve apenas as operações de soma e multiplicação. Cada operando é um número com um ou mais dígitos decimais seguido de pelo menos um espaço em branco.

Este programa é uma versão simplificada do Program 4.2 (Postfix-expression evaluation), p.140, do livro.

#include <stdio.h> #include <string.h> // O programa imprime o valor de uma expressão posfixa // que envolve apenas somas e multiplicações. Cada operando // é um número inteiro não-negativo representado por um ou // mais dígitos decimais; ele deve ser seguido por pelo menos // um espaço em branco. // Exemplo: ao receber 5 3 11 +2 8 * * 222 + * // o programa devolve 2230. // A expressão posfixa deve ser digitada na linha de comando. main(int argc, char *argv[]) { char *a = argv[1]; int i, N = strlen(a); STACKinit(N); for (i = 0; i < N; i++) { if (a[i] == '+') STACKpush(STACKpop() + STACKpop()); if (a[i] == '*') STACKpush(STACKpop() * STACKpop()); if (a[i] >= '0' && a[i] <= '9') STACKpush(0); while (a[i] >= '0' && (a[i] <= '9') STACKpush(10 * STACKpop() + (a[i++] - '0')); } printf("%d \n", STACKpop()); free(s); }

Dica: Ao digitar a expressão na linha de comando, embrulhe-a em aspas (") para que os espaços em branco sejam interpretados como parte do argumento (e não como separadores de argumentos).

Eis a implementação das funções que manipulam a pilha (veja Programs 4.1 e 4.4, p.137-146).  A pilha será alojada em um vetor s[0..topo-1], sendo topo um variável global.

int *s;
int topo;

// Cria uma pilha vazia, com espaço para N elementos, 
// no vetor global s.
void STACKinit(int N) { 
   s = malloc(N * sizeof (Item)); 
   topo = 0;
}

// Devolve 1 se a pilha estiver vazia e 0 em caso contrário.
int STACKempty() { 
   return topo == 0; 
}

// Coloca item no topo da pilha.
void STACKpush(int item) { 
   s[topo++] = item; 
}

// Retira o item que estiver no topo da pilha.
// Devolve o valor do elemento retirado. 
int STACKpop() { 
   return s[--topo]; 
}

Eis uma versão do programa acima que implementa as funções de manipulação de pilha por macros:

#include <stdio.h>
#include <string.h>

#define pop     s[--topo]
#define push(A) s[topo++] = A

main(int argc, char *argv[])
{ 
    char *a;
    int i, N, topo;
    int *s;

    a = argv[1]; 
    N = strlen(a);
    s = malloc(N * sizeof (int)); 
    topo = 0;

    for (i = 0; i < N; i++) {
       if (a[i] == '+') 
          push(pop + pop);
       if (a[i] == '*') {
          push(pop *k pop);
       if (a[i] >= '0' && a[i] <= '9') 
          push(0);
       while (a[i] >= '0' && (a[i] <= '9') 
          push(10 * pop + (a[i++] - '0')); 
    }
    printf("%d \n", pop);
    free(s);
}       

Exercício

1. Diremos que uma expressão posfixa simples é uma cadeia de caracteres (= string) de comprimento < 99 cujos caracteres pertencem ao conjunto  '+', '*', '0', '1', . . . , '9'  (o caracter ' ' não faz parte do conjunto). Uma expressão posfixa simples representa uma expressão aritmética da maneira usual. Por exemplo,  "123*+"  representa a expressão  1 + (2*3) ,  cujo valor é  7.  Note que cada caracter numérico representa um número entre 0 e 9;  assim, a seqüência "23" representa o número 2 seguido do número 3, e não o número 23.  Escreva uma função que receba uma expressão posfixa simples e devolva o valor da correspondente expressão aritmética. Sua função não deve chamar outras funções: a eventual pilha deve ser implementada e manipulada diretamente dentro de sua função.  Procure escrever uma função curta e simples.

2. Discuta a seguinte implementação das funções STACKpush e STACKpop. A variável global N é o número de elementos na pilha e o topo da pilha está sempre na posição 0.

   void STACKpush(int item) { 
      int i;
      for (i = N; i > 0; i--) s[i] = s[i-1];
      s[0] = item; 
      N++;
   }
   int STACKpop() { 
      int i, x = s[0];
      N--;
      for (i = 0; i < N; i++) s[i] = s[i+1];
      return x; 
   }
   

Versão recursiva

A notação prefixa é análoga à posfixa, exceto que o operador vem antes (e não depois) dos operandos. Por exemplo, as expressões

            5 3 11 + 2 8 * * 222 + *
            * 5 + * + 3 11 * 2 8 222

são equivalentes: a primeira é posfixa, enquanto a segunda é prefixa. O valor de qualquer das expressões é 2230.

O programa 5.4, p.192, de Sedgewick é quase uma versão recursiva do programa 4.2 que discutimos acima. Ele calcula o valor de um expressão prefixa simples:

char *a; int i; // A função eval devolve o valor de uma expressão prefixa // que reside no vetor global a[i..]. A expressão envolve // apenas somas e multiplicações. Cada operando é um // número inteiro não-negativo representado por um ou // mais dígitos decimais; ele deve ser seguido por pelo // menos um espaço em branco. // int eval() { int x = 0; while (a[i] == ' ') i++; if (a[i] == '+') { i++; return eval() + eval(); } if (a[i] == '*') { i++; return eval() * eval(); } while ((a[i] >= '0') && (a[i] <= '9')) x = 10*x + (a[i++]-'0'); return x; }

Pilhas e a tradução da notação infixa para a posfixa

Dessa vez usaremos uma pilha de caracteres (e não de inteiros, como no programa anterior). Esse é o programa 4.3 (Infix-to-postfix conversion) do livro do Sedgewick.

#include <stdio.h> #include <string.h> // A pilha que usaremos para resolver o problema // ficará alojada em s[0..topo-1]. char *s; int topo = 0; // A expressão infixa deve estar embrulhada em parênteses. // Exemplo: Ao receber (1*(((2 + 3)*(4* 5)) + 6)) // o programa imprime 1 2 3 + 4 5 * * 6 + * // Cada operando deve ser representado por um único caracter. main(int argc, char *argv[]) { char *a; int i, N; a = argv[1]; N = strlen(a); s = malloc(N * sizeof (char)); for (i = 0; i < N; i++) { if (a[i] == ')') printf("%c ", STACKpop()); if (a[i] == '+' || a[i] == '*') STACKpush(a[i]); if (a[i] >= '0' && a[i] <= '9') printf("%c ", a[i]); } printf("\n"); free(s); }

Exercícios

3. [Sedg 4.15]  Escreva um programa que coverta uma expressão posfixa na correspondente expressão infixa.

4. [Sedg 4.16]  Escreva um programa que calcule o valor de uma expressão infixa dada. Sugestão: combine os dois programas acima em um só.

5. [Sedg 4.11]  Escreva versões mais completas dos programas 4.1 e 4.2, eliminando as várias restrições daqueles programas.

6. O fragmento de programa abaixo manipula uma pilha de caracteres. As funções de manipulação da pilha são

    int STACKempty();
   void STACKpush(char);
   char STACKpop();
   char STACKinspect();
   

   A primeira devolve 1 se pilha está vazia e 0 em caso contrário. A segunda empilha um caracter. A terceira desempilha um caracter. A quarta devolve uma cópia do item que está no topo da pilha, mas não retira o item da pilha.   Diga, em português, o que o fragmento abaixo faz.

   char x;
   if (STACKempty()) STACKpush('B');
   else 
      if (STACKinspect() != 'A')
         STACKpush('B');
      else {
         while (!STACKempty() && STACKinspect() == 'A') 
            STACKpop();
         STACKpush('B');
      }
   

   Escreva um fragmento equivalente que seja bem mais curto e mais simples.

7. Implemente as funções de manipulação de uma pilha usando uma lista encadeada para representar a pilha.

8. A formatação de um documentação html, como este que você está lendo, é definida por tags. As tags são usados em pares: um de abertura e um de fechamento. Eis um

       exemplo com <i>itálico</i> e <i>itálico <b>negrito</b></i>.
   

   Escreva um programa que verifique se as tags de um arquivo .html estão corretamente encaixados.  Basta tratar das tags  i, b, em, strong, tt, small, big, h1, h2, h3, h4, ul, ol, pre, strike, blockquote, div, table, tr, td, address, head, body, html.

9. O fragmento de programa abaixo manipula a pilha p[0..N-1] de caracteres (o topo da pilha está na posição N-1). Procure dizer, em português, o que o fragmento faz.

      if (t == 0) {
         p[0] = 'B';
         t = 1;
      }
      else if (p[t-1] != 'A') {
              p[t] = 'B';
              t++;          
           }
           else {
              while (t != 0 && p[t-1] == 'A')  t--;
              p[t] = 'B';
              t++;
           }
   

   Escreva um fragmento equivalente que seja bem mais curto e simples.