Conversion from Infix to Postfix Algorithm (
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