1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

"Infix-Postfix" & "Postfix-Infix" codes problem

Discussion in 'C' started by SHENGTON, Oct 11, 2008.

  1. SHENGTON

    SHENGTON New Member

    Joined:
    Oct 10, 2008
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Good day Go4Expert experts.

    This is my first post here and hope you can help me with my problem. I'm a noob with Borand C++.

    I see a tutorial here "Converting and Evaluating Infix, Postfix and Prefix Expressions in C". I copied the code and run it in my Borland C++ program.

    Problem with "Infix to Postfix"
    Here's what I get if I run the code:

    [​IMG]

    I'll just include the code here:
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    
    #define MAX 10
    #define EMPTY -1
    
    struct stack
    {
    	char data[MAX];
    	int top;
    };
    
    int isempty(struct stack *s)
    {
    	return (s->top == EMPTY) ? 1 : 0;
    }
    
    void emptystack(struct stack* s)
    {
    	s->top=EMPTY;
    }
    
    void push(struct stack* s,int item)
    {
    	if(s->top == (MAX-1))
    	{
    		printf("\nSTACK FULL");
    	}
    	else
    	{
    		++s->top;
    		s->data[s->top]=item;
    	}
    }
    
    char pop(struct stack* s)
    {
    	char ret=(char)EMPTY;
    	if(!isempty(s))
    	{
    		ret= s->data[s->top];
    		--s->top;
    	}
    	return ret;
    }
    
    void display(struct stack s)
    {
    	while(s.top != EMPTY)
    	{
    		printf("\n%d",s.data[s.top]);
    		s.top--;
    	}
    }
    
    int isoperator(char e)
    {
    	if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
    		return 1;
    	else
    		return 0;
    }
    
    
    int priority(char e)
    {
    	int pri = 0;
    
    	if(e == '*' || e == '/' || e =='%')
    		pri = 2;
    	else
    	{
    		if(e == '+' || e == '-')
    			pri = 1;
    	}
    	return pri;
    }
    
    void infix2postfix(char* infix, char * postfix, int insertspace)
    {
    	char *i,*p;
    	struct stack X;
    	char n1;
    	emptystack(&X);
    	i = &infix[0];
    	p = &postfix[0];
    
    	while(*i)
    	{
    		while(*i == ' ' || *i == '\t')
    		{
    			i++;
    		}
    
    		if( isdigit(*i) || isalpha(*i) )
    		{
    			while( isdigit(*i) || isalpha(*i))
    			{
    				*p = *i;
    				p++;
    				i++;
    			}
    			/*SPACE CODE*/
    			if(insertspace)
    			{
    				*p = ' ';
    				p++;
    			}
    			/*END SPACE CODE*/
    		}
    
    		if( *i == '(' )
    		{
    			push(&X,*i);
    			i++;
    		}
    
    		if( *i == ')')
    		{
    			n1 = pop(&X);
    			while( n1 != '(' )
    			{
    				*p = n1;
    				p++;
    				/*SPACE CODE*/
    				if(insertspace)
    				{
    					*p = ' ';
    					p++;
    				}
    				/*END SPACE CODE*/
    				n1 = pop(&X);
    			}
    			i++;
    		}
    
    		if( isoperator(*i) )
    		{
    			if(isempty(&X))
    				push(&X,*i);
    			else
    			{
    				n1 = pop(&X);
    				while(priority(n1) >= priority(*i))
    				{
    					*p = n1;
    					p++;
    					/*SPACE CODE*/
    					if(insertspace)
    					{
    						*p = ' ';
    						p++;
    					}
    					/*END SPACE CODE*/
    					n1 = pop(&X);
    				}
    				push(&X,n1);
    				push(&X,*i);
    			}
    			i++;
    		}
    	}
    	while(!isempty(&X))
    	{
    		n1 = pop(&X);
    		*p = n1;
    		p++;
    		/*SPACE CODE*/
    		if(insertspace)
    		{
    			*p = ' ';
    			p++;
    		}
    		/*END SPACE CODE*/
    	}
    	*p = '\0';
    }
    
    int main()
    {
    	char in[50],post[50];
    
    	strcpy(&post[0],"");
    	printf("Enter Infix Expression : ");
    	fflush(stdin);
    	gets(in);
    	infix2postfix(&in[0],&post[0],1);
    	printf("Postfix Expression is : %s\n",&post[0]);
    
    	return 0;
    }
    /* SAMPLE OUTPUT:
    Enter Infix Expression : A + B + C / (E - F)
    Postfix Expression is : A B + C E F - / +  
    */
    

    Problem with "Postfix to Infix"
    Here's the code of Postfix to Infix conversion:
    Code:
    /* include necessary preprocessor header files */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    /* constants */
    #define TRUE 1
    #define FALSE 0
    
    /* structure for stack */
    typedef struct
    {
    char data[20]; /* array to hold stack contents */
    int tos; /* top of the stack pointer */
    } STACK;
    
    
    /* function prototypes */
    void initStack(STACK *stack);
    void get_postfix(char infix[]);
    void convertToinfix(char postfix[], char infix[]);
    int isOperator(char c);
    int precedence(char operator1, char operator2);
    int pred_level(char ch);
    void push(STACK *stack, char value);
    char pop(STACK *stack);
    char stackTop(STACK *stack);
    int isEmpty(STACK *stack);
    int isFull(STACK *stack);
    void printResult(char postfix[], char infix[]);
    void print_msg(void);
    
    
    int main(void)
    {
    char postfix[20], infix[20] ="";
    //float result;
    
    /* convert from infix to postfix main function */
    convertToinfix(postfix, infix);
    
    /* display the infix equivalent */
    infix[strlen(postfix)-2] = '\0';
    printResult(postfix, infix /*, result*/);
    
    return EXIT_SUCCESS;
    }
    
    void initStack(STACK *stack)
    {
    stack->tos = -1; /* stack is initially empty */
    }
    
    
    void get_postfix(char postfix[])
    {
    int i;
    
    printf("Enter postfix expression below (max 18 characters excluding spaces) : \n");
    fflush(stdin);
    /* to read in only 18 characters excluding spaces */
    for ( i=0; i<18; )
    {
    if ( (postfix[i] = getchar()) == '\n' )
    {
    i++;
    break;
    }
    else if ( !(isspace(postfix[i])) )
    i++;
    }
    
    postfix[i] = '\0';
    }
    
    void convertToinfix(char postfix[], char infix[])
    {
    int i, length;
    int j=0;
    char tos_ch;
    STACK stack;
    
    initStack(&stack); /* initialise stack */
    get_postfix(postfix); /* get postfix expression from user */
    length = strlen(postfix);
    
    /* if strlen if postfix is more than zero */
    if ( length )
    {
    push(&stack, '(');
    strcat(postfix, ")");
    length++;
    
    for ( i=0; i<length; i++ )
    {
    /* if current operator in postfix is digit */
    if ( isdigit(postfix[i]) )
    {
    infix[j++] = postfix[i];
    }
    /* if current operator in postfix is left parenthesis */
    else if ( postfix[i] == '(' )
    {
    push(&stack, '(');
    }
    /* if current operator in postfix is operator */
    else if ( isOperator(postfix[i]) )
    {
    while ( TRUE )
    {
    /* get tos */
    tos_ch = stackTop(&stack);
    
    /* no stack left */
    if ( tos_ch == '\0' )
    {
    printf("\nInvalid postfix expression\n");
    print_msg();
    exit(1);
    }
    else
    {
    if ( isOperator(tos_ch) )
    {
    if ( pred_level(tos_ch) >= pred_level(postfix[i]) )
    infix[j++] = pop(&stack);
    else
    break;
    }
    else
    break;
    }
    }
    push(&stack, postfix[i]);
    }
    /* if current operator in postfix is right parenthesis */
    else if ( postfix[i] == ')' )
    {
    while ( TRUE )
    {
    /* get tos */
    tos_ch = stackTop(&stack);
    
    /* no stack left */
    if ( tos_ch == '\0' )
    {
    printf("\nInvalid postfix expression\n");
    print_msg();
    exit(1);
    }
    else
    {
    if ( tos_ch != '(' )
    {
    infix[j++] = tos_ch;
    pop(&stack);
    }
    else
    {
    pop(&stack);
    break;
    }
    }
    }
    continue;
    }
    }
    }
    
    infix[j] = '\0';
    }
    
    
    /* determine if c is an operator */
    int isOperator(char c)
    {
    if ( c == '+' || c == '-' || c == '*' ||
    c == '/' || c == '%' || c == '^' )
    {
    return TRUE;
    }
    else
    return FALSE;
    }
    
    /* determine precedence level */
    int pred_level(char ch)
    {
    if ( ch == '+' || ch == '-' )
    return 1;
    else if ( ch == '^' )
    return 3;
    else
    return 2;
    }
    
    /* determine if the precedence of operator1 is less than,
    equal to, greater than the precedence of operator2 */
    int precedence(char operator1, char operator2)
    {
    if ( pred_level(operator1) > pred_level(operator2) )
    return 1;
    else if ( pred_level(operator1) < pred_level(operator2) )
    return -1;
    else
    return 0;
    }
    
    /* push a value on the stack */
    void push(STACK *stack, char value)
    {
    if ( !(isFull(stack)) )
    {
    (stack->tos)++;
    stack->data[stack->tos] = value;
    }
    }
    
    /* pop a value off the stack */
    char pop(STACK *stack)
    {
    char ch;
    
    if ( !(isEmpty(stack)) )
    {
    ch = stack->data[stack->tos];
    (stack->tos)--;
    return ch;
    }
    else
    return '\0';
    }
    
    /* return the top value of the stack without popping the stack */
    char stackTop(STACK *stack)
    {
    if ( !(isEmpty(stack)) )
    return stack->data[stack->tos];
    else
    return '\0';
    }
    
    /* determine if stack is empty */
    int isEmpty(STACK *stack)
    {
    /* empty */
    if ( stack->tos == -1 )
    return TRUE;
    /* not empty */
    else
    return FALSE;
    }
    
    /* determine if stack is full */
    int isFull(STACK *stack)
    {
    /* full */
    if ( stack->tos == 19 )
    return TRUE;
    /* not full */
    else
    return FALSE;
    }
    
    
    /* display the result postfix expression */
    void printResult(char postfix[], char infix[]/*, float result*/)
    {
    /*system("cls");*/
    printf("\n\n");
    printf("Postfix notation: %s\n\n", postfix);
    printf("Infix notation : %s\n", infix);
    //printf("Result is: %f\n", result);
    print_msg();
    }
    
    /* print exit message */
    void print_msg(void)
    {
    printf("Hit <RETURN> to exit......");
    fflush(stdin);
    getchar();
    }
    When I run this code this what I get:
    [​IMG]

    When I press enter this is the result:
    [​IMG]

    What's wrong with the code?

    I'm just a beginner with Borland C++. Hope you can help me with this Gurus.

    Thanks and God bless. :)
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
  3. SHENGTON

    SHENGTON New Member

    Joined:
    Oct 10, 2008
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for your code Sir shabbir. It really helps. However, how about the Infix to Postfix above? What's wrong with the code?

    I'm just a beginner Sir, hope you can help me.

    Thanks and God bless. :)
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    Thats pretty simple code where you just arrange the postfix expression in binary tree and Inorder traversal gives you infix expression. I don't have the ready code as of now but I guess it would not be that difficult to write as well for you if you have the concept and one part of it
     
  5. SHENGTON

    SHENGTON New Member

    Joined:
    Oct 10, 2008
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Thanks Sir.
     

Share This Page