Hi,

help me in completing my program.

i dont get the logic how to make my program work for both the inputs.

just compile and run will come to know the problem.

this program is to create the infix tree for the given expression.

if the expression is given completely paranthesized then the out put is fine but when there are no paranthesis or some part paranthesized then the out put is wrong.

cant get the idea how to solve.
plz review and help me.

``````#include <stdio.h>
#include <string.h>
#include <ctype.h>

#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 == '\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 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) )\"\n");
strcpy(in1," ( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g) )");
emptystacks();
root1 = infixtree(in1);
inorder(root1);
printf("\n");
printf("Exp : \"a + b * c ^ d / ( e + f ) * g\" \n");
strcpy(in2,"a + b * c ^ d / ( e + f ) * g");
emptystacks();
root2 = infixtree(in2);
inorder(root2);
return 0;
}``````

DO the following at the very begining:

1) push a '(' to the stack.
2) append ')' to the inputted expression string
3) now proceed with your remaining code.

All 3 Replies

DO the following at the very begining:

1) push a '(' to the stack.
2) append ')' to the inputted expression string
3) now proceed with your remaining code.

DO the following at the very begining:

1) push a '(' to the stack.
2) append ')' to the inputted expression string
3) now proceed with your remaining code.

dear dkalita,
I have changed the code as you suggested but no change in the out put.

``````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;
}``````

the main program:

``````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) )\"\n");
strcpy(in1," ( a + ( ( ( ( b * c ) ^ d ) / ( e + f ) ) * g) ))");
// added extra ')' in red color
emptystacks();
root1 = infixtree(in1);
inorder(root1);
printf("\n");
printf("Exp : \"a + b * c ^ d / ( e + f ) * g\" \n");
strcpy(in2,"a + b * c ^ d / ( e + f ) * g)"); // added extra ')' in red
emptystacks();
root2 = infixtree(in2);
inorder(root2);
return 0;
}``````

then there must be some bug with the function

``BST_t * infixtree(char* infix){...}``

do dry run of the code using pen and paper with a small example with '(' and check where it started going wrong......

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.