Departamento de Ciência da
Computação - IME - USP
Neste EP você escreverá um programa que lê de um arquivo expressões aritméticas em notação posfixa (= notação polonesa reversa) e calcula e imprime o resultado de cada uma das expressões.
Várias rotinas desse trabalho serão utilizadas no próximo EP, Calculadora II para a construção de uma calculadora de expressões infixas.
2 2.5 + 25.6 4.2 3.1 * - 12 4.3 2.1 / - 3 * 15 -Cada expressão pode conter números e os seguintes símbolos para operações aritméticas:
Para cada expressão posfixa o programa deve calcular e imprimir o seu valor.
operação símbolo adição + subtração - multiplicação * divisão / exponenciação ^ troca de sinal !
2 2.5 + 2 3 - 2.1 2 * 6.4 .8 / 3.1 ! 2 3 ^ 25.6 4.2 3.1 * - 12 4.3 2.1 / - 3 * 15 -
Para o programa executável chamado "polonesa", a execução desse programa seria:
> polonesa entrada.txt Linha 1: 2 2.5 + Resultado: 4.500000 Linha 2: 2 3 - Resultado: -1.000000 Linha 3: 2.1 2 * Resultado: 4.200000 Linha 4: 6.4 .8 / Resultado: 8.000000 Linha 5: 3.1 ! Resultado: -3.100000 Linha 6: 2 3 ^ Resultado: 8.000000 Linha 7: 25.6 4.2 3.1 * - Resultado: 12.580002 Linha 8: 12 4.3 2.1 / - 3 * 15 - Resultado: 14.857143
/* codigos */
#define NUMERO '#'
#define SOMA '+'
#define SUB '-'
#define MULT '*'
#define DIV '/'
#define EXP '^'
#define NEG '!'
typedef struct celula {
char simbolo;
float numero;
struct celula *prox;
} Celula;
Você deve implementar um programa na linguagem C que:
A fila de números e operadores deverá ser implementada por meio de uma lista encadeada circular com cabeça em que cada elemento é do tipo Celula. A implementação desta fila como indicada será também utilizada no próximo EP.
Cada célula cel deverá armazenar um número ou um operador:Escreva uma função com o seguinte protótipo
Celula * constroiFilaPosfixa (char *linha);que recebe um string linha contendo a expressão posfixa e devolve o endereço cab da célula cabeça da fila contruída.
Para calcular o valor da expressão posfixa a partir da fila o seu programa deve utilizar um pilha de números. A pilha deve ser implementada por meio de uma lista encadeada com cabeça em que cada elemento é do tipo Celula. A implementação desta pilha como indicada será também utilizada no próximo EP.
O seu programa deve examinar cada célula da fila e:
Para saber mais detalhes de como o programa realiza o cálculo da expressão em notação posfixa, consulte as notas de aula.
Escreva uma função com o seguinte protótipo
float calculaPosfixa(Celula *cab);
que recebe uma fila circular com cabeça cab de números e operadores representando um expressão posfixa e calcula e devolve o valor da expressão.
Na função constroiFilaPosfixa você necessitará converter uma cadeia de caracteres em um número. Para esta tarefa utilize a função
float strtof(const char *nptr, char **endptr);da biblioteca stdlib.h que recebe um endereço nptr para uma cadeia de caracteres e devolve o número no início da cadeia. O segundo parâmetro da função endptr é utilizada para devolver o endereço do primeiro caractere após o número na cadeia.
Exemplo:
A seguinte função f imprime todos os números recebidos no string linha.
#include <stdio.h>
#include <stdlib.h>
void f (char * linha) {
float valor;
char *ptr = linha;
while (*ptr != '\0')
if (*ptr >= '0' && *ptr <= '9')
{
valor = strtof (ptr, &ptr);
printf ("Achei o numero %f\n", valor);
}
else ptr++;
}
Para o string linha abaixo:
| linha | 1 | 5 | 3 | . | 1 | 4 | + | \0 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Achei o numero 15.000000 Achei o numero 3.140000
O arquivo esqueleto-ep3.c deve ser utilizado para o desenvolvimento de sua solução.
Além das declarações descritas anteriormente, o esqueleto contém o programa main, que realiza a leitura do arquivo de entrada e varre as suas linhas chamando as funções descritas nesse enunciado para calcular o valor das expressões.
Seu programa não precisa fazer nenhuma modificação no main, mas recomendamos que, durante o desenvolvimento, você inclua algumas chamadas para funções que imprimam o conteúdo da pilha e da fila sendo utilizadas.