INFIX TO POSTFIX

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.

Prefix notation:   In the case of preFix, the operator comes before its operands as

+ a b. this notation is also called Polish notation.

PostFix notation: 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.

From the above updated expression,  the next sub postfix part is 7 4 * so again do the same and replace it with its result.

-1 8 8 28 * + +

I have given all the steps below

step 1: 7 8 - 8 8 7 4 * * + + 

at the first step, we encountered an - sign with its operands 7 and 8. Replace this sub postfix exp with its result.

-1 8 8 7 4 * * + + 

step 2: -1 8 8 7 4 * * + + 

replace 7 4 * with 28.

and do the same, until you got your final result.

-1 8 8 28 * + +

step 3 : -1 8 8 28 * + +

-1 8 224 + +

step 4: -1 8 224 + +

-1 232 +

Result: 231 (final answer)

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	^

+,- has an equal priority but less than that of /, *. And ^ has the higher priority.

But how do we convert? 

easy pissy!

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

Required: var result, array char, and a stack s.

Step 1: take all characters in a sequence left to right into a char array.

step 2:  for each char do the following steps(3-6). Then go to last.

step 3:  If char is an operand, simply add it to result and repeat step 3 for next char otherwise, go to step 4.

step 4: If the char is an open bracket, simply push it on to the stack and go to step 3 for next char otherwise to step 5.

step 5: if char is an operator, push it onto the stack if the priority of 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.

step 6: if char is a close bracket then pop out all the elements from the stack and add them to result until you got an open bracket(do not add an open bracket to result just discard it).

Last (end): if the stack is not empty, pop out all the elements from the stack and add them to the result.

Other Recommended posts from this blog

Making a calculator project  in java [2020]