Advertisement
juaniisuar

Preorder notation (C) -> assembly

Sep 24th, 2015
350
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3.  
  4. using namespace std;
  5.  
  6. struct nodo{ // representado en memoria (moviendose teoricamente de a 16 bytes)
  7.     int isOperation;
  8.     int n;
  9.     nodo *der;
  10.     nodo *izq;
  11. };
  12.  
  13. void postorder(nodo *x){ //DFS
  14.     if( !x->isOperation ){
  15.         cout << x->n;
  16.         return;
  17.     }
  18.     cout << "(";
  19.     postorder(x->izq);
  20.     cout << ' ';
  21.     postorder(x->der);
  22.     cout << ' ' << char(x->n);
  23.     cout << ")";
  24. }
  25.  
  26. int order(nodo *x){ //resultado
  27.     if( !x->isOperation ) return x->n;
  28.  
  29.     switch(x->n){
  30.         case '/': return order(x->izq) / order(x->der); break;
  31.         case '+': return order(x->izq) + order(x->der); break;
  32.         case '-': return order(x->izq) - order(x->der); break;
  33.         case '*': return order(x->izq) * order(x->der); break;
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.     char input[100]; //pedir el espacio .space 100
  40.     stack<nodo*> S; //en teoría ya tenemos la pila
  41.  
  42.     cin.getline(input, 100); //leer el string
  43.     int total; //buscate 1 registro para guardar esto
  44.  
  45.     nodo *p, *left, *right; //el nodo esta en memoria, el stack guarda punteros a esos lugares
  46.     for(int i=0; input[i]; i++){
  47.         if( input[i]>='0' && input[i]<='9' ){
  48.             total = 0;
  49.             while(input[i] && input[i]!=' '){ //leer numeritos de string
  50.                 total *= 10;
  51.                 total += input[i++]-'0';
  52.             }
  53.             p = new nodo; // pedir lugar en memoria
  54.             p->isOperation = 0; //esto es basicamente ir guardando en el stack
  55.             p->n = total;
  56.             p->der = NULL;
  57.             p->izq = NULL;
  58.             S.push(p); //moverme 4 bytes (en teoria)
  59.         }
  60.         else if( input[i]!=' ' ){ //es una operacion
  61.             p = new nodo;
  62.             p->isOperation = 1;
  63.             p->n = input[i]; // ver valor ascii de operaciones
  64.             p->der = NULL;
  65.             p->izq = NULL;
  66.             S.push(p);
  67.         }
  68.         if( S.size() == 3 ){ // hay 3 cosas en el stack (me movi 12 bytes teoricamente)
  69.             p = S.top(); //hay que organizar como copiar c/ cosa
  70.             S.pop(); //volver sp
  71.             right = S.top();
  72.             S.pop();
  73.             left = S.top();
  74.             S.pop();
  75.             p->der = right;
  76.             p->izq = left;
  77.             S.push(p);
  78.         }
  79.     }
  80.     /** Termina el for -> queda el arbol hecho
  81.         en el primer lugar del stack (asumiendo input correcto) **/
  82.  
  83.     cout << "post order: "; postorder( S.top() ); //mostrar en notacion polaca inversa
  84.     cout << endl << "resultado: " << order( S.top() ); //calcular en orden normal
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement