ARBOL_POLACA.c

//       EVALUACION DE EXPRESIONES MEDIANTE LA NOTACION POLACA
// Programa: 	EvaluaciOn de expresiones
// Programador J. Rafael RodrIguez Ochoa
//
// CaracterIsticas:
//	en un arbol y posteriormente se evalUa mediante la notaciOn
//	polaca auxiliAndose por una pila para resolverla.
// Manera de ejecutarse:
//              Al correr el programa pedirA el siguiente dato:
//		1.- "Introduzca la expresiOn: "
//		2.- Teclee la expresiOn terminando con enter
//		3.- a lo que el programa contestarA con el valor numErico
//		    equivalente
//
// El programa se probO con la siguiente expresiOn
//
//	(2+3*4/(2-1) +7)
//-------------------------------------------------------------------------

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

void muestra(void);
void crea_polaca(char);
int evalua(void);
void push(int);
int pop(void);
int operacion(char, int, int);

struct polaca
{
	 char dato;
	 struct polaca *sig;
};

struct pila
{
	 int dato;
	 struct pila *sig;
	 struct pila *ant;
};

struct arbol
{
	 char dato;
	 struct arbol *raiz;
	 struct arbol *izq;
	 struct arbol *der;
};

struct polaca *pol;
struct arbol *raiz;
struct pila *stack;

void ver_polaca(struct arbol *r)
{
	 if(r->izq) ver_polaca(r->izq);
	 if(r->der) ver_polaca(r->der);
	 printf("%c",r->dato);
	 crea_polaca(r->dato);
}

struct arbol *crea_nodo(char c)
{
	 struct arbol *hoja;
	 if( c== '(' || c == ')' || c == ' ' ) return NULL;
	 if( !(hoja = (arbol *)malloc(sizeof(struct arbol))) )
		 { printf("No hay memoria suficiente ..."); return NULL; }
	 hoja->dato = c;
	 hoja->izq = hoja->der = hoja->raiz = NULL;
	 return hoja;
}

void inserta_nodo(struct arbol *hoja, int parent, char ant)
{
	 struct arbol *act = raiz;

	 if(!hoja) return;
	 if ( !parent && ant == ')' &&
				(act->dato == '+' || act->dato == '-' ||
				 act->dato == '*' || act->dato == '/') &&
				(hoja->dato == '+' || hoja->dato == '-' ||
				 hoja->dato == '*' || hoja->dato == '/') )
	 {
			hoja->izq = act;
			act->raiz = hoja;
			raiz = hoja;
			return;
	 }
	 if (!raiz) { raiz = hoja; return; }
	 while(act->der) act = act->der;
	 {
			if ( ant != ')')
			{
				 if ( act->raiz &&
						 (act->raiz->dato == '*' || act->raiz->dato == '/') &&
						 (hoja->dato == '+' || hoja->dato == '-') )
				 {
						act = act->raiz;
						hoja->izq = act;
						act->raiz = hoja;
						if(raiz == act) raiz = hoja;
						return;
				 }
				 hoja->raiz = act->raiz;
				 if(raiz == act) raiz = hoja;
				 else hoja->raiz->der = hoja;
				 hoja->izq  = act;
				 act->raiz  = hoja;
				 return;
			}
			else
			{
				 act = act->raiz;
				 hoja->izq = act;
				 act->raiz = hoja;
				 if(raiz == act) raiz = hoja;
				 return;
			}
	 }
			act->dato == '*' || act->dato == '/')
	 {
			{
				 act->der = hoja;
				 hoja->raiz = act;
				 return;
			}
	 }
}

void crea_arbol(char *expr)
{
	 int parentesis=0;
	 char c_ant= '\0';

	 while(expr[0]!= '\0')
	 {
			if(expr[0] == '(') parentesis++;
			if(expr[0] == ')') parentesis--;
			inserta_nodo( crea_nodo(expr[0]), parentesis, c_ant );
			c_ant = expr[0];
			++expr;
	 }
}

void crea_polaca(char c)
{
	 struct polaca *act=pol,*ant=NULL;
	 while(act)
	 {
		 ant = act;
		 act = act->sig;
	 }
	 if ( !(act = (polaca *)malloc(sizeof(struct polaca))))
	 {
			printf("No hay memoria suficiente...");
			return;
	 }
	 act->dato = c;
	 act->sig = NULL;
	 if(!ant) pol = act;
	 else	ant->sig = act;
}

void main(void)
{
	 pol = NULL;
	 raiz = NULL;
	 stack = NULL;
	 char *expr;
	 int resultado = 0;

	 clrscr();
	 if(!gets(expr)) return;
	 crea_arbol(expr);
	 //ver_arbol();
	 clrscr();
	 ver_polaca(raiz);
	 resultado = evalua();
	 printf("\nResultado= %d",resultado);
	 getch();
}

int evalua(void)
{
	 struct polaca *p=pol;
	 int a, b, c;
	 char *str;

	 if(!pol) return 0;

	 while(p)
	 {
			if(p->dato >= '0' && p->dato <= '9')
				push(p->dato - '0');
			else
			{
				 a = pop(); b = pop();
				 c = operacion(p->dato, a, b);
				 push(c);
			}
			p= p->sig;
	 }
	 return pop();
}

void push(int dato)
{
	 struct pila *pc=stack;
	 if( !(pc = (pila *)malloc(sizeof(struct pila))))
		 { printf("\nNo hay memoria suficiente..."); getch(); return; }
	 if(!stack) { stack = pc; stack->dato = dato; stack->sig = stack->ant = NULL; return; }
	 pc->dato = dato;
	 pc->sig = NULL;
	 pc->ant = stack;
	 stack->sig = pc;
	 stack = pc;
}

void muestra(void)
{
	 struct pila *pc=stack;
	 int k=1;
	 printf("\nInicio de pila:");
	 while(pc)
	 {
			printf("\ndato de pila %d= %d",k,pc->dato);
			pc=pc->ant;
			k++;
	 }
	 printf("\nFin de pila:");
}

int pop(void)
{
	 struct pila *pc=stack;
	 int dato;
	 dato = pc->dato;
	 if(pc->ant) stack = pc->ant;
	 else stack = NULL;
	 free(pc);
	 return dato;
}

int operacion(char opr, int d1, int d2)
{
	 if(opr == '+') { return d1 + d2 ;}
	 if(opr == '-') { return d1 - d2 ;}
	 if(opr == '*') { return d1 * d2 ;}
	 if(opr == '/') { return d1 / d2 ;}
	 return 0;
}