Pilhas e calculadoras RPN

Esta página foi extraída (com várias modificações) da seção 3 (Using stacks in an application) do capítulo 8 (Abstract Data Types) do livro de Eric Roberts.  Ela usa o exemplo de uma calculadora RPN (reverse Polish notation) para introduzir o conceito de pilha.

Imagine uma estrutura sujeita a duas operações: inserção (= push) de novos elementos e remoção (= pop) de elementos antigos.  Se o elemento removido é sempre aquele que foi inserido mais recentemente, dizemos que a estrutura é uma pilha (= stack). 

Calculadora

Expressão aritmética em notação usual (infixa):

                  (5 + 3) * 2 / (4 - 6)

                  5 3 + 2 * 4 6 - /

(Note que a ordem dos operandos é exatamente a mesma nas duas expressões.)

// Este programa simula uma calculadora RPN. O usuário deve // digitar uma expressão em notação RPN. À medida que a // expressão é digitada, o programa exibe o valor da // subexpressão corrente (como se fosse o mostrador de uma // calculadora). Cada linha digitada deve conter um número, // um operador (+, -, *, /), ou um dos seguintes comandos: // Q (quit): para sair do programa, // C (clear): para limpar a calculadora, // S (stack): para exibir o contéudo da pilha. // Restrição 1: cada linha deve ter no máximo 100 caracteres. // Restrição 2: a pilha é limitada a 100 elementos (portanto, // não posso garantir o funcionamento se a expressão tiver // mais que 100 operandos). //////////////////////////////////////// // Seção 1: Bibliotecas e tipos de dados //////////////////////////////////////// #include <stdio.h> #include <stdlib.h> // preciso de atof #include <ctype.h> // preciso de isdigit, toupper etc. typedef char* string; typedef enum {FALSE, TRUE} bool; ///////////////////////////////////////////////////////////// // Seção 2: Pilha (= stack) // O programa armazena os resultados intermediários em uma // pilha de números do tipo double. Essa estrutura está // sujeita a duas operações apenas: // a operação empilha (= push) acrescenta um novo elemento // ao topo da pilha; // a operação desempilha (= pop) retira um elemento do topo // da pilha. ///////////////////////////////////////////////////////////// // A pilha residirá no vetor stk[0..stkcount-1], sendo // stkcount - 1 o índice do tipo da pilha. As variáveis // stk[] e stkcount serão globais. #define MaxStackSize 100 double stk[MaxStackSize]; int stkcount; // Operação empilha: coloca element na pilha // stk[0..stkcount-1]. void Push( double element) { if (stkcount == MaxStackSize) printf( "Stack size exceeded.\n"); exit( EXIT_FAILURE); } stk[stkcount++] = element; } // Operação desempilha: retira o elemento que está // no topo da pilha. double Pop( void) { if (stkcount == 0) { printf( "Pop of an empty stack.\n"); exit( EXIT_FAILURE); } return stk[--stkcount]; } ////////////////////////////////////////////////////////// // Seção 3: Código do programa de simulação da calculadora ////////////////////////////////////////////////////////// void ApplyOperator( char op); void DisplayStack( void); string getLine( void); int main( void) { string line; char ch; printf( "RPN Calculator Simulation\n"); stkcount = 0; while (TRUE) { printf( "> "); line = getLine(); ch = toupper( line[0]); switch (ch) { case 'Q': return 0; case 'C': stkcount = 0; break; case 'S': DisplayStack(); break; default : if (isdigit( ch)) Push( atof( line)); else ApplyOperator( ch); break; } } } // Esta função aplica o operador op aos dois operandos que // estão no topo da pilha stk[]. A função supõe que o // usuário não vai tentar divisão por zero. void ApplyOperator( char op) { double lhs, rhs, result; rhs = Pop(); // operando direito lhs = Pop(); // operando esquerdo switch (op) { case '+': result = lhs + rhs; break; case '-': result = lhs - rhs; break; case '*': result = lhs * rhs; break; case '/': result = lhs / rhs; break; default : printf( "Illegal operator\n"); exit( EXIT_FAILURE); } printf( "%g\n", result); Push( result); } // Imprime o conteúdo da pilha stk[0..stkcount-1]. void DisplayStack( void) { int i; printf( "Stack: "); if (stkcount == 0) printf( "empty\n"); else { for (i = 0; i < stkcount; i++) { if (i > 0) printf( ", "); printf( "%g", stk[i]); } printf( "\n"); } } // Lê uma linha do teclado e devolve a linha na forma de // uma string. A linha deve ter no máximo 100 caracteres. // Esta função foi inspirada na GetLine da biblioteca // simpio de Eric Roberts, mas é bem mais simples que // aquela. string getLine( void) { string line; int n, ch; n = 0; line = malloc( 100+1); if (line == NULL) exit( EXIT_FAILURE); while ((ch = getc( stdin)) != '\n') { if (n >= 100) { free( line); exit( EXIT_FAILURE); } line[n++] = ch; } line[n] = '\0'; return line; }

Observe como o código que trata da pilha foi todo reunido em uma só seção. Isso contribui para uma boa organização do programa.  (Mas eu devo admitir que o programa não está muito "limpo", pois a função DisplayStack manipula a pilha diretamente e não através das funções Pop ou Push.)

[Veja versão colorida do programa]

Exercícios

1. Que acontece se o usuário digitar apenas um ENTER, sem mais nada, ao receber um "prompt" do programa?

2. Implemente a operação de expoente inteiro (ou seja, x^y, sendo y inteiro) na calculadora RPN.  Faça uma implementação eficiente (dica: você conhece busca binária?)

3. Escreva uma função que receba uma string que representa uma expressão aritmética em notação RPN e devolva o valor da expressão.  Para simplificar, suponha que cada operando da expressão RPN tem apenas um dígito (por exemplo, "23" não representa o número vinte e três mas sim o número dois seguido do número três).  Sua função não deve chamar quaisquer outras funções. 

4. Escreva uma função que receba uma string que representa um expressão aritmética em notação RPN e devolva o valor da expressão. Suponha que os operandos e operadores são separados por espaços em branco. Suponha que cada operando pode ter um número arbitrário de caracteres. Por exemplo,

                  55.5 33.3 + 22 * 44 66.66 - /
   

   Sugestão: veja o token scanner na próxima página.

5. Escreva uma função que receba uma expressão aritmética em notação usual (infixa) essa expressão em uma expressão RPN equivalente. Suponha que as duas expressões são cadeias de caracteres (strings).

A caminho de um ADT

Vale a pena isolar e estudar em separado a parte do programa (seção 2 do código) que lida com a pilha.  Isso é um primeiro passo na direção de tratar a pilha como um tipo abstrato de dados (= ADT = abstract data type).

Vamos representar a pilha por um struct com dois campos:  o vetor que contém os elementos da pilha e o índice do topo da pilha, ou seja, o índice da primeira posição vaga da pilha:

struct {
   double elements[100];
   int    count;
} stack;

[Veja minhas anotações sobre Registros de Structs.]  Melhor ainda: vamos tratar a pilha como um novo tipo-de-dados, que chamaremos  stackT  (o "T" final só está aí para lembrar que isso é o nome de um tipo-de-dados e não o nome de uma variável):

typedef struct {
   double elements[100];
   int    count;
} stackT;

Se stack é uma variável do tipo stackT, então o número de elementos na pilha é  stack.count  e o objeto que está no topo da pilha é  stack.elements[stack.count - 1] .

Se s é um ponteiro para uma pilha do tipo stackT, então o número de elementos na pilha é  s->count  e o objeto que está no topo da pilha é  s->elements[s->count - 1] .

Segue o código que implementa uma pilha de números reais. É preciso ter algumas funções que pudemos evitar no exemplo da calculadora: uma função que cria uma nova pilha e outra que "mata" uma pilha.

///////////////////////////// // Implementação de uma pilha ///////////////////////////// #define MaxStackSize 100 // Uma pilha é um objeto do tipo stackT (ou melhor, um ponteiro // para um objeto do tipo stackT). O vetor elements armazena os // elementos da pilha e count é o número de elementos da pilha. typedef struct { double elements[MaxStackSize]; int count; } stackT; // Operação empilha: coloca element na pilha s. void Push( stackT *s, double element) { if (s->count == MaxStackSize) printf( "Stack size exceeded.\n"); exit( EXIT_FAILURE); } s->elements[s->count++] = element; } // Operação desempilha: retira o elemento que está // no topo da pilha e devolve o valor desse elemento. double Pop( stackT *s) { if (s->count == 0) { printf( "Pop of an empty stack.\n"); exit( EXIT_FAILURE); } return s->elements[--s->count]; }

Além das funções Pop e Push, é conveniente que o módulo de manipulação de pilhas tenha algumas funções "auxiliares":

// Cria uma pilha vazia. Devolve o endereço da nova pilha. stackT *NewStack( void) { stackT *s; s = malloc( sizeof (stackT)); if (s == NULL) exit( EXIT_FAILURE); s->count = 0; return s; } // Libera o espaço ocupado pela pilha s. void FreeStack( stackT *s) { free( s); } // Devolve 1 se a pilha s estiver vazia e // devolve 0 em caso contrário. int StackIsEmpty( stackT *s) { return s->count == 0; }

Poderíamos até acrescentar mais funções ao módulo:

// Devolve o número de elementos na pilha s. int StackDepth( stackT *s) { return s->count; } // Devolve o valor do elemento que está na posição index de s. // O elemento do topo tem index == 0, o elemento que está logo // abaixo do topo tem index == 1 etc. double GetStackElement( stackT *s, int index) { if (index < 0 || index >= s->count) exit( EXIT_FAILURE); return s->elements[s->count - index - 1]; }

Exercícios

6. Veja implementação de uma pilha em uma lista encadeada.