Polonesa 0 1

Prévia do material em texto

Universidade Federal do Rio de Janeiro 
Introdução a C/C++ 
Eduarda Leal de Carvalho DRE: 118199369 
 
CALCULADORA POLONESA 
 
A calculadora polonesa utiliza a notação Polonesa (reversa). Ela foi proposta como uma 
forma de escrever expressões aritméticas e lógicas sem a necessidade de utilizar 
parênteses. Na notação polonesa, os operadores são escritos depois dos operandos. 
 
CASO EXEMPLO 
Como já lido acima, a calculadora polonesa é um pouco diferente das que costumamos 
utilizar. Vejamos um exemplo de uma entrada e o seu resultado: 
%echo '2 3 4 + *' | ./polonesa.exe 
 14 
% 
Quando o programa vê um número, ele coloca esse número no topo da pilha e quando 
vê uma operação, ele retira dois elementos da pilha e computa a operação envolvendo 
esses elementos e o resultado da operação é recolocado na pilha. Nesse caso, ele 
recebe 3 números e os 2 operadores e vai adicionando na pilha e ela fica da seguinte 
forma: 
 
4 
3 
2 
+ 
* 
 
Agora na hora de realizar as operações ele pega os dois números no topo da pilha (4 e 
3) e o primeiro operador (+). Feito a operação, ele retira esses dois números do topo da 
pilha e coloca o resultado da operação (7). e então a pilha fica da seguinte forma: 
 
7 
2 
* 
 
E agora o mesmo passo a passo é feito. Pega os dois números no topo da pilha (7 e 2) 
e o operador (*). Feito a operação ele retira os dois números da pilha e coloca o 
resultado da operação (14). Realizando dessa forma, ele imprime o resultado que no 
caso é o 14. 
 
 
 
 
 
 
 
 
STACK.C 
No arquivo stack.c, o procedimento push() adiciona um item no topo da pilha e o 
procedimento pop() retorna o item no topo e o remove da pilha. Abaixo é possível ver o 
código desse arquivo. 
#include <stdio.h> 
#include "polonesa.h" 
#define MAXVAL 100 
 
int sp = 0; 
int val[MAXVAL]; 
 
void push(int n) { 
 if (sp < MAXVAL) 
 val[sp++] = n; 
 else 
 printf("error: stack full: %d\n", n); 
} 
 
int pop(void) { 
 if (sp > 0) 
 return val[--sp]; 
 else { 
 printf("error: tried to pop an empty stack\n"); 
 return 0; 
 } 
O push() recebe o operador /++/ na direita de sp pois ele está inserindo um objeto a 
pilha e o pop() recebe o operador /--/ na esquerda de sp pois ele está removendo um 
objeto da pilha. 
 
PILHA 
Uma pilha é uma estrutura de dados e é chamada de assim pois permite “empilhar” os 
itens que serão armazenados e “desempilhar” estes elementos. 
 
GETCH.C 
O arquivo getch().c possui dois procedimento: getch() e ungetch(). O procedimento 
getch() entrega o próximo caractere de entrada a ser considerado e o ungetch () irá 
retorná-los antes de ler a nova entrada. Esses dois procedimentos trabalham juntos é 
simples. ungetch coloca os caracteres empurrados para trás em um buffer 
compartilhado - uma matriz de caracteres. getch lê do buffer se houver mais alguma 
coisa e chama getchar se o buffer estiver vazio. 
#include <stdio.h> 
#define BUFSIZE 100 
 
char buf[BUFSIZE]; /* a buffer for ungetch() */ 
int p = 0; /* the next free position in buf */ 
 
int getch(void) { /* get a (possibly pushed-back) character */ 
 if (p > 0) 
 return buf[--p]; 
 else 
 return getchar(); 
} 
 
void ungetch(int c) { 
 if (p >= BUFSIZE) 
 printf("ungetch: too many characters; buffer full\n"); 
 else 
 buf[p++] = c; 
} 
 
#ifdef TEST 
int main(void) { 
 int c; 
 ungetch('a'); ungetch('b'); ungetch('c'); 
 c = getch(); printf("c = %c, p = %d\n", c, p); 
 c = getch(); printf("c = %c, p = %d\n", c, p); 
 c = getch(); printf("c = %c, p = %d\n", c, p); 
 return 0; 
} 
#endif 
MECANISMOS BUFFER 
Somos obrigados a utilizar um mecanismo de buffer pois ele é quem liga o getch() e o 
ungetch(). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
GETOP() 
O getop() ele funciona como um filtro na hora do usuário informar o número e o 
operador que será realizada a conta. Ele verifica se tem algum espaço em branco ou 
um tab e caso o usuário informe o operador sem o espaçamento ideal, ele é capaz de 
identificar quando termina os números e qual o operador. 
Veja o código abaixo: 
include <stdio.h> 
#include <ctype.h> 
#include "polonesa.h" 
 
int getop(char s[]) { 
 int i, c; 
 
 while ((s[0] = c = getch()) == ' ' || c == '\t') 
 ; /* Esse bloco de código será repetido até localizar um caractere que, no 
caso, será o operador */ 
 
 s[1] = '\0'; /* localizado o operador e armazenado ele em s[0], fecharemos o 
caractere com ‘\0’ na próxima posição */ 
 
 if (!isdigit(c)) { 
 return c; /* Se ser não for um dígito então c é o operador */ 
 } 
 
 i = 0; 
 if (isdigit(c)) 
 while (isdigit(s[++i] = c = getch()))/* Se c for um digito ele irá ler até 
encontrar algo diferente de um digito */ 
 ; 
 s[i] = '\0'; /* encontrando algo diferente de um digito, a string será fechada 
*/ 
 
 if (c != EOF) 
 ungetch(c); /* Se c não for o final do arquivo, iremos empurrar o caractere c 
de volta para a entrada */ 
 
 return NUMBER; 
} 
Ambos são usados para fechar a string mas o s[1]= ‘\0’ é utilizado para separar o 
operador que foi localizado e armazenado em s[0]. Já o s[i] = ‘\0’ é utilizado para 
fechar a string após receber todos os números inteiro e por serem duas coisas 
diferentes (operador e número) fazemos isso duas vezes. 
Devemos fazer o ungetch(c) pois pode ocorrer do usuário colocar o operador junto ao 
número sem o espaçamento necessário, então pegamos esse caractere que e 
retornaremos ele para a “entrada padrão”. Fazemos o ungetch() para toda vez que o 
programa lê um caractere a mais empurrar o caractere de volta para o fluxo de 
entrada. 
 
MAIN() 
É no main() que realizamos as operações, já que já temos o operando e o operador 
“filtrados” e corretos. O procedimento atoi() converte uma string para um inteiro e 
pude descobrir isso acessando o manual. O programa em C não nos deixa escolher a 
ordem dos operandos e por se tratar de uma subtração ou divisão, a ordem dos 
operandos é importante. Se fizéssemos como na adição ou multiplicação o resultado 
poderia vir diferente do que esperamos. 
CONCLUSÃO 
A melhor forma de apresentar a implementação do programa foi a especificada acima 
pois o main() é o parte principal mas totalmente ligada aos outros arquivos. Se 
começássemos pelo main não iriamos compreender alguns procedimentos e variáveis 
pertencentes aos outros arquivos.