Thread: Infix to Postfix Coding Problem

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    51

    Infix to Postfix Coding Problem

    Code:
    #include<stdio.h>
    #include<string.h>
    #define STACKSIZE 100
    
    typedef int Item_t;
    
    typedef struct {
    	Item_t Items[STACKSIZE];
    	int Top;
    } stack_t;
    
    void Initializes_Stack(stack_t *);
    int EmptyStack(stack_t);
    int FullStack(stack_t);
    void Push(Item_t X, stack_t *);
    void Pop(stack_t *s, Item_t *);
    int is_operand(Item_t);
    int is_operator(Item_t);
    int HigherPrecedence(Item_t, Item_t);
    void Postfix(stack_t *);
    
    void Initializes_Stack(stack_t *s){
    	s->Top =0;
    }
    
    int EmptyStack(stack_t s){
    	return (s.Top == 0);
    }
    
    int FullStack(stack_t s){
    	return (s.Top==STACKSIZE);
    }
    
    void Push(Item_t x, stack_t *s){
    	if(FullStack(*s))
    		printf("\nERROR: Stack overflow!\n");
    	else {
    		s->Items[s->Top]=x;
    		++(s->Top);
    	}
    }
    
    void Pop(stack_t *s, Item_t *x)
    {
    	if(EmptyStack(*s))
    	printf("\nERROR: Empty stack.\n");
    	else {
    		--(s->Top);
    		*x=s->Items[s->Top];
    	}
    }
    
    int is_operand(Item_t data)
    {
       if (((data >= 'a') && (data <= 'z')) ||
          ((data >= 'A') && (data <= 'Z')) ||
          ((data >= '0') && (data <= '9')))
          return 1;
       else
          return 0;
    }
    
    int HigherPrecedence(Item_t OperatorA, Item_t OperatorB)
    {
       if (OperatorA == '(')
          return 0;
       else if (OperatorB == '(')
          return 0;
       else if (OperatorB == ')')
          return 1;
       else if ((OperatorA == '^') && (OperatorB == '^'))
          return 0;
       else if (OperatorA == '^')
          return 1;
       else if (OperatorB == '^')
          return 0;
       else if ((OperatorA == '*') || (OperatorA == '/'))
          return 1;
       else if ((OperatorB == '*') || (OperatorB == '/'))
          return 0;
       else
          return 1;
    }
    
    void Postfix(stack_t *s)
    {
    	Item_t ch,pop;
    
    	ch=getchar();
    
    	if( ch != '\n' )
    	{
    		if(is_operand(ch))
    			putchar(ch);
    		else
    		{
    			while(!EmptyStack(*s)  && HigherPrecedence(s->Items[s->Top], ch)){
    				Pop(s,&pop);
    				if(pop!='(')
    				putchar(pop);
    			}
    
    			if ( (!EmptyStack(*s)) && (ch == ')') )
    				Pop(s,&pop);
    			else
    				Push(ch,s);
    		}
    		Postfix(s);
    	}
    	else
    	{
    		while(!EmptyStack(*s)){
    			Pop(s,&pop);
    			if(pop!=')')
    			putchar(pop);
    		}
    
    	}
    }
    
    int main(void)
    {
    	stack_t s;
    	Item_t in='y';
    	Initializes_Stack(&s);
    	printf("Enter an infix expression:");
    	Postfix(&s);
    	putchar('\n');
    	return 0;
    }
    This program will missed up some expression when there are parentheses... and dunno why it didn't skip '(' or ')' without adding if(pop!=')') and if(pop!='(')...

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    As much as I love to take time out of my busy life to develop test cases for your program, I'm going to have to ask for a few examples of input that fails to parse correctly and the output you were expecting.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    51
    Failed Sample 1
    input: a+(b/c)
    output: abc/
    Expected : abc/+

    Failed Sample 2
    input: 1+(a+(b/c)-d)
    output: 1abc/+d-
    Expected: 1abc/+d-+

  4. #4
    Registered User
    Join Date
    Jun 2003
    Posts
    51
    can someone help me to figure out the problem?

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Sure, create it on paper, how the process should work, then turn it into code.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. One more coding problem
    By zrepaer in forum C Programming
    Replies: 1
    Last Post: 04-09-2009, 05:37 PM
  2. Replies: 9
    Last Post: 03-20-2009, 05:22 PM
  3. stack (array impl) problem: postfix notation
    By kocika73 in forum C Programming
    Replies: 2
    Last Post: 04-17-2005, 01:35 PM
  4. Infix to postfix Q
    By Liberty4all in forum C++ Programming
    Replies: 8
    Last Post: 11-03-2002, 08:34 AM
  5. Infix to postfix
    By Liberty4all in forum C Programming
    Replies: 2
    Last Post: 11-01-2002, 08:50 AM