Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

creating infix tree

hi,

i am working on creating infix tree for the given expression
i want to have same function which works for
both paranthesized and non paranthesized inputs
my function is working for fully paranthesized inputs
but ot working for non paranthesized please
help how to male my function work for both.

i just need the procedure not the actual code.

thanks in advance.


[code]

#include
#include
#include

#include "BST.h"

#define EMPTY 0

void push_exp(int item);
int pop_exp();
int is_stk_exp_empty();
void push_tree();
BST_t *pop_tree();
int is_stk_tree_empty();

BST_t * infixtree(char* infix);

struct stack_exp
{
int data[MAX];
int top;
};

struct stack_exp ex;

struct stack_tree
{
BST_t *nodes[100];
int top;
};

struct stack_tree tree;

int emptystacks()
{
ex.top =-1;
tree.top =-1;
}

void push_exp(int item)
{
++ex.top;
ex.data[ex.top]=item;
}

int pop_exp()
{
int ret =0;
if(ex.top != -1)
{
ret= ex.data[ex.top];
--ex.top;
}
return ret;
}

int is_stk_exp_empty()
{
if(ex.top == -1)

return 1;
else
return 0;
}

int isoperator(char e)
{
if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%'|| e == '^')

return 1;
else
return 0;
}

BST_t *create_node(int n1)
{
BST_t *newnode;
newnode = (BST_t *)malloc(sizeof(newnode));

newnode->data=n1;
newnode->left=NULL;
newnode->right=NULL;

return newnode;
}
int isoper(char ch)
{
char op;
switch(ch)
{
case '+':
case '-':
case '/':
case '*':
case '^':
op =1;
break;
default:
op=0;
break;
}
return op;
}

BST_t * infixtree(char* infix)
{
char *i,*p;
char n1;
BST_t *temp,*r,*l,*root,*t;
i = &infix[0];
while(*i)
{

// skip spaces
while(*i == ' ' || *i == ' ' && *i != '')
{
i++;
}
push_exp('(');
if( isdigit(*i) || isalpha(*i))
{
while( isdigit(*i) || isalpha(*i))
{
push_exp(*i);
i++;
}
}
if(isoper(*i))
{
push_exp(*i);
}
if( *i == '(' )
{
push_exp(*i);
}

if( *i == ')')
{
while( (n1 = pop_exp()) != '(')
{

if(isoperator(n1))
{
temp = create_node(n1);
t = pop_tree();
if(t)
temp->right = t;
}
else
{
r=create_node(n1);
push_tree(r);
}

}
l=pop_tree();
if(l){
temp->left=l;
root=temp;
push_tree(root);
}
}
i++;
}
return root;
}

void push_tree(BST_t *t)
{
tree.top++;
tree.nodes[tree.top]=(BST_t *)malloc(sizeof(BST_t));
tree.nodes[tree.top]=t;
}


BST_t *pop_tree()
{
if(tree.top > -1 )
return tree.nodes[tree.top--];
else
return NULL;
}

int is_stk_tree_empty()
{
if(tree.top == -1)
return 1;
else
return 0;
}

void inorder(BST_t * root)
{
if(root != NULL )
{
inorder(root->left);
printf("%c", root->data);
inorder(root->right);
}
}


int main()
{
char in1[70],in2[70],post[50],ch;
BST_t * root1, *root2;root1=root2=NULL;
int i=0;
printf(" Exp: "( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g) )"
");
strcpy(in1," ( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g) )");
emptystacks();
root1 = infixtree(in1);
inorder(root1);
printf("
");
printf("Exp : "a + b * c ^ d / ( e + f ) * g"
");
strcpy(in2,"a + b * c ^ d / ( e + f ) * g");
emptystacks();
root2 = infixtree(in2);
inorder(root2);
return 0;
}
[/code]
Sign In or Register to comment.