Tuesday 13 September 2016

Algorithm Infix to postfix conversation

Infix to Postfix Baner

Postfix expression evolution is task for computer not for human. We deal with infix expression in our daily life.  Where we take care about operator priority etc which untimely need some more consideration for solve an expression if computer will follow infix expression as calculation then it need more time for getting priority operation.

So postfix is a solution where all bracket are removed.  One advantage that postfix has over infix is that it is very easily implemented and does not have overhead of parentheses. Evaluating an expression in postfix notation requires scanning from left to right so you know what to do as soon as you encounter an operator in the expression string. Also, with postfix there is no complication of precedence of one operator over the other.
  1. Algorithm Infix to postfix conversation
  2. Get the infix expression string
  3. Make a table with three column named (Symbol,Stack,Output)
  4. Scan and remove each character from infix expression from left to right
  5. If character is operand write into output
  6. If character is operator push into stack with following rule
  7. If stack is not empty and upcoming operator is high or equal from top position operator then
  8. Pop stack and write into output then push upcoming character into stack
  9. If newly character priority is less than top position operator from stack then push
  10. If newly character is "(" then push all member operator before) with operator priority rule as mention in step 7   
  11. If newly character is ")" then pop all operator and write into output until ")" pop, leave the ")"
Example :

Z+(X+5)/y-(5+6)*2

Symbol
Stack
Output
Z

EMPTY
Z
+

+
Z
(
+(
Z
X
+(
ZX
+
+(+
ZX
5
+(+
ZX5
)
+
ZX5+
/
+/
ZX5+
Y
+/
ZX5+Y
-
-
ZX5+Y/+
(
-(
ZX5+Y/+
5
-(
ZX5+Y/+5
+
-(+
ZX5+Y/+5
6
-(+
ZX5+Y/+56
)
-
ZX5+Y/+56+
*
-*
ZX5+Y/+56+
2
-*
ZX5+Y/+56+2

-
ZX5+Y/+56+2*

-
ZX5+Y/+56+2*-

EMPTY
ZX5+Y/+56+2*-


No comments:

Post a Comment