Thread: Infix to Postfix

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    28

    Infix to Postfix

    Hey guys, I'm having much difficulties with a problem from my C book. The problem asks you to convert an infix notation, such as "1 + 2" to the more computer friendly postfix, "1 2 +". I tried with the algorithm that my book supplied to me but my program keeps crashing. Here's what i have so far:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    #define LENGTH(x) ( sizeof(x) / sizeof(x[0]) )
    
    typedef struct node{
    	char data;
    	struct node *next;
    } Node;
    
    void push( Node **sHead, char value );
    char pop( Node **sHead );
    int isEmpty( Node *head );
    void printS( Node *s );
    char stackTop( Node *s );
    void convertInToPost( Node **sHead, char *infix, char *postfix );
    void strchar( char *str, char c );
    int isOperator( char c );
    int precedence( char op1, char op2 );
    
    int main( void ){
    	Node *head = NULL;
    	char infix[] = "1+2";
    	char postfix[10];
    	postfix[0] = '\0';
    	
    	convertInToPost( &head, infix, postfix );
    	
    	printf( "%s ", postfix );
    	
    	
    
    	return 0;
    	
    } // main
    
    void convertInToPost( Node **sHead, char *infix, char *postfix ){
    	int i;
    	
    	push( sHead, '(' );
    	strncat( infix, ")", 1 );
    	
    	while( !isEmpty( *sHead ) )
    		for( i = 0 ; i < LENGTH( infix ) ; i++ )
    			if( isdigit(infix[i]) )
    				strchar( postfix, infix[i] );
    			else if( infix[i] == '(' )
    				push( sHead, infix[i] );
    			else if( isOperator( infix[i] ) ){
    				if( precedence( stackTop( *sHead ), infix[i] ) >= 0  )
    					strchar( postfix, pop( sHead ) );
    				push( sHead, infix[i] );
    			}else if( infix[i] == ')' ){
    				while( stackTop( sHead ) != '(' )
    					strchar( postfix, pop( sHead ) );
    				pop( sHead );
    			}
    	
    } // convertIntoPost
    
    void strchar( char *str, char c ){
    	
    	while( *str != '\0' )
    		str++;
    	*str = c;
    	*(str + 1 ) = '\0';
    	
    } // strchar
    
    int isOperator( char c ){
    	
    	if( c == '*' || c == '/' || c == '+' || c == '-' )
    		return 1;
    	
    	return 0;
    	
    } // isOperator
    
    int precedence( char op1, char op2 ){
    
    	
    	switch( op1 ){
    		case '*': case '/':
    			if( op2 == '*' || op2 == '/' )
    				return 0;
    			else
    				return 1;	
    		case '+': case '-':
    			if( op2 == '*' || op2 == '/' )
    				return -1;
    			else
    				return 0;
    	
    	}
    	
    	return -10;
    	
    } // precedence
    
    char stackTop( Node *s ){
    	
    	if( !isEmpty( s ) )
    		return s->data;
    	
    	return '\0';
    	
    } // stackTop
    
    void printS( Node *s ){
    	
    	while( !isEmpty( s ) ){
    		printf( "%3c --> ", s->data );
    		s = s->next;		
    	}
    	printf( "NULL\n\n" );
    	
    } // printS
    
    
    void push( Node **sHead, char value ){
    	Node *newNode;
    	
    	newNode = malloc( sizeof( Node ) );
    	
    	if( newNode != NULL ){
    		newNode->data = value;
    		newNode->next = *sHead;
    		*sHead = newNode;	
    	}else
    		printf( "***ERROR*** Could _NOT_ allocate memory for new object!\n" );
    	
    } // push
    
    char pop( Node **sHead ){
    	Node *temp;
    	char value;
    	
    	if( !isEmpty( *sHead ) ){
    		value = (*sHead)->data;
    		temp = *sHead;
    		*sHead = (*sHead)->next;
    		free( temp );
    		return value;		
    	}
    	
    	return '\0';
    	
    } // pop
    
    
    int isEmpty( Node *head ){
    	return head == NULL;
    } // isEmpty
    Thanks for any help guys.

    Dat
    Dat
    http://hoteden.com <-- not an porn site damnit!

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    #define LENGTH(x) ( sizeof(x) / sizeof(x[0]) )
    EVIL!

    Both unnecessary (don't argue, I've been through this) and unreliable.

    For example, it won't work where you use it.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    The places where it is reliable are where it is unnecesary.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>The places where it is reliable are where it is unnecesary.<<
    Not at all. Hard coding array sizes is unnecessary, it's better to let the compiler do the work, imho. Care to provide an example of where you think it's unnecessary?
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Actually I can think of one example where it makes sense:
    Code:
    int array[] = {1, 2, 3, 4, 35, 234, 27, 123, 10};
    No other.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    How many elements are in the array? Answer: 9. LENGTH will work that out for you, so you could use either:

    >foo(array, 9);
    or
    >foo(array, LENGTH(array));

    which do you think is better? Here's a working example:

    Code:
    #include <stdio.h>
    
    #define LENGTH(a) (sizeof((a)) / sizeof ((a[0])))
    
    int main(void)
    {
        int a[] = {1, 2, 3};
        printf ("Length %d\n", LENGTH(a));
        return 0;
    }
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    As I said - one application, and I've used this syntax, what, 2 times in my programming time (~4 years)?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 07:44 AM
  2. Infix, Postfix, Pseudo-Calculator using Stack ADT
    By sangken in forum C Programming
    Replies: 9
    Last Post: 09-08-2006, 08:17 AM
  3. Replies: 4
    Last Post: 03-12-2006, 02:17 PM
  4. Converting from infix to postfix
    By jcramer in forum C Programming
    Replies: 4
    Last Post: 03-27-2004, 09:23 PM
  5. Infix to postfix
    By Liberty4all in forum C Programming
    Replies: 2
    Last Post: 11-01-2002, 08:50 AM