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