Arbol Binario!!!

janiopc
12 de Marzo del 2008
Hola... necesito por FAVOR..
Un programa en C++ que dado un fichero donde aparece una expresión algebraica escrita en pre orden y luego en in orden, calcule el valor final de dicha expresión.

Obs: Hay que Implementar a través de pilas y árboles. Asuma que las cifras numéricas son de un solo dígito

Rex
12 de Marzo del 2008
*Expression tree: Creation, Conversion and Evaluation.*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<math.h>
#include<string.h>
#include<iostream.h>

#define MAX 50

struct node
{
struct node* left_child;
char x;
struct node* right_child;
} * stack[50];
int top = -1;

struct node* CreateExpTreePostfix(char*);
struct node* CreateExpTreePrefix(char*);

void preorder(struct node* sr);
void inorder(struct node* sr);
void postorder(struct node* sr);

int Evaluate(struct node* sr);

void push(struct node**, struct node*);
struct node* pop(struct node**);

void Delete_Tree(struct node*);

main()
{
struct node* root;
char str[50];
int z;
char ch;

clrscr();
printf("Input expression is:\n1)Prefix\n2)Postfix ");
ch=getche();
if(ch==\'1\')
{
printf("\nEnter Prefix Expression:");
gets(str);
root = CreateExpTreePrefix(str);
}
else
{
printf("\nEnter Postfix Expression:");
gets(str);
root = CreateExpTreePostfix(str);
}

printf("\nPrefix Exp. :");
preorder(root);
printf("\nInfix Exp. :");
inorder(root);
printf("\nPostfix Exp. :");
postorder(root);

z=Evaluate(root);
printf("\nExpression Evaluated to: %d", z);

Delete_Tree(root);

getch();

}
struct node* CreateExpTreePostfix(char* str)
{
struct node* nleft, * nright, * nodeptr;
while (*str)
{
nodeptr = (struct node *) malloc(sizeof(struct node));
nodeptr->x = *str;
if (*str == \'+\' || *str == \'-\' || *str == \'/\' ||
*str == \'*\' || *str == \'^\')
{
nright = pop(stack);
nleft = pop(stack);

nodeptr->left_child = nleft;
nodeptr->right_child = nright;
}
else
{
nodeptr->left_child = NULL;
nodeptr->right_child = NULL;
}
push(stack, nodeptr);
str++;
}

return pop(stack);
}

struct node* CreateExpTreePrefix(char* str)
{
struct node* nleft, * nright, * nodeptr;
strrev(str);
while (*str)
{
nodeptr = (struct node *) malloc(sizeof(struct node));
nodeptr->x=*str;

if (*str == \'+\' || *str == \'-\' || *str == \'/\' || *str
== \'*\' || *str == \'^\')
{
nleft = pop(stack);
nright = pop(stack);

nodeptr->left_child = nleft;
nodeptr->right_child = nright;

}
else
{
nodeptr->left_child = NULL;
nodeptr->right_child = NULL;
}
push(stack, nodeptr);
str++;
}
return pop(stack);
}

void inorder(struct node* sr)
{
if (sr != NULL)
{
inorder(sr -> left_child) ;

/* print the data of the node whose left child is NULL or the path
has already been traversed */
printf("%c", sr ->x) ;

inorder(sr -> right_child) ;
}
}


void preorder(struct node* sr)
{
if (sr != NULL)
{
/* print the data of a node */
printf("%c", sr -> x) ;
/* traverse till left child is not NULL */
preorder(sr -> left_child) ;
/* traverse till right child is not NULL */
preorder(sr -> right_child) ;
}
}



void postorder(struct node* sr)
{
if (sr != NULL)
{
postorder(sr -> left_child) ;
postorder(sr -> right_child) ;
printf("%c", sr -> x) ;
}
}


void push(struct node** stack, struct node* ptr)
{
if (top == MAX - 1)
printf("\nStack is full.\n") ;
else
{
top++ ;
stack[top] = ptr ;
}
}

/* pops an operator from the stack */
struct node* pop(struct node** stack)
{
if (top == -1)
{
printf("Stack is empty\n") ;
return 0 ;
}
else
{
struct node* ptr = stack[top] ;
top-- ;
return ptr ;
}
}


int Evaluate(struct node* sr)
{
int x,y,z;
if (sr != NULL)
{
if ( sr->x == \'+\' || sr->x == \'-\' || sr->x == \'/\' || sr->x == \'*\' || sr->x == \'^\' )
{
x = Evaluate(sr -> left_child) ;
y = Evaluate(sr -> right_child) ;

switch(sr->x)
{
case \'+\' : z=x+y; break;
case \'-\' : z=x-y; break;
case \'*\' : z=x*y; break;
case \'/\' : z=x/y; break;
case \'^\' : z=pow(x,y); break;

}
return z;
}
return (sr -> x - 48) ;
}
}
void Delete_Tree(struct node * root)
{
if(root!=NULL)
{
Delete_Tree(root->left_child);
Delete_Tree(root->right_child);
free(root);
}
}