infix expression tree

Question

Gaiety 1 Junior Poster

15 Years Ago

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.

thanks in advance

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

c

2 Contributors
3 Replies
277 Views
1 Day Discussion Span
Latest Post 15 Years Ago Latest Post by dkalita

dkalita 110 Posting Pro in Training

15 Years Ago

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.

This should solve your problem.

Edited 15 Years Ago by dkalita because: n/a

Reply to this topic

Be a part of the DaniWeb community

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

Gaiety 1 Junior Poster · Answer 1 · 2009-10-07T10:23:52+00:00

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.
This should solve your problem.

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];
        push_exp('('); // added code here
        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;
}

dkalita 110 Posting Pro in Training · Answer 2 · 2009-10-07T12:24:58+00:00

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......