INFIX To POSTFIX Conversion *************************** Given: a queue called INFIX that holds the input tokens Uses: a stack called OPSTACK that holds operators during the processing Output: a queue called POSTFIX that holds the resultant postfix expression The algorithm: ************** PUSH(OPSTACK,EndToken) while not ISEMPTY(INFIX) { DEQUEUE(INFIX, NewToken) case 1. If NewToken is an operand then ENQUEUE(POSTFIX, NewToken) case 2. If NewToken is ")" then { POP(OPSTACK,OP) while OP is not "(" { ENQUEUE(POSTFIX, OP) POP(OPSTACK, OP) } } case 3. If NewToken == EndToken then while not ISEMPTY(OPSTACK) { POP(OPSTACK, OP) ENQUEUE(POSTFIX, OP) } case 4. /* NewToken is an operator */ while (StackPriority(ONTOP(OPSTACK)) >= InfixPriority(NewToken) { POP(OPSTACK, OP) ENQUEUE(POSTFIX, OP) } PUSH(OPSTACK, NewToken) } InfixPriority * / + - ( ) # 2 2 1 1 3 0 0 StackPriority * / + - ( ) # 2 2 1 1 0 - 0