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 do livro do Roberts.
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: |
| 5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) |
| posfixa: |
| 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 Programa 4.2 (Postfix-expression evaluation) 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.
void 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 Programas 4.1 e 4.4). 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 // inteiros, no vetor global s. void STACKinit (int N) { s = malloc(N * sizeof (int)); 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]; }
Segue uma versão do programa acima que implementa as funções de manipulação de pilha por meio de macros:
#include <stdio.h>
#include <string.h>
#define pop s[--topo]
#define push(A) s[topo++] = A
void 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);
}
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;
}
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 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 um ou
// mais espaços 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;
}
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. void 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); }
int STACKempty(); void STACKpush(char); char STACKpop(); char STACKinspect();A primeira devolve 1 se a 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.
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.
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.
<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, blockquote, div, table, tr, td, head, body, html.