#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define Arnold  '\0'  /* The Terminator */
#define Blank   ' '
#define Tab     '\t'

#define MaxLen 64

static char
  infix[ MaxLen + 1 ],
  stack[ MaxLen ],
  postfix[ MaxLen + 1 ];

#define Empty (-1)       /* empty stack */
static int top;

/* symbol types */
#define Operator   (-10)
#define Operand    (-20)
#define LeftParen  (-30)
#define RightParen (-40)

static char *symbols = "()+-%*/";

/* symbol precedence */
#define LeftParenPrec 0    /* ( */
#define AddPrec       1    /* + */
#define SubPrec       1    /* - */
#define MultPrec      2    /* * */
#define DivPrec       2    /* / */
#define RemPrec       2    /* % */
#define None        999    /* all else */

void
  read_input( void ),
  infix_to_postfix( void ),
  write_output( void );
void push( char symbol );
char pop( void );
int
  get_type( char symbol ),
  get_prec( char symbol ),
  whitespace_p( char symbol );
void full_stack( void );
void empty_stack( void );

main()
{
  char ans[ 2 ];

  do {
    /*
     * Read an infix string from stdin,
     * convert it to postfix, and write
     * infix and postfix to stdout.
     */
    top = Empty; /* reset stack */
    read_input();
    infix_to_postfix();
    write_output();

    /* Do another? */
    printf( "\n\t\tAnother? (y/n)  " );
    gets( ans );
  } while ( toupper( ans[ 0 ] ) == 'Y' );

  return EXIT_SUCCESS;
}

void infix_to_postfix( void )
{
  int
    i, p,
    len,
    type, precedence;
  char next;

  /* i for infix, p for postfix */
  i = p = 0;
  len = strlen( infix );

  /* Loop through input string. */
  while ( i < len ) {

    /* Ignore whitespace in infix expression. */
    if ( !whitespace_p( infix[ i ] ) ) {
      type = get_type( infix[ i ] );

      switch ( type ) {

      /* Push left paren onto stack. */
      case LeftParen:
        push( infix[ i ] );
        break;

      /* Pop stack until matching left paren. */
      case RightParen:
        while ( ( next = pop() ) != '(' )
          postfix[ p++ ] = next;
        break;

      /* Transfer operand to postfix string. */
      case Operand:
        postfix[ p++ ] = infix[ i ];
        break;

      /*
       * Pop stack until first operator of higher
       * precedence and then stack this operator.
       */
      case Operator:
        precedence = get_prec( infix[ i ] );

        /* Anything on stack to pop? */
        while ( top > Empty &&
                precedence <= get_prec( stack[ top ] ) )
          postfix[ p++ ] = pop();

        push( infix[ i ] );
        break;
      }
    }

    i++;  /* next symbol in infix expression */
  }

  /* Pop any remaining operators. */
  while ( top > Empty )
    postfix[ p++ ] = pop();

  postfix[ p ] = Arnold;    /* ensure a string */
}

int get_type( char symbol )
{
  switch ( symbol ) {

  case '(':
    return LeftParen;

  case ')':
    return RightParen;

  case '+':
  case '-':
  case '%':
  case '*':
  case '/':
    return Operator;

  default:
    return Operand;
  }
}

int get_prec( char symbol )
{
  switch ( symbol ) {

  case '+':
    return AddPrec;

  case '-':
    return SubPrec;

  case '*':
    return MultPrec;

  case '/':
    return DivPrec;

  case '%':
    return RemPrec;

  case '(':
    return LeftParenPrec;

  default:
    return None;
  }
}

int whitespace_p( char symbol )
{
  return symbol == Blank  ||
     symbol == Tab    ||
     symbol == Arnold;
}

void push( char symbol )
{
  /*
   * For program robustness,
   * check for overflow.
   */
  if ( top > MaxLen )
    full_stack();
  else
    stack[ ++top ] = symbol;
}

char pop( void )
{
  /*
   * For program robustness,
   * check for underflow.
   */
  if ( top <= Empty )
    empty_stack();
  else
    return stack[ top-- ];
}

/* Exit in case of overflow. */
void full_stack( void )
{
  printf( "\n\n\t\tFull stack...exiting.\n\n" );
  exit( EXIT_SUCCESS );
}

/* Exit in case of underflow. */
void empty_stack( void )
{
  printf( "\n\n\t\tEmpty stack...exiting.\n\n" );
  exit( EXIT_SUCCESS );
}

void read_input( void )
{
  printf( "\n\n\tInfix (up to %d chars): ", MaxLen );
  gets( infix );
}

void write_output( void )
{
  printf( "\n\tInfix:   %s\n", infix );
  printf( "\tPostfix: %s\n", postfix );
}