Postfix Notation

Postfix Notation Postfix notation also called reverse polish notation or RPN places each binary arithmetic operator after its two operands instead of between them. Infix Expression : (9 - 5) + 2 = (9 5 -) + 2 = (9 5-) 2 + =95-2+ Infix Expression : Postfix Notation : 9 - (5 + 2) = 9 - (5 2+) = 9 (5 2+) =952+- : Postfix Notation Why postfix notation? There are two reasons • • There is only one interpretation We do not need parenthesis to disambiguate the grammar. Infix Expression : Any expression in the standard form like "2*3-4/5" is an Infix (or Inorder) expression. Postfix Expression : The Postfix (or Postorder) form of the above expression is "2 3*4 5/-". Postfix Evaluation : In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is a b c*+. The algorithm for the conversion is as follows : ▪ ▪ ▪ Scan the Postfix string from left to right. Initialize an empty stack. If the scanned character is an operand, add it to the stack. If the scanned character is an operator, there will be at least two operands in the stack. ▪ If the scanned character is an Operator, there will be at least two operands in the stack. Apply the Operator to the top two Operands and replace them by the result of the operation. Repeat the previous two steps until all the characters are scanned. After all characters ▪ are scanned, we will have only one element in the stack. Example : Let us see how the above algorithm will be implemented using an example. Postfix String : 1 2 3*+4Initially 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. Expression Stack 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. Expression Stack The value of the expression(2*3) that has been evaluated(6) is pushed into the stack. Expression Stack 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. Expression Stack The value of the expression(1+6) that has been evaluated(7) is pushed into the stack. Expression Stack Next character scanned is "4", which is added to the stack. Expression Stack 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. Expression Stack The value of the expression(7-4) that has been evaluated(3) is pushed into the stack. Expression Stack 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 : 1 2 3*+4Result : 3 A postfix expression is one in which we write the operation after the operands; consider the following examples. Infix Postfix 4+5 45+ 1+2*3 123*+ (4 + 5) * (6 + 7) 45+67+* 1+2+3+4+5+6 123456+++++ invalid 1+ invalid 111+ When a calculation is done on a computer you can do that in different ways. If you have en expression like 1 + 1 * 6 - 4 that is going to be calculated. It can be a little tricky at first. Some may try to parse the expression and find out the operators that has the highest priority, calculate them and later calculate operator with lower priority. But if parentheses and functions are added to the expression it will soon be very complicated to do the calculation. An easier way to calculate it is to convert the expression from infix notation to postfix notation. A expression like 1 + 1 becomes 1 1 + and 4 + ( 6 + 10 ) * 5 becomes 4 6 10 + 5 * +. This may first look very strange but when we need to do some calculations on a computer this is much easier.