Thread: Expression: Convert infix notation to postfix notation.

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Expression: Convert infix notation to postfix notation.

    Hi,

    Compilers usually convert expressions to postfix notation. If i have an expression 1 + 2, then the postfix notation version would be 1 2 +, and if i have 7 / 4, i will get 7 4 /. I have to write a program to convert infix notation to postfix notation. However i can't get it to work. Pls help me check if there are any logical errors and such. If you want to read the algorithm first, it's below, thnx.

    The algorithm is to have two arrays and a stack. The program should read the expression into char array infix, then create the postfix expression in char array postfix.

    1. First push a left parenthesis onto the stack.
    2. Then append a right parenthesis to the end if infix.
    3. While stack is not empty, read infix from left to right and do
    the following:

    If current character in infix is a digit, copy it to the next element of postfix.

    If current char in infix is left parenthesis, pus it onto the stack.

    If current char in infix is an operator, pop operators ( if any) at top of stack while they have equal or higher precedence than current operator, then insert the popped operators in postfix.
    Push current character in infix onto stack.

    If current character in infix is a right parenthesis, pop operators form the top of stack and insert them in postfix until a left parenthesis is at top of stack. Then pop and discard the left parenthesis from the stack.

    thnx in advance
    Last edited by Nutshell; 02-17-2002 at 12:13 AM.

  2. #2
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    We had to do this in the second year. Forgot how though, sorry.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Here's the basic idea, you can scale it as you wish and use it as a template. Or compare the functionality with your program and test where yours is going awry.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    static char *s;
    static int top;
    
    int main ( int argc, char *argv[] )
    {
      char *a = argv[1];
      int i, n = strlen ( a );
      /* Initialize the stack */
      s = malloc ( n * sizeof *s );
      top = 0;
      for ( i = 0; i < n; i++ ) {
        if ( a[i] == ')' )
          /* Pop a value off the stack and print */
          printf ( "%c", s[--top] );
        if ( a[i] == '+' || a[i] == '*' )
          /* Push the value onto the stack */
          s[top++] = a[i];
        if ( a[i] >= '0' && a[i] <= '9' )
          printf ( "%c ", a[i] );
      }
      printf ( "\n" );
      return EXIT_SUCCESS;
    }
    -Prelude
    My best code is written with the delete key.

  4. #4
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Ok, i understand that posting the whole code is really hard to read. SO i chose the most critical part. It's the actual function to convert form infix notation to postfix notation. BUt there are other functions i wrote used in this function, just assume they're fine and correct right now. Pls hav a look at the following function and see if there are any logic erros and stuff. If you forgot the algorithm, it's in the first thread.

    thnx in advance

    Code:
    void convertToPostfix( char infix[], char postfix[] )
    {
       StackNodePtr topPtr = NULL;
       int arraySize, infixCounter = 0, postfixCounter = 0;
       char popValue;
       int i;
    
       push( &topPtr, '(' );
    
       arraySize = strlen( infix );
    
       infix[ arraySize + 1 ] = ')';
       infix[ arraySize + 2 ] = '\0';
    
       while ( isEmpty( topPtr ) != 1 ) {
    
          if ( isdigit( infix[ infixCounter ] ) ) {
             postfix[ postfixCounter ] = infix[ infixCounter ];
             infixCounter++;
             postfixCounter++;
          }
          else if ( infix[ infixCounter ] == '(' ) {
             push( &topPtr, infix[ infixCounter ] );
             infixCounter++;
          }
          else if ( isOperator( infix[ infixCounter ] ) ) {
             while ( precedence( stackTop( topPtr ), infix[ infixCounter ] ) == 1 ||
                     precedence( stackTop( topPtr ), infix[ infixCounter ] ) == 0 ) {
                popValue = pop( &topPtr );
                postfix[ postfixCounter ] = popValue;
                postfixCounter++;
             }
             push( &topPtr, infix[ infixCounter ] );
             infixCounter++;
          }
          else if ( infix[ infixCounter ] == ')' ) {
             while ( stackTop( topPtr ) != '(' ) {
                popValue = pop( &topPtr );
                postfix[ postfixCounter ] = popValue;
                postfixCounter++;
             }
             pop( &topPtr );
             infixCounter++;
          }
       }
       postfix[ postfixCounter ] = '\0';
    }

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Hey Hey, i think i've got it to work!!!

    However, it has some bugs. Whenever i input things like 1+2 or 4+5....etc, it turned out fine: 1 2 + and 4 5 +. But when i put something like 1+2-3, 4+4-2.....etc, it generate errors and program has to shut down. Pls give a hand. It is very close to getting it work now. Pls.

    it's attached, thnx in advance

  6. #6
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    FINALLY. Finished. Works beautifully. After my 2 days of hard work and fustration. God i swear i hate debugging...

    Heres the code for those who are interested. Tell me what you think of it. I think it's not bad.

  7. #7
    Registered User
    Join Date
    Feb 2010
    Posts
    1
    can you plz write the code of reading the infix and to check if it is valid ( i mean if an expression contains +* it is not vaild and to skip it from converting to postfix ).


    plz i need help

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Good searching skills, but your post is not worthy enough to resurrect this thread and keep it alive. Start your own.

    *thread closed*
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  2. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 09:15 AM
  3. Replies: 4
    Last Post: 03-12-2006, 02:17 PM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. Infix to Postfix
    By dat in forum C Programming
    Replies: 6
    Last Post: 06-16-2003, 08:46 AM