Postfix to tree and then to stack C ++

Question

Postfix to tree and then to stack C ++

Navigation

#1 by (0 votes)

2

I'm trying to make the following pseudocodigo

Pseudocodigo:

Algoritmo-Posfija-Árbol
INICIO
    Crear pila y árbol, inicialmente vacíos
    MIENTRAS posfija no este vacía y no hay errores HACER
       Extraer el primer termino de posfija (lo llamaremos E)
       SELECTOR E
        CASO E es operando :    Insertar E en la pila           
        CASO E es operador :    SI La pila tiene menos de dos elementos ENTONCES
                            ERROR 
                        SINO
                            Extraer elemento de la pila (lo llamaremos A2)
                            Extraer elemento de la pila (lo llamaremos A1)
                            Crear un árbol donde la raíz contenga al operador E,
                            el hijo izquierdo sea A1 y el hijo derecho sea A2
                            Insertar el árbol en la pila
                        FIN-SI
        DEFAULT: ERROR
       FIN-SELECTOR
    FIN-MIENTRAS
    SI pila vacía o con más de un elemento ENTONCES
        ERROR
    SINO
        Extraer elemento de la pila (lo llamaremos E)
        LLAMAR A Evaluar_Arbol(E);
        El resultado del algoritmo (el árbol de salida) es E      
    FIN-SI
    { Borrado de la pila, si se ha producido error }
    MIENTRAS pila no esté vacía HACER
        Extraer elemento de la pila
        Destruir elemento
    FIN-MIENTRAS
    Destruir pila
FIN

But when I get to the point where I have to pass the values to the tree, it works only if it's a simple operation like "34+" but with another operation added, example 34 + 5 * it gives me this error

and that when I try to pass it from the tree to the stack in the case of operation 34+ I get the following compilation error Can not convert 'Node *' to 'char' . I understand that I can not enter a structure in a char but I do not know how to do it with a pointer inside the function.

Code so far:

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>


struct nodo {
       char palabra;
       struct nodo *sgte;
       struct nodo *arbol;
       };

typedef struct nodo *Ptrpila;
typedef struct nodo *Tlista;


struct Nodo{
    char datoA;
   Nodo *izq;
   Nodo *der;
};

struct t_nodo{
    char datoP;
   t_nodo *sgte;
   t_nodo *izq;
   t_nodo *der;
};

//------------POSFIJO--------
void push(Ptrpila &,char);
char pop(Ptrpila &);
void agregar(Tlista &,char);
void destruir(Ptrpila &);
int  prioridadInfija(char );
int  prioridadPila(char );
void imprimir( Tlista &);
void balanceoSimbolos( Ptrpila &, char []);
//------------ARBOL-----------
Nodo *crearNodo(char);
void mostrarArbol(Nodo *,int);
void eliminarArbol(Nodo*&);

void meterPila(t_nodo*&, char);
void sacarPila(t_nodo*&, char&);

Nodo *arbol = NULL;
Nodo *arbolAux = NULL;


main(){
    Ptrpila p=NULL;
   Ptrpila M=NULL;
   t_nodo *pila = NULL;
   Tlista lista=NULL;
   char cad[100], salida,E,A2,A1;
   int tam, c,contador=0;

   do{
   cout<<"Operacion Infija:\n";
   gets(cad);
   if(M!=NULL)
    destruir(M);
      balanceoSimbolos(M,cad);
      }while(M!=NULL);
   tam=strlen(cad);
   for(int i=0;i<tam;i++){
    if(cad[i]>=48&&cad[i]<=57||cad[i]=='.')
        agregar(lista,cad[i]);
    if(cad[i]=='+'||cad[i]=='-'||cad[i]=='*'||cad[i]=='/'||cad[i]=='('||cad[i]=='^'){
        if(p==NULL){
            push(p,cad[i]);
         }else{
            if(prioridadInfija(cad[i])>prioridadPila(p->palabra)){
                push(p,cad[i]);
            }else{
                if(prioridadInfija(cad[i])==prioridadPila(p->palabra)){
                    c=pop(p);
                  agregar(lista,c);
                  push(p,cad[i]);
               }else{
                    c=pop(p);
                  agregar(lista,c);
               }
            }
        }
      }
      if(cad[i]==')'){
        while(p->palabra!='('&&p!=NULL){
            c=pop(p);
            agregar(lista,c);
         }
         if(p->palabra=='(')
            c=pop(p);
         }
      }
      while(p!=NULL){
            c=pop(p);
         agregar(lista,c);
      }

      cout<<"Notacion Postfija:\n\n";
      while(lista!=NULL){

         E=lista->palabra;

         if(E>=48&&E<=57||E=='.'){
            meterPila(pila, E);
         }else{
           arbol=crearNodo(E);
           sacarPila(pila, E);
           A1=E;
           sacarPila(pila, E);
           A2=E;
           arbol->der=crearNodo(A1);
           arbol->izq=crearNodo(A2);
           arbolAux = arbol;
           meterPila(pila,arbol);
           cout<<"AQUI INICIA LA INSERCION AL ARBOL:\n";
           mostrarArbol(arbolAux,contador);
         }

         lista = lista->sgte;
      }cout<<"\n\n";

        system("pause");
        return 0;

}

//--------------INICIO POSTFIJA---------------------------

void push(Ptrpila &p,char a){
    Ptrpila q=new struct nodo;
    q->palabra=a;
    q->sgte=p;
    p=q;
}


char pop(Ptrpila &p){
    int n;
    Ptrpila aux;

    n=p->palabra;
    aux=p;
    p=p->sgte;
    delete(aux);
    return n;

}


void agregar(Tlista &lista,char a){
    Tlista t, q = new(struct nodo);

   q->palabra  = a;
   q->sgte = NULL;

   if(lista==NULL){
    lista = q;
   }else{
    t = lista;
      while(t->sgte!=NULL){
        t = t->sgte;
      }
        t->sgte = q;
   }
}

void destruir(Ptrpila &M)
{    Ptrpila aux;

     if(M !=NULL)
     {
         while(M!=NULL)
         {
             aux=M;
             M=M->sgte;
             delete(aux);
         }

      }
}

int prioridadInfija(char a){
    if(a=='^')
    return 4;
   if( a=='*')
    return 2;
   if( a=='/')
       return 2;
   if( a=='+')
       return 1;
   if( a=='-')
       return 1;
   if(a=='(')
       return 5;
}


int prioridadPila(char a){
    if(a=='^')
    return 3;
   if( a=='*')
      return 2;
   if( a=='/')
      return 2;
   if( a=='+')
      return 1;
   if( a=='-')
      return 1;
   if(a=='(')
      return 0;
}

void balanceoSimbolos( Ptrpila &p, char cad[])
{
     Ptrpila aux;
     int i = 0;

     while( cad[i] != 'Algoritmo-Posfija-Árbol
INICIO
    Crear pila y árbol, inicialmente vacíos
    MIENTRAS posfija no este vacía y no hay errores HACER
       Extraer el primer termino de posfija (lo llamaremos E)
       SELECTOR E
        CASO E es operando :    Insertar E en la pila           
        CASO E es operador :    SI La pila tiene menos de dos elementos ENTONCES
                            ERROR 
                        SINO
                            Extraer elemento de la pila (lo llamaremos A2)
                            Extraer elemento de la pila (lo llamaremos A1)
                            Crear un árbol donde la raíz contenga al operador E,
                            el hijo izquierdo sea A1 y el hijo derecho sea A2
                            Insertar el árbol en la pila
                        FIN-SI
        DEFAULT: ERROR
       FIN-SELECTOR
    FIN-MIENTRAS
    SI pila vacía o con más de un elemento ENTONCES
        ERROR
    SINO
        Extraer elemento de la pila (lo llamaremos E)
        LLAMAR A Evaluar_Arbol(E);
        El resultado del algoritmo (el árbol de salida) es E      
    FIN-SI
    { Borrado de la pila, si se ha producido error }
    MIENTRAS pila no esté vacía HACER
        Extraer elemento de la pila
        Destruir elemento
    FIN-MIENTRAS
    Destruir pila
FIN
')
     {
            if( cad[i]=='(' || cad[i]=='[' || cad[i]=='{' )
            {
                 push( p, cad[i] );
            }
            else if( cad[i]==')' || cad[i]==']' || cad[i]=='}' )
            {
                 aux = p;

                 if(aux!=NULL)
                 {
                      if( cad[i]==')' )
                      {
                           if( aux->palabra == '(')
                              pop( p );
                      }
                      else if( cad[i]==']' )
                      {
                           if( aux->palabra == '[')
                              pop( p );
                      }
                      else if( cad[i]=='}' )
                      {
                           if( aux->palabra == '{')
                              pop( p );
                      }
                 }
                 else
                     push( p, cad[i] );
            }
            i++;
     }

     if(p==NULL)
         cout<<"\n\tBalanceo CORRECTO..."<<endl<<endl;
     else
         cout<<"\n\t Balanceo INCORRECTO, faltan simbolos de agrupacion..."<<endl;


}


//--------------------------INICIO ARBOL--------------------------------

void meterPila(t_nodo *&pila, char palabra){
    t_nodo *nodo = (t_nodo*)malloc(sizeof(t_nodo));
   nodo->datoP =  palabra;
   nodo->sgte = pila;
   pila = nodo;

}

void sacarPila(t_nodo *&pila, char &n){
    t_nodo *aux=pila;
   n = aux->datoP;
   pila=aux->sgte;
   free(aux);
}

Nodo *crearNodo(char n){
    Nodo *nuevoNodo = new Nodo();
   nuevoNodo->datoA = n;
   nuevoNodo->izq = NULL;
   nuevoNodo->der = NULL;

   return nuevoNodo;
}


void mostrarArbol(Nodo *arbol, int contador){
    if(arbol == NULL){
    return;
   }else{
    mostrarArbol(arbol->der, contador+1);
      for(int i=0; i<contador; i++){
        cout<<"  ";
      }
      cout<<arbol->datoA<<endl;
      mostrarArbol(arbol->izq, contador+1);
   }
}

void eliminarArbol(Nodo *&arbol){
    if(arbol != NULL){
    eliminarArbol(arbol->izq);
      eliminarArbol(arbol->der);
      arbol = NULL;
   }
}

c++ pilas

asked by GersonRod_ 12.04.2017 в 19:12

source

1 answer

Error breaking a c ++ program into .h, .cpp, and main.cpp files Because I can not save more than 4096 characters in a Delphi 10.1 string

score 0 · Answer 1

I've already said in other messages: C ++ no is C:

The C ++ system headers do not end with .h . And those inherited from C should use the prefix c :

#include <iostream> // sin .h, en este caso el .h no es portable
#include <cstdlib>  // prefijo c
#include <stdio.h>  // Esta no forma parte del estandar

For classes and structures it is not necessary to use typedef struct :

// esto
struct nodo {
  char palabra;
  struct nodo *sgte;
  struct nodo *arbol;
};
// es equivalente a
struct nodo {
  char palabra;
  nodo *sgte;
  nodo *arbol;
};

// y esto
typedef struct nodo *Ptrpila;
// es equivalente a
typedef nodo* Ptrpila;

C ++ has the class string for string management ... much safer and cleaner option than char[] :
```
// evita esto
char cad[100];
// y usa esto
std::string cad;
```
C ++ has its own output input library with cin and cout (which you use in some parts of the code):
```
// evita esto
gets(cad);
// y usa esto
std::cin >> cad;
```

C ++ has its own memory management mechanism with new and delete :

// evita esto
t_nodo *nodo = (t_nodo*)malloc(sizeof(t_nodo));
// y usa esto
t_nodo* nodo = new t_nodo;

C ++ allows you to configure the constructors and destructors of each class and structure:

// evita esto
t_nodo *nodo = (t_nodo*)malloc(sizeof(t_nodo));
nodo->datoP =  palabra;
nodo->sgte = pila;
pila = nodo;

//Y usa esto
struct t_nodo
{
  // ...

  t_nodo(char dato, nodo_t* sig)
    : datoP(dato), sgte(sig)
  { }
};
// ...
t_nodo* nodo = new t_nodo(palabra,pila); // new invoca automaticamente el constructor
pila = nodo;

In C ++ the function main() must have mandatory a return type:

// No conforme al estandar
main(){
// Conforme al estandar
int main(){

In C ++, the classes and functions typical of the standard are usually found in the namespace std . Either use using namespace std or add as prefix std:: to each library and class (one more reason why your code does not compile).

And even with all this your program still does not compile:

First the errors:

prog.cc:118:12: error: no matching function for call to 'meterPila'
           meterPila(pila,arbol);
           ^~~~~~~~~

The function has this signature:

void meterPila(t_nodo*&, char);

Then it is clear that at a type char you can not pass a type Nodo* ... you will see how to correct that error.

You should also pay special attention to warnings since they do not say nonsense:

prog.cc:68:18: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if(cad[i]>=48&&cad[i]<=57||cad[i]=='.')
       ~~~~~~~~~~^~~~~~~~~~~~~~


prog.cc:107:18: warning: '&&' within '||' [-Wlogical-op-parentheses]
     if(E>=48&&E<=57||E=='.'){
        ~~~~~^~~~~~~~~

That is, you are combining different operators without using parentheses to group them with what they are going to execute linearly without distinctions ... are you sure that the result will be as expected?

You have a lot to do before analyzing the reason why your program does not work correctly ... in fact it is more correct to say that your program does not compile right now.