1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

calculadora postfix em arvore binaria c++

Discussão em 'Programação' iniciada por jpmor82, 24 de Maio de 2008. (Respostas: 0; Visualizações: 2118)

  1. jpmor82

    jpmor82 Power Member

    Ola, boa noite estou a tentar fazer uma calculadora em arvore binaria, ja tenho muito codigo feito, so me falta por a imprimir a expressao derivada e simplificar a expressao, primeiro gostaria de saber se alguem me ajuda a imprimir a expressao derivada, ja que e uma arvore nova.
    O codigo fica na resposta

    Código:
    #include <iostream>
    #include<cstdlib>
    #include<cmath>
    #include<list>
    #include<cctype>
    #include<cstring>
    usingnamespace std;
    double valorx=NULL; // variavel global para o caso do calcula que guarda nesta variavel o valor de x
    class Expressao;
    class No 
    {
    public: No(No*arg1,No*arg2,char); // +, -, *, /, ...
    No(No*unico,char); // sin, cos, ...
    No(double); // valor
    friendclass Expressao;
    No* Duplica(void);
    double Calcula(void);
    No* Simplifica(void);
    No* Deriva(void);
    int Imprime(void);
    private: No* pesq;
    No* pdir;
    char op;
    double valor;
    };
    No::No (No*arg1,No*arg2,char c) 
    { 
    pesq = arg1;
    pdir = arg2;
    op = c;
    valor = NULL;
    }
    No::No (No*unico,char c)
    {
    pdir = NULL;
    pesq = unico;
    op = c;
    valor = NULL;
    } 
    No::No (double v)
    {
    pesq = NULL;
    pdir = NULL;
    op = 0;
    valor = v;
    }
    No* No::Duplica(void)
    {
    No* pNovo = new No(valor);
    pNovo->op = op;
    if( (pesq == NULL) && (pdir == NULL) )
    return pNovo;
    else
    if( pesq == NULL )
    {
    pNovo->pdir = pdir->Duplica();
    return pNovo;
    }
    else
    if( pdir == NULL )
    {
    pNovo->pesq = pesq->Duplica();
    return pNovo;
    }
    else
    {
    pNovo->pdir = pdir->Duplica();
    pNovo->pesq = pesq->Duplica();
    return pNovo;
    }
    }
    class PilhadeNos // pilha de nos para empilhar varios nos da entrada do programa
    {
    public:PilhadeNos& Push(No*); 
    No* Pop(void);
    private:list<No*> pilha;
    };
    PilhadeNos& PilhadeNos::Push(No*p)
    {
    pilha.push_back(p);
    return *this;
    }
    No* PilhadeNos::Pop(void)
    {
    No*p = pilha.back(); //último elemento
    pilha.pop_back();
    return p;
    }
    class Expressao // class da calculadora
    {
    public:
    Expressao(void) { pRaiz = 0; };
    Expressao(No*p);
    No* Simplifica(void) {return pRaiz->Simplifica();}; // simplifica a expressao
    double Calcula(void) {return pRaiz->Calcula();}; //calcula a expressao com valor de x
    No* Deriva(void) {return pRaiz->Deriva();}; // faz a derivada
    void LePosfixo(list<char*> posfixo); // funcao cria a arvore a partir da pilha de nos
    int Imprime(void) {return pRaiz->Imprime();}; // imprimir a arvore
    private:
    No*pRaiz;
    };
    void Expressao::LePosfixo(list<char*> posfixo)
    {
    PilhadeNos pilha;
    list<char*>::iterator s = posfixo.begin();
    while( s!=posfixo.end())
    {
    char ss = (*s)[0];
    if(isdigit(ss) || ((ss == '-') && isdigit((*s)[1])) ) //se é número o menos e para o caso de um numero ser negativo
    {
    double v = atof(*s);
    No*p=new No(v);
    pilha.Push(p);
    }
    else
    if(ss=='s') // caso do seno
    {
    No*p = new No(pilha.Pop(),'s');
    pilha.Push(p);
    }
    else
    if(ss=='c') // caso do seno
    {
    No*p = new No(pilha.Pop(),'c');
    pilha.Push(p);
    }
    else
    if(ss=='e')// caso do e^
    {
    No*p = new No(pilha.Pop(),'e');
    pilha.Push(p);
    }
    else
    if(ss=='x') // caso do x, no caso do calcula valorx diferente de null nos outros valorx = null
    {
    No*q = new No(valorx);
    No*p = new No(q,'x');
    pilha.Push(p);
    }
    else
    if(ss=='*') // caso da multiplicacao
    {
    No*p = new No(pilha.Pop(), pilha.Pop(), '*');
    pilha.Push(p);
    }
    else 
    if(ss=='p') // caso da potencia
    {
    No*p = new No(pilha.Pop(), pilha.Pop(), 'p');
    pilha.Push(p);
    }
    else
    if(ss=='/') // caso da divisao
    {
    No*p = new No(pilha.Pop(), pilha.Pop(), '/');
    pilha.Push(p);
    }
    else
    if(ss=='-') // caso da subtraccao
    {
    No*p = new No(pilha.Pop(), pilha.Pop(), '-');
    pilha.Push(p);
    }
    else
    if(ss=='+') // caso da soma
    {
    No*p = new No(pilha.Pop(), pilha.Pop(), '+');
    pilha.Push(p);
    }
    s++;
    }
    pRaiz = pilha.Pop();
    }
    No* No::Simplifica(void)
    {
    return 0;
    }
    double No::Calcula ( void ) // funcao recursiva fica em espera ate receber valor, quando recebe valor comeca 
    { // a fazer as operacoes correspondentes a expressao tem que estar correcta
    if ( op == '+' )
    return pesq->Calcula() + pdir->Calcula();
    else
    if ( op == '-' )
    return pesq->Calcula() - pdir->Calcula();
    else
    if ( op == '/' )
    return pesq->Calcula() / pdir->Calcula();
    else
    if ( op == '*' )
    return pesq->Calcula() * pdir->Calcula();
    else
    if ( op == 's' ) 
    return sin( pesq->Calcula() );
    else 
    if ( op == 'e' ) 
    return exp( pesq->Calcula() );
    else 
    if ( op == 'c' ) 
    return cos( pesq->Calcula() );
    else 
    if ( op == 'p' ) 
    return pow(pesq->Calcula(), pdir->Calcula()) ;
    else
    if ( op == 'x' ) 
    return pesq->Calcula();
    else
    return valor;
    }
    No* No::Deriva ( void ) // Funcao recursiva que cria nova arvore com a derivada da expressao
    {
    if ( op == '+' )
    {
    No* pNovo = new No('+');
    pNovo->pesq = pesq->Deriva();
    pNovo->pdir = pdir->Deriva();
    return pNovo;
    }
    else
    if ( op == '-' )
    {
    No* pNovo = new No('-');
    pNovo->pesq = pesq->Deriva();
    pNovo->pdir = pdir->Deriva();
    return pNovo;
    }
    else
    if ( op == '/' )
    { 
    No* pNovoDivide = new No('/');
    No* pNovoMenos = new No('-');
    No* pNovoMultiplicacao1 = new No('*');
    No* pNovoMultiplicacao2 = new No('*');
    No* pNovoU = pesq->Duplica();
    No* pNovoV1 = pdir->Duplica();
    No* pNovoDerU = pNovoU->Deriva();
    No* pNovoDerV = pNovoV1->Deriva();
    No* pNovoPotencia = new No('^');
    No* pNovoV2 = pdir->Duplica();
    No* pNovo2 = new No('2');
    pNovoMultiplicacao1->pesq = pNovoDerU;
    pNovoMultiplicacao1->pdir = pNovoV1;
    pNovoMultiplicacao2->pesq = pNovoU;
    pNovoMultiplicacao1->pdir = pNovoDerV;
    pNovoMenos->pesq = pNovoMultiplicacao1;
    pNovoMenos->pdir = pNovoMultiplicacao2;
    pNovoPotencia->pesq = pNovoV2;
    pNovoPotencia->pdir = pNovo2;
    pNovoDivide->pesq = pNovoMenos;
    pNovoDivide->pdir = pNovoPotencia;
    
    return pNovoDivide;
    }
    else
    if ( op == '*' )
    { 
    No* pNovoSoma = new No('+');
    No* pNovoMultiplicacao1 = new No('*');
    No* pNovoMultiplicacao2 = new No('*');
    No* pNovoU = pesq->Duplica();
    No* pNovoV = pdir->Duplica();
    No* pNovoDerU = pNovoU->Deriva();
    No* pNovoDerV = pNovoV->Deriva();
    pNovoMultiplicacao1->pesq = pNovoDerU;
    pNovoMultiplicacao1->pdir = pNovoV;
    pNovoMultiplicacao2->pesq = pNovoU;
    pNovoMultiplicacao1->pdir = pNovoDerV;
    pNovoSoma->pesq = pNovoMultiplicacao1;
    pNovoSoma->pdir = pNovoMultiplicacao2;
    
    return pNovoSoma;
    }
    else
    if ( op == 's' ) 
    {
    No* pNovoMultiplicacao = new No('*');
    No* pNovoU = pesq->Duplica();
    No* pNovoDerU = pNovoU->Deriva();
    No* pNovoCos = new No('c');
    pNovoCos->pesq = pNovoU;
    pNovoMultiplicacao->pesq = pNovoDerU;
    pNovoMultiplicacao->pdir = pNovoCos;
    
    return pNovoMultiplicacao;
    }
    else 
    if ( op == 'e' ) 
    {
    No* pNovoMultiplicacao = new No('*');
    No* pNovoU = pesq->Duplica();
    No* pNovoDerU = pNovoU->Deriva();
    No* pNovoExp = new No('e');
    pNovoMultiplicacao->pesq = pNovoDerU;
    pNovoExp->pesq = pNovoU;
    pNovoMultiplicacao->pesq = pNovoDerU;
    pNovoMultiplicacao->pdir = pNovoExp;
    
    return pNovoMultiplicacao;
    }
    else 
    if ( op == 'c' ) 
    {
    No* pNovoMenos = new No('-');
    No* pNovo0 = new No('0');
    No* pNovoMultiplicacao = new No('*');
    No* pNovoU = pesq->Duplica();
    No* pNovoDerU = pNovoU->Deriva();
    No* pNovoSin = new No('s');
    pNovoSin->pesq = pNovoU;
    pNovoMultiplicacao->pesq = pNovoDerU;
    pNovoMultiplicacao->pdir = pNovoSin;
    pNovoMenos->pesq = pNovo0;
    pNovoMenos->pdir = pNovoMultiplicacao;
    
    return pNovoMenos;
    }
    else 
    if ( op == 'p' )
    { 
    No* pNovoMultiplicacao = new No('*');
    No* pNovoExpoente1 = new No(pdir->valor);
    No* pNovoPotencia = new No('p');
    No* pNovoBase = new No(pesq->valor);
    No* pNovoMenos = new No('-');
    No* pNovoExpoente2 = new No(pdir->valor);
    No* pNovo1 = new No('1'); 
    pNovoMenos->pesq = pNovoExpoente2;
    pNovoMenos->pdir = pNovo1;
    pNovoPotencia->pdir = pNovoBase;
    pNovoPotencia->pesq = pNovoMenos;
    pNovoMultiplicacao->pesq = pNovoExpoente1;
    pNovoMultiplicacao->pdir = pNovoPotencia;
    
    return pNovoMultiplicacao;
    } 
    else
    if ( op == 'x' ) 
    {
    No* pNovo = new No('1');
    return pNovo;
    }
    else
    {
    No* pNovo = new No('0');
    return pNovo;
    }
    }
    int No::Imprime(void)
    {
    if( (pesq==NULL) && (pdir==NULL) )
    {
    if(valor!=NULL)
    cout << valor;
    return 0;
    }
    else
    if( pdir == NULL)
    {
    if( op == 'x' )
    cout << "x";
    else
    {
    if( op == 's' )
    cout << "sin( ";
    else
    if( op == 'c' )
    cout << "cos( ";
    else
    if( op == 'e' )
    cout << "exp( ";
    
    pesq->Imprime();
    cout << " )";
    
    }
    }
    else
    {
    if( op == '*' )
    {
    cout << "( ";
    pesq->Imprime();
    cout << " ) * ";
    cout << "( ";
    pdir->Imprime();
    cout << " )";
    }
    else 
    if( op == '/' )
    {
    cout << "( ";
    pesq->Imprime();
    cout << " ) / ";
    cout << "( ";
    pdir->Imprime();
    cout << " )";
    }
    else 
    if( op == 'p' )
    {
    cout << "( ";
    pesq->Imprime();
    cout << " ) ^ ";
    cout << "( ";
    pdir->Imprime();
    cout << " )";
    }
    else 
    if( op == '+' )
    {
    pesq->Imprime();
    cout << " + ";
    pdir->Imprime();
    } 
    else 
    if( op == '-' )
    {
    pesq->Imprime();
    cout << " - ";
    pdir->Imprime();
    } 
    }
    return 1;
    }
    int main(int argc, char* argv[])
    { 
    int i, inicio=2;
    list<char*> args;
    if (argc <= 2) // porque se argc <= 2 nao contem todos os dados necessarios ao programa
    {
    fprintf(stderr, "Erro introduza: %s (comando) parametros", argv[0]);
    cout << endl;
    }
    else
    {
    if( !strcmp(argv[1],"calcula") )
    {
    inicio=3;
    valorx = atof(argv[2]);
    }
    for(i=inicio ; i<argc ; i++)
    {
    args.push_back(argv[i]);
    }
    Expressao e;
    e.LePosfixo(args);
    
    if( !strcmp(argv[1],"calcula") )
    {
    cout << e.Calcula() << endl;
    }
    else
    if( !strcmp(argv[1],"deriva") )
    {
    No* novo=e.Deriva();
    novo->Imprime();
    cout << endl;
    }
    else
    if( !strcmp(argv[1],"infix") )
    {
    e.Imprime();
    cout << endl;
    }
    else
    if( !strcmp(argv[1],"simplifica") )
    {
    e.Simplifica();
    cout << endl;
    } 
    }
    system("PAUSE");
    return 0;
    }
     
    Última edição pelo moderador: 24 de Maio de 2008

Partilhar esta Página