Converting from infix to postfix

This is a discussion on Converting from infix to postfix within the C Programming forums, part of the General Programming Boards category; I'm working on a project that involves converting an infix equation to a postfix, and am having problems. If the ...

  1. #1
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23

    Question Converting from infix to postfix

    I'm working on a project that involves converting an infix equation to a postfix, and am having problems. If the precedence of the top elementof stack is not greater, it seems to work, but if it is, its dropping the last operator (ie doesnt print, and doesnt show up at the pop at end of function).

    Algorithm used:

    1) If is digit, send to postfix string.
    2) If operator:
    a) If stack empty, push
    b) Else, use top to get copy of top stack element, compare to token. If stackVal has higher precedence, pop stack and repeat step 2.
    c) Else push operator.

    Tried using while loop for repeating step 2, only way I could get it to not go in an infinite loop is to add the !isEmpty(&st) to the conditions.

    This is only the part that does the conversion:

    Code:
    static char postfix[BUFLEN]
    static int curTok = 0;
    static int nxtTok = 1;
    
    void intopost(char buffer[])
    {
    
    STACK st;
    
    int i, j, result = 0;
    char temp;
    
    initStack (&st);
    
    curTok = 0;
    nxtTok = 1;
    
    for (i = 0, j = 0; i < strlen(buffer); i++)
        {
    
        if (isdigit(buffer[i]))
          {
           postfix[curTok++] = buffer[i];
           }
        else
           {
            if (isEmpty(&st))
               {
               push(&st, buffer[i]);
               }
            else
               {
               do
               {
    	top(&st, &temp);
               
    	result = preCheck(temp, buffer[i]);
               
                  if (result == 1)
                     {
                     pop(&st, &postfix[curTok++]);
                     top(&st, &temp);
                     printf("TopVal: %c\n", temp);
                     }
                }
    	while ((result != 0) && (!isEmpty(&st)));
    
    	if (result == 0)
    	{
                    push(&st, buffer[i]);
    	}
                 }
             }
        }
    
    
    while(!isEmpty(&st))
       {
       pop(&st, &postfix[curTok++]);
       }
    
    postfix[curTok++] = '\0';
    
    printf("%s\n", postfix);
    
    }
    
    int preCheck(char stackVal, char tokenVal)
        {
    
        int sval = 0, tval = 0;
    
        switch(stackVal)
              {
    	case '(':
    	case ')':
    	   sval = 0;
    	   break;
    
    	case '+':
    	case '-':
    	   sval = 1;
    	   break;
    
    	case '*':
    	case '/':
    	   sval = 2;
         	   break;
               }
    
        switch(tokenVal)
                  {
    	case '(':
    	case ')':
    	   tval = 0;
    	   break;
    
    	case '+':
    	case '-':
    	   tval = 1;
    	   break;
    
    	case '*':
    	case '/':
    	   tval = 2;
    	   break;
                   }
    
        printf("stackVal: %d\n", sval);
        printf("tokenVal: %d\n", tval);
    
         if (sval > tval)
             {
             return(1);
             }
         else
            {
             return(0);
            }
    
    return(0);
    	}
    Last edited by jcramer; 03-24-2004 at 05:04 PM.
    Viva la Tutorial
    What is the meaning of life? 42 of course!

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    What happened to the indentation (its a mess)
    Where is main()
    What input causes it to fall over
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23
    Sorry about that, main() is in another file, all main does is prepare the equation, (parentheses check, removing spaces, removing newlines), then sends the array to the intopost() function.

    Here's the input I've been testing this with:

    3*4+3
    3-4/3
    3+4*3
    3+4/3

    And this is the output:

    34*3
    343/-
    343*+
    343/+
    Viva la Tutorial
    What is the meaning of life? 42 of course!

  4. #4
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23
    *Non-thread bump*

    I get it, the silent treatment (j/k).

    Thanks for the help guys... yah...

    Got it figured out by myself.
    Viva la Tutorial
    What is the meaning of life? 42 of course!

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    It always helps if you can post something which can be run. Without that, it's just a guessing game as to what's wrong.

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, 06:44 AM
  2. converting infix to postfix
    By rainman39393 in forum C++ Programming
    Replies: 1
    Last Post: 10-24-2008, 07:24 AM
  3. Replies: 4
    Last Post: 03-12-2006, 01:17 PM
  4. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM
  5. Converting Infix 2 Postfix
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 01-06-2002, 12:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21