Hi ,
finally i managed to write code for infix tree generation.
but when i am getting segementation fault .
when i debug the code its entering infinite loop.
please review my code and kindly let me know wheres the problem.
i am passing a file through command line and the contents of the file are
( a + ( ( b * c ) / ( d * e ) ) )
ofcourse the below header file contains macros and other function protos , those are used in other files.
just for clarity i have added here, please consider only contents that are usefull for infixtree() function.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
//#include "BST.h"
#ifndef __BSTREE__
#define __BSTREE__
typedef struct Bin_Srch_Tree BST_t;
struct Bin_Srch_Tree
{
BST_t *left;
int data;
BST_t *right;
};
extern BST_t *nodes[20];
#define Node_Inserted_Successfully 1
#define Node_Creation_Failed 2
#define Duplication_Not_Allowed 3
#define MAX 20
BST_t *create_node(int );
int insert(BST_t **, int );
void inorder(BST_t *);
void preorder(BST_t *);
void postorder(BST_t *);
extern int top, b;
int empty();
void push(BST_t **, BST_t *);
BST_t* pop(BST_t **);
#endif
#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 == '\t' && *i != '\0')
{
i++;
}
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 preorder(BST_t * root)
{
if(root != NULL )
{
printf("%c", root->data);
preorder(root->left);
preorder(root->right);
}
}
int main(int argc, char *argv[])
{
char in[70],post[50],ch;
BST_t * root=NULL;
int i=0;
FILE *fp;
fp=fopen(argv[1],"r");
if(fp)
{
while((ch=fgetc(fp))!=EOF)
in[i++]=ch;
in[i]='\0';
emptystacks();
root = infixtree(in);
preorder(root);
}
else
printf("no such file\n");
fclose(fp);
return 0;
}