Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- using namespace std;
- struct nodo{ // representado en memoria (moviendose teoricamente de a 16 bytes)
- int isOperation;
- int n;
- nodo *der;
- nodo *izq;
- };
- void postorder(nodo *x){ //DFS
- if( !x->isOperation ){
- cout << x->n;
- return;
- }
- cout << "(";
- postorder(x->izq);
- cout << ' ';
- postorder(x->der);
- cout << ' ' << char(x->n);
- cout << ")";
- }
- int order(nodo *x){ //resultado
- if( !x->isOperation ) return x->n;
- switch(x->n){
- case '/': return order(x->izq) / order(x->der); break;
- case '+': return order(x->izq) + order(x->der); break;
- case '-': return order(x->izq) - order(x->der); break;
- case '*': return order(x->izq) * order(x->der); break;
- }
- }
- int main()
- {
- char input[100]; //pedir el espacio .space 100
- stack<nodo*> S; //en teoría ya tenemos la pila
- cin.getline(input, 100); //leer el string
- int total; //buscate 1 registro para guardar esto
- nodo *p, *left, *right; //el nodo esta en memoria, el stack guarda punteros a esos lugares
- for(int i=0; input[i]; i++){
- if( input[i]>='0' && input[i]<='9' ){
- total = 0;
- while(input[i] && input[i]!=' '){ //leer numeritos de string
- total *= 10;
- total += input[i++]-'0';
- }
- p = new nodo; // pedir lugar en memoria
- p->isOperation = 0; //esto es basicamente ir guardando en el stack
- p->n = total;
- p->der = NULL;
- p->izq = NULL;
- S.push(p); //moverme 4 bytes (en teoria)
- }
- else if( input[i]!=' ' ){ //es una operacion
- p = new nodo;
- p->isOperation = 1;
- p->n = input[i]; // ver valor ascii de operaciones
- p->der = NULL;
- p->izq = NULL;
- S.push(p);
- }
- if( S.size() == 3 ){ // hay 3 cosas en el stack (me movi 12 bytes teoricamente)
- p = S.top(); //hay que organizar como copiar c/ cosa
- S.pop(); //volver sp
- right = S.top();
- S.pop();
- left = S.top();
- S.pop();
- p->der = right;
- p->izq = left;
- S.push(p);
- }
- }
- /** Termina el for -> queda el arbol hecho
- en el primer lugar del stack (asumiendo input correcto) **/
- cout << "post order: "; postorder( S.top() ); //mostrar en notacion polaca inversa
- cout << endl << "resultado: " << order( S.top() ); //calcular en orden normal
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement