INFIX POSTFIX AND PREFIX
Infix notation:
you already know this form of mathematical expression when the operator comes
between the operands, for instance,
a + b.
In the case of postFix, the operator comes after its operands as a b +. this notation is also called Reverse Polish notation.
POSTFIX or REVERSE POLISH notation
suppose you got an expression like 7-8+(8+8*(7*4)).
And you wanna implement a method or function that returns its result.
If you try to attempt it with infix notation(as the expression is given), then simply it will be a headache for you how will you know the order of operations. it's a hard way.
But there is an easy way of doing this work by converting input exp to
postFix as 7 8 - 8 8 7 4 * * + + (don't think, how we got this, you'll know just stick with this post).
Now it is easy to know the order of operations as you go from left to right.
Going from left to right you will get your first operator "-" with two operands 7 and 8 respectively.
So the first operation that should be performed is 7-8.
Further, we update the subpart of this expression with the result -1.
as -1 8 8 7 4 * * + +
Similarly, you just have to find the next operator as you got it, look backwards for its operands.
I have given all the steps below
at the first step, we encountered an - sign with its operands 7 and 8.
Replace this sub postfix exp with its result.
how to convert from INFIX to POSTFIX.
Conversion from infix to postfix could be easy for you. If you know the BODMAS rule.
basically, it tells which operator has higher priority than others.
Let's take an example if we have 3 + 8 * ( 10 / 5 ) then the order of operation will be like division => multiplication => addition.
postfix notation for this expression will something like 3 8 10 5 / * + .
With the above example, you actually saw the priority of operators, means operators with higher priority comes first in postfix. see the priority table.
|
priority from low to high |
operators |
| 1 | +,-(equal) |
| 2 | /,*(equal) |
| 3 | ^ |
higher priority.
Just go from left to right in infix 3 + 8 * ( 10 / 5 ), save your operands in postfix one by one as you get them. you'll also get operators, put them on a stack only if the operator on top of the stack having a lower priority than this or stack is empty.
If the priority of the current operator is less or equal than that of the stack top operator then you will simply pop out all the operators from the stack until either the stack is empty or the stack top element has the lowest priority than the current operator. you have to save all the popped out elements in postfix expression.
If you encountered open brackets you can also insert that onto the
stack.
If you encountered a close bracket you just pop out all the operators, save them to postfix until you get an open bracket.
After parsing the infix expression if the stack isn't empty pop out all the operators from the stack and save them to postfix expression.
Algorithm to find POSTFIX of an INFIX expression
array.
last.
3 for next char otherwise, go to step 4.
go to step 3 for next char otherwise to step 5.
char is greater than that of stack top operator or stack is empty
otherwise, continue popping out elements from the stack and add them to
result until you got lower priority operator than that of char or the stack gets empty at last push char.
stack and add them to result until you got an open bracket(do not add an
open bracket to result just discard it).
stack and add them to the result.
