#include <stdlib.h>
struct stack {
   char data;
   struct stack *next;
};
typedef struct stack s_list;
typedef s_list *link;
link operator  = NULL;

void push(char value) {
   link node;
   node = ( link ) malloc(sizeof(s_list));
   if (!node ) { printf(" overflow !!!\n"); }
   node->data = value; node->next = operator; operator = node;
}

int pop() {
   link top; char value;
   if ( operator != NULL )  {
      top = operator;    operator = operator->next;
      value = top->data; free(top);
   }
   else value = -1;
   return value;
}

int empty(link stack) {
   if (stack == NULL) return 1;  else  return 0;
}

int isoperator(char op) {
   switch ( op ) {
      case '(':
      case ')':
      case '+':
      case '-':
      case '*':
      case '^':
      case '/': return 1;
      default:  return 0;
   }
}

int prior(char op)
{
   switch ( op ) {
      case '^': return 3;
      case '*':
      case '/': return 2;
      case '+':
      case '-': return 1;
      default:  return 0;
   }
}

void main()
{
   char exp[100],postfix[100],cc;
   int  res=0, pos=0, fir=0;

   printf("input expression ==> "); gets(exp);
   while ( exp[pos] != '\0' && exp[pos] != '\n' ) {
    if (isoperator(exp[pos])) { /* '+ - * /' */
      fir=1;
      if (exp[pos] == '(') push('(');
      else
       if (exp[pos] == ')') {
	 while (!empty(operator) && (cc=pop()) != '(') {
	   postfix[res++]=' '; postfix[res++]=cc;
	 }
       }
       else {
	 if (!empty(operator))
       while (prior(exp[pos]) <= prior(operator->data) && !empty(operator)) {
	    postfix[res++]=' '; postfix[res++]= pop();
	 }
	 push(exp[pos]);
       }
    }
    else {
      if (fir == 1) { postfix[res++]=' '; fir=0; }
      postfix[res++] = exp[pos];
    }
    pos++;
   }
   while (!empty(operator)) {
     postfix[res++]=' '; postfix[res++]= pop();
   }
   postfix[res]='\0';
   printf("the infix string --> %s\nthe postfix string --> %s\n",exp,postfix);
}