**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.

- If the scanned character is an Operator, then we store the top most element of the stack(
- 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

## No comments:

## Post a Comment