Postfix Evaluation Infix Expression : Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression. Postfix Expression : The Postfix(Postorder) form of the above expression is "23*45/-". Postfix Evaluation : In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows : Scan the Postfix string from left to right. Initialise an empty stack. If the scannned character is an operand, add it to the stack. If the scanned character is an operator, there will be atleast two operands in the stack. If the scanned character is an Operator, then we store the top most element of the stack(topStack) in a variable temp. Pop the stack. Now evaluate topStack(Operator)temp. Let the result of this operation be retVal. Pop the stack and Push retVal into the stack. Repeat this step till all the characters are scanned. After all characters are scanned, we will have only one element in the stack. Return topStack. Example : Let us see how the above algorithm will be imlemented using an example. Postfix String : 123*+4- Initially the Stack is empty. Now, the first three characters scanned are 1,2 and 3, which are operands. Thus they will be pushed into the stack in that order. Stack Expression Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped. Stack Expression The value of the expression(2*3) that has been evaluated(6) is pushed into the stack. Stack Expression Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped. Stack Expression The value of the expression(1+6) that has been evaluated(7) is pushed into the stack. Stack Expression Next character scanned is "4", which is added to the stack. Stack Expression Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped. Stack Expression The value of the expression(7-4) that has been evaluated(3) is pushed into the stack. Stack Expression Now, since all the characters are scanned, the remaining element in the stack (there will be only one element in the stack) will be returned. End result : Postfix String : 123*+4- Result : 3 © 2002 Premshree Pillai.