Translate

Wednesday, April 1, 2015


Conversion from Infix to Postfix Algorithm (Part 2)


As we saw in the part 1 of this topic what is notations and how to convert from infix to prefix expression, now we will do also the same methodology to discuss the conversion from infix to postfix.

·         Infix notation
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on E.g. A + B

·         Postfix notation
In Postfix notation, the operator comes after the Operand.
For example, the Infix expression A+B will be written as AB+ in its Postfix Notation.
Postfix is also called ‘Reverse Polish Notation’

It provided a straightforward solution for calculator or computer software mathematics because it treats the instructions (operators) and the data (operands) as "objects" and processes them in a last-in, first-out (LIFO) basis. This is called a "stack method". (Think of a stack of plates. The last plate you put on the stack will be the first plate taken off the stack.)

so that the InfixNotation expression (3 + 5) * (7 - 2)
would be written as  * + 3 5 - 7 2
In this notation the above expression would be   3 5 + 7 2 - *

In the first expression, the brackets tell us that we have to add 3 to 5, then subtract 2 from 7, and multiply the two results together.

In Polish Notation, one has to parse the expression recursively to obtain the operands for each operator.
In RPN, the numbers and operators are listed one after another, and an operator always acts on the most recent numbers in the list. The numbers can be thought of as forming a stack, like a pile of plates. The most recent number goes on the top of the stack. An operator takes the appropriate number of arguments from the top of the stack and replaces them by the result of the operation.

      Now let's see in a simple way how infix notation expression (3 + 5) * (7 - 2) 
     would be written as  * + 3 5 - 7 2 ?

      Reading from left to right, this is interpreted as follows:

-       Push 3 onto the stack.
-       Push 5 onto the stack. The stack now contains (3, 5).
-       Apply the + operation: take the top two numbers off the stack, add them together, and put the result back on the stack. The stack now contains just the number 8.
-       Push 7 onto the stack.
-       Push 2 onto the stack. It now contains (8, 7, 2).
-       Apply the - operation: take the top two numbers off the stack, subtract the top one from the one below, and put the result back on the stack. The stack now contains (8, 5).
-       Apply the * operation: take the top two numbers off the stack, multiply them together, and put the result back on the stack. The stack now contains just the number 40.    * + 3 5 - 7 2

Conversion from Infix to Postfix Algorithm

Step1: Scan the Infix expression from left to right for tokens (Operators, Operands & Parentheses) and perform the steps 2 to 5 for each token in the Expression

Step2: If token is operand, Append it in postfix expression

Step3: If token is a left parentheses “(“, push it in stack.

Step4: If token is an operator,
         - Pop all the operators which are of higher or equal precedence then the incoming token and append them (in the same order) to the output Expression.
         - After popping out all such operators, push the new token on stack.

Step5: If “)” right parentheses is found,
         - Pop all the operators from the Stack and append them to Output String, till you encounter the Opening Parenthesis “(“.
         - Pop the left parenthesis but don’t append it to the output string (Postfix notation does not have brackets).

Step6: When all tokens of Infix expression have been scanned. Pop all the elements from the stack and append them to the Output String.
   - The Output string is the Corresponding Postfix Notation.

Example
Let we want to convert this Infix expression :  A * (B + C) – D / E  to Postfix as shown:

Stage      
Input
Postfix_Stack
Stack
Stack is empty and we only have the Infix Expression



The first token is Operand A Operands are Appended to the Output as it is
A
A
Empty
Next token is * Since Stack is empty (top==NULL) it is pushed into the Stack
*
A
*
Next token is ( the precedence of open-parenthesis, when it is to go inside, is maximum. But when another operator is to come on the top of ‘(‘ then its precedence is least.

(
A
*(
Next token, B is an operand which will go to the Output expression as it is
B
AB
*(
Next token, + is operator, We consider the precedence of top element in the Stack, ‘(‘. The outgoing precedence of open parenthesis is the least (refer point 4. Above). So + gets pushed into the Stack
+
AB
*(+
Next token, C, is appended to the output
C
ABC
*(+
Next token ), means that pop all the elements from Stack and append them to the output expression till we read an opening parenthesis.
)
ABC+
*
Next token, -, is an operator. The precedence of operator on the top of Stack ‘*‘ is more than that of Minus. So we pop multiply and append it to output expression. Then push minus in the Stack.
-
ABC+*
-
Next, Operand ‘D‘ gets appended to the output.
D
ABC+*D
-
Next, we will insert the division operator into the Stack because its precedence is more than that of minus.
/
ABC+*D
-/
The last token, E, is an operand, so we insert it to the output Expression as it is.
E
ABC+*DE
-/
The input Expression is complete now. So we pop the Stack and Append it to the Output Expression as we pop it.
Empty
ABC+*DE/-
Empty


The result is ABC+*DE/-

The next part is the most important one to illustrate how to use these notations in our application and Odoo(OpenERP) for example.

To Be Continued..,
See you in the next parts.

No comments:

Post a Comment