Code:
/* InfixtoPostfix - translate from infix to postfix form
Pre: The input is a valid expression in infix form.
Post: The output is the input expression converted into postfix expression. */
void InfixtoPostfix(Expression expr, Expression postfix)
{
Stack stack;
StackEntry topentry;
Token token, tmp;
KindType type;
CreateStack(&stack);
do {
GetToken(token, expr);
switch (type = Kind(token)){
case OPERAND:
PutToken(token, postfix);
break;
case LEFTPAREN:
Push(token, &stack);
break;
case RIGHTPAREN:
for (Pop(token, &stack); Kind(token) != LEFTPAREN; Pop(token, &stack))
PutToken(token, postfix);
break;
case UNARYOP: /* Treat both kinds together */
case BINARYOP:
do {
if (StackEmpty(&stack))
break;
else {
StackTop(&topentry, &stack);
if(Kind(topentry) == LEFTPAREN)
break;
else if (Priority(topentry) < Priority(token))
break;
else if (Priority(topentry) == Priority(token)
&& Priority(token) == MAXPRIORITY)
break;
else {
Pop(tmp, &stack);
PutToken(tmp, postfix);
}
}
}while (1);
Push(token, &stack);
break;
case ENDEXPR:
while(!StackEmpty(&stack)) {
Pop(token, &stack);
PutToken(token, postfix);
}
break;
}
}while (type != ENDEXPTR);
}