Polish Notations (Infix,Prefix,Postfix)
There are basically three types of polish notation:
(A) Infix: When the operator is written between two operands then it is known as Infix notation. For example A+B
(B) Prefix: When the operator is written before their operands then it is known as Prefix notation. For example +AB
(C) Postfix: When the operator is written after their operands then it is known as Postfix notation. For example AB+
Conversion of Infix Expression into Postfix Expression
Before understanding the conversion process of Infix expression into Postfix expression we must know the precedence of each operator.
Following are the precedence of each operator from highest to lowest.
Generally we use infix notation in arithmetic expression. In order to convert an expression from infix notation to postfix notation follows the steps given below:
(1) Initialize an empty stack.
(2) Scan infix string from left to right.
(3) If scanned character is an operand then append it into postfix string.
(4) If scanned character is left parenthesis “(“then PUSH it into stack.
(5) If scanned character is an operator and stack is either empty or contains “(“at topmost element then PUSH it into stack.
(6) If scanned character is right parenthesis “)” then POP all the operators from stack until “(“is encountered in the stack. Do not append parenthesis into postfix string.
(7) If scanned character is an operator and top of the stack also contains an operator then we have to compare the precedence of operators as follow:
(a) If precedence of scanned operator is less then or equal to the precedence of topmost operator in the stack then POP that operator from stack and append it into postfix string and PUSH scanned operator into stack.
(b) If precedence of scanned operator is greater then the precedence of topmost operator in the stack then PUSH scanned operator into stack.
(8) Repeat step7 until “(“is encountered into stack or stack becomes empty.
(9) When all the characters are scanned from infix string, POP remaining characters from stack and append it into postfix string.
Infix String: (a + b) * (c + d)
|Scanned Character||Content of Stack||Postfix String|