Avaliador de expressões

[Douglas Dantas 0]

Olá gente.

 

Faz uns dois meses que venho tentando criar uma calculadora. Eu consegui fazer uma simples, mas não fiquei satisfeito.

 

Eu queria um avaliador que, recebendo uma string com uma expressão, com parênteses, +, -, * e / ele retorne o resultado.

 

Então pesquisei e vi que tinha pouca coisa na Internet sobre. Então era eu mesmo.

 

Resolvi implementar usando uma árvore, visto que a expressão é um ente recursivo, mas vi que tava complicando desnecessariamente. Achei como verificar uma sequência de parênteses bem fechados na net e daí parti:

 

5 + 6 * ( 7 - 4 * ( 5 - 1 ) ) - 2

 

0 0 0 0 1 1 1 1 1 2 2 2 2 1 0 0 0

 

Ou seja, cada vez que ele acha um abre parêntese, ele incrementa a variável de teste em 1, quando fecha, decrementa em 1. Se estiver bem fechado, ao fim será 0. Isso também serve para analisar a profundidade, que é 2, no cado.

 

Então imaginei uma função principal double resolve (char *exp), que primeiro verifica de está bem fechado.

Se a profundidade for maior que zero, procurar o primeiro operador de precedência mais baixa na profundidade zero e retornar resolve(1ª fatia) op resolve(2ªfatia). seria como, no caso: resolve(5) + resolve (6*(7-4*(5-1))-2). Se não ouver + ou - no primeiro nível, procurar pelo primeiro * ou /.

 

Se a profundidade fosse 0 (sem parênteses), e tivesse mais de um operador, ele faria o mesmo processo anterior, recursivamente. Até que chegaria um momento em que o numero de operadores fosse 1 ou nenhum, o caso mínimo.

 

Eu fiz os seguintes códigos:

 

calc.h: http://pastebin.com/hhfiNB5B

calc.c: http://pastebin.com/sVt9mJhu

main.c: http://pastebin.com/kvcnjqJf

 

Eu estou com uma dificuldade de tratar unários e o código calc.c está cheio de erros. Queria sugestões, saber se o algoritmo é por aí mesmo e como tratar unários.

 

Desde já, obrigado.

[guidjos 65]

Bem-vindo, Douglas!

Você está no caminho certo.

Um dos clássicos da programação, que discute ASTs, é o Wizard Book: http://mitpress.mit.edu/sicp/full-text/book/book.html

De volta ao C, minhas observações iniciais são:

1. No calc.h, a declaração de erro está errada. O correto seria:

char *erro[] = {"Parenteses invalidos.", "Erro de sintaxe"};

2. Não recomendo o uso do storage class specifier register das declarações (como na linha 7 do calc.c).

3. É preciso incluir stdlib.h no arquivo calc.c.

4. Recomendo não fazer cast do valor de retorno de malloc, já que existe conversão implícita bem definida entre (T *) e (void *), sendo (T) um tipo de objeto. Exemplo:

        char *fatia = (char *) malloc ((f-i+1)*sizeof(char)); // bleh

        char *fatia = malloc((f-i+1)*sizeof(char)); // melhor!

5. Por definição, sizeof (char) é 1. Uma melhoria do código acima seria:

        char *fatia = malloc(f-i+1);

6. Nunca assuma que malloc, realloc ou calloc conseguiram todos os bytes que você pediu:

       char *fatia = malloc(f-i+1);

       if (!fatia) 

       {

              /* imprimir msg de erro, sair */ 

       }

Outra alternativa:

void xmalloc(size_t size)

{

    void *result = malloc(size);


    if (!result)

    {

        /* mensagem de erro, fim do programa */

    }


    return result;

}

7. Na linha 41 do calc.c há um parêntese direito desnecessário e errado.

8. Nas linhas 63 e 66, faltam parênteses direitos para fechar a lista de argumentos a atof.

9. Sugiro usar strtod ao invés de atof.

10. Acho que você esqueceu de chamar a função fats na linha 64.

A lista continua... sugiro que você examine os resultados da seguinte linha de compilação:

gcc -std=c99 -Wall -Wextra -pedantic main.c calc.c -o calc

Se tiver problemas com algum erro em específico, poste aqui e ajudaremos.

[Douglas Dantas 0]

Obrigado. Alguns desses erros eu verifiquei depois de postar no fórum, como o *erro, o parêntese errado na linha 63...

 

Muito obrigado, vou ver o livro que você mandou e vou fazer modificações necessárias. Qualquer progresso eu posto.

 

Uma pergunta, por que não devo usar register e nem cast? Só pra saber, porque eu vi essas recomendações no livro C Completo e Total. O register faria com que, se possível, a variável funcionasse num registrador e, o cast, tornaria o código compatível com o C++.

[Douglas Dantas 0]

Boa, eu já consegui fazer o analisador de expressões. Ele deu certo com as expressões seguintes que testei:

5

5+(6*7)

5+34

5+(6*7+6)

-5

-5*10

-6*30.

-6/10

As únicas expressões que eu não consegui foram, sobre unários, as do tipo:

-5+45 ou -6+14

I. e., ele não soma unários, é só esse o problema. Do mais estou feliz :D

Alguém sabe o por que de ele não conseguir tratar unários?

Novos códigos:

https://docs.google.com/file/d/0B2cA11bPc9S7YlpsMHE3VEFCRzA/edit?usp=sharing

[guidjos 65]

O `register` é uma sugestão, que, em muitas arquiteturas, não faz sentido algum. De forma geral, é melhor deixar a otimização de performance para os compiladores/interpretadores, investindo sempre na legibilidade.

 

O cast introduz sim compatibilidade com C++. Mas há muitas diferenças mais entre as duas linguagens, e você precisaria ficar atento a todas, caso quisesse seguir essa filosofia. Sugiro que escolha a linguagem na qual deseja escrever seu programa e foque nela.

 

Sobre o livro "C Completo e Total": ele é uma fonte péssima. Sugiro o bom e velho K&R 2 ou "C: A Reference Manual".

 

Para postar códigos, sugiro usar um site como o http://gist.github.com . Talvez valha a pena aprender a usar o git desde já. Tenho uma conta no github e acho muito prático - talvez te ajude.

[Douglas Dantas 0]

Obrigado pelas dicas, vou pesquisar mais ainda, aliás, sempre. Vou criar uma conta no Git.

 

Graças a Deus o programa ta funcionando bem, depois vou otimizá-lo e embutir em outras aplicações. Estou procurando que há de errado com expressões do tipo -5+3 ou -5-7, você pode me ajudar?

 

Desde já obrigado.

[Douglas Dantas 0]

Eu postei o código certo. O certo é esse:

https://docs.google.com/file/d/0B2cA11bPc9S7ekFkbnU1QWR4UVE/edit?usp=sharing

[Douglas Dantas 0]

Melhorei meu algoritmo e também achei o local do erro. É na função trata_una(). Obrigado.