Algorithms and Me: Stacks : Infix to postfix conversion

Key Point: Using Stack
Java code from http://people.cs.clemson.edu/~turner/courses/cs102/spring98/section2/assignments/asg4/InfixToPostfix.java

int is_operand(char op){ 

if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')

return 1;  

return 0;

}



/* This function returns associated precedence to an operator */

int precedence(char op){ 

switch (op){   

case '+' : 

case '-' :

return 1; 

case '/' : 

case '*' : 

return 2;     

case '%' :    

return 3; 

default : 

return 4;  

}

}

/* This function tell if the op1 has lower precedence than op2 */

int lower_precedence(char op1, char op2){

if(precedence (op1) < precedence(op2)) 

return 1; 

return 0;

}

void infix_to_postfix(cahr *s){

stack ms;

char *post  = p;

char temp;

/* Wrong input */

if(s== NULL) return ;

if(*s == '\0') return ;

/* Case 1. If '(', push on to stack */

if(*s == '('){

push(&ms, *s);

}

/* Case 2. If ')', pop all op from stack till we see ')', Discard ')' */

else if(*s == ')'){

while(!is_empty(ms) && peek(ms) != '('){

*p  = pop(&ms);

p++;

}

if(!is_empty(ms))

pop(&ms);

}

/* Case 3. If it is operator, pop all op on stack which are of higher 

  precedence than it. Push this onto stack */

else if(is_operand(*s)){

while(!is_empty(ms) && (!lower_precedence(peek(ms), *s))){

*p  = pop(&ms);

p++;

}

push(&ms, *s);

}

/* Case 4. If it neither of above, add it to postfix expression */

else{

*p = *s;

p++;

}

s++;

}

/*Flush all ops from stack once infix is completely visited */

while(!is_empty(ms)){

*p  = pop(&ms);

p++;

}

printf("\nPostfix expression is : ");

printf("%s\n" , post);

}

Read full article from Algorithms and Me: Stacks : Infix to postfix conversion