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

We had to do this in the second year. Forgot how though, sorry.

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

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';
}

---

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

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.

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

Good searching skills, but your post is not worthy enough to resurrect this thread and keep it alive. Start your own.

*thread closed*