Departamento de Ciência da
Computação - IME - USP
Neste EP você implementará uma calculadora mais completa. Para isso você escreverá um programa que lê de um arquivo expressões aritméticas em notação infixa corretas e calcula e imprime o resultado de cada uma das expressões. Além da notação infixa, a Calculadora II permite também o uso de variáveis nas expressões além do operador = para atribuições. Aqui, como em um programa, variáveis serão inicializadas por meio de atribuições.
2 + 0.5 A = 1 B = A+2Cada expressão pode conter números, variáveis representadas por uma única letra maiúscula de A a Z, parênteses e os mesmos símbolos utilizados no EP3 para operações, acrescido do símbolo '=' para o operador atribuição. Cada letra maiúscula corresponde a uma variável. As expressões, portanto, podem ser formadas por até 26 variáveis.
Para cada expressão infixa o programa deve calcular e imprimir o seu valor, e imprimir também o conteúdo de todas as variáveis utilizadas até aquele momento.
operação símbolo adição + subtração - multiplicação * divisão / exponenciação ^ troca de sinal ! atribuição =
A tabela abaixo é baseada na tabela de precedência disponível aqui. Nessa tabela, os operadores estão em ordem decrescente de prioridade: na primeira linha os operadores executados em primeiro lugar e na última os operadores executados por último. Assim, o operador '=' possui a menor precedência dentre os operadores da tabela. A coluna direta indica a convenção de associação para os operadores da linha.
| () | esquerda-para-direita | |
| operador unário | ! | direita-para-esquerda |
| ^ | direita-para-esquerda | |
| * / | esquerda-para-direita | |
| + - | esquerda-para-direita | |
| = | direita-para-esquerda |
A tabela abaixo exemplifica a precedência dos operadores. Note a associativida da esquerda para direira entre operadores como '+' e '-' ou '*' e '/' e a associatividade da direita para a esquerda dos operadores '!', '^' e '='.
| expressão | interpretação |
| 2 + 3 + 4 | (2 + 3) + 4 |
| 2 ^ 3 ^ 4 | 2 ^ (3 ^ 4) |
| A * B / C | (A * B) / C |
| A = B + C / 3.2 / C | A = (B + ((C / 3.2) / C)) |
| A = B = C = 3.2 | A = (B = ( C = 3.2 ) ) |
| A * ! B ^ C - 2 | ((A * ((! B) ^ C)) - 2) |
A = 2 B = 3.1 + A 2.2 * 3 C = D = A = B + A / 3.2 / A A = 1 A = (B = A + 1) * 3 ^ ! 2 ^ 2
Se o nome do executável do EP4 é "calculadora", então o resultado da sua execução tendo como entrada o arquivo expressoes.txt produz o seguinte resultado:
> calculadora expressoes.txt
Linha 1: A = 2
A 2=
Resultado: 2.000000
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 2.000000
........................................
Linha 2: B = 3.1 + A
B 3.1 A+=
Resultado: 5.100000
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 2.000000
B | 5.100000
........................................
Linha 3: 2.2 * 3
2.2 3*
Resultado: 6.600000
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 2.000000
B | 5.100000
........................................
Linha 4: C = D = A = B + A / 3.2 / A
C D A B A 3.2/ A/+===
Resultado: 5.412500
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 5.412500
B | 5.100000
C | 5.412500
D | 5.412500
........................................
Linha 5: A = 1
A 1=
Resultado: 1.000000
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 1.000000
B | 5.100000
C | 5.412500
D | 5.412500
........................................
Linha 6: A = (B = A + 1) * 3 ^ ! 2 ^ 2
A B A 1+= 3 2! 2^^*=
Resultado: 162.000000
Conteudo das variaveis:
Variavel | Valor
----------|----------------
A | 162.000000
B | 2.000000
C | 5.412500
D | 5.412500
........................................
#define TRUE 1
#define FALSE 0
/* codigos */
#define NUMERO '#'
#define SOMA '+'
#define SUB '-'
#define MULT '*'
#define DIV '/'
#define EXP '^'
#define NEG '!'
#define ATR '='
typedef struct celula {
char simbolo;
float numero;
struct celula *prox;
} Celula;
typedef struct {
int inic;
float valor;
} Tabela;
O programa utilizará uma tabela para armazenar os valores das 26 possíveis variáveis nas expressões (A, B,..., Y ou Z). Essa tabela será representada através de um vetor de 26 posições em que cada posição é um struct do tipo Tabela. Considere a seguinte declaração que deve ser feita no main:
Tabela variavel[26]A tabela variavel deve ser de tal forma que
A finalidade do campo inic é indicar se a variável já foi inicilizada. Ao criar a tabela variavel, o campo inic de cada posição deve conter FALSE. Quando uma variável for inicializada, o campo inic deve receber TRUE. Assim, por exemplo,
Cada linha do arquivo de entrada contém uma expressão infixa correta formada por números, variáveis e pelos operadores '!', '^', '*', '/', '+', '-', '='. As variáveis são as letras maiúsculas de A a Z (26 letras).
Após a leitura de cada linha contendo uma expressão infixa, o programa deve produzir a expressão posfixa correspondente. Para isto escreva uma função com o seguinte protótipo
char * infixaParaPosfixa (char *linha);que recebe um string linha contendo uma expressão infixa e devolve um string contendo a correspondente expressão posfixa. Esta função é uma adaptação da função de mesmo nome dessa página.
A fila de variáveis, números e operadores deverá ser implementada por meio de uma lista encadeada circular com cabeça em que cada elemento é do tipo Celula, como no EP3.
Cada célula cel deverá armazenar uma variável, um número, ou um operador:
Escreva uma função com o seguinte protótipo
Celula * constroiFilaPosfixa (char *posfixa);que recebe um string posfixa 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 uma pilha. A pilha deve ser implementada por meio de uma lista encadeada com cabeça em que cada elemento é do tipo Celula, como no EP3. Na descrição a seguir, por valor de uma célula cel entenda-se:
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, Tabela variavel[26]);
que recebe uma fila circular com cabeça cab de números e operadores representando um expressão posfixa e o vetor variavel que armazena a tabela de variáveis.
Utilizando a tabela de variáveis a função calcula e
devolve o valor da expressão além de eventualmente alterar ou
inicializar os valores de variáveis na tabela.
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
Não será fornecido um esqueleto para este EP. O seu EP3 deve ser utilizado para o desenvolvimento de sua solução.
Nenhum protótipo das funções pedidas pode ser alterado.
As estruturas pedidas (como filas e pilhas) devem ser implementadas como descritas neste enunciado.
Seu programa deve modificar algumas funções do EP3, como as funções main, calculaPosfixa e constroiFilaPosfixa.
Você pode criar outras funções que julgar conveniente.