INfix expression to POSTfix

CONVERSIONS OF EXPRESSIONS: Arithmetic expressions can be represented in 3 ways.

1.    INFIX expression or notations A+B
2.    PREFIX expression or notations +AB
3.    POSTFIX expression or notations  AB+  

1)  INFIX  EXPRESSION OR NOTATION :If the operator is placed between the operand then it is called Infix expression or notation. They can be converted into postfix and prefix

PROCEDURE TO CONVERT INFIX TO POSTFIX:

STEP-1:  Add a unique symbol # into stack at the end of the array infix.

STEP-2: Scan the symbol of the array infix one by one left to right.

STEP-3: If the symbol is left parenthesis then add into the stack.

STEP-4: If the symbol is right parenthesis then pop all the operators from the stack.

STEP-5: If the symbol is operand then add into array postfix.

STEP-6: If the symbol is operator then pop the operators which have same precedencies or higher precedencies then the operators which occurred.

Add the popped operator to the array postfix

Add scanned symbol operator into stack.

STEP-7:  If the symbol is # then pop all the symbols from the stack and add them to array postfix except #.

STEP-8: Do the same process until # comes in the scanning array infix.

Infix to postfix conversion of the expression A-B*C+D/A/(E+F)

Symbol Scanned	Stack	POSTfix expression
A	#	A
-	#-	A
B	#-	AB
*	#-*	AB
C	#-*	ABC
+	#+	ABC*-
D	#+	ABC*-D
/	#+/	ABC*-D
A	#+/	ABC*-DA
/	#+/	ABC*-DA/
(	#+/(	ABC*-DA/
E	#+/(	ABC*-DA/E
+	#+/(+	ABC*-DA/E
F	#+/(+	ABC*-DA/EF
)	#+/	ABC*-DA/EF+
#		ABC*-DA/EF+/+

 

RESULT: POSTfix expression of the given infix is ABC*-DA/EF+/+

/* Java implementation to convert infix expression to postfix*/
// Note that here we use Stack class for Stack operations

import java.util.Stack;

class intopost
{
        // Driver method
    public static void main(String[] args)
    {
        String exp = "a+(b*c-(d/e*f)*g)";
        System.out.println(infixToPostfix(exp));
    }
    // A utility function to return precedence of a given operator
    // Higher returned value means higher precedence
    static int Prec(char ch)
    {
        switch (ch)
        {
        case '+':
        case '-':
            return 1;
   
        case '*':
        case '/':
            return 2;
   
        case '^':
            return 3;
        }
        return -1;
    }
   
    // The main method that converts given infix expression
    // to postfix expression.
    static String infixToPostfix(String exp)
    {
        // initializing empty String for result
        String result = new String("");
       
        // initializing empty stack
        Stack<Character> stack = new Stack<>();
       
        for (int i = 0; i<exp.length(); ++i)
        {
            char c = exp.charAt(i);
           
    // If the scanned character is an operand, add it to output.
            if (Character.isLetterOrDigit(c))
                result += c;
           
    // If the scanned character is an '(', push it to the stack.
            else if (c == '(')
                stack.push(c);
           
    // If the scanned character is an ')', pop and output from the stack
            // until an '(' is encountered.
            else if (c == ')')
            {
                while (!stack.isEmpty() && stack.peek() != '(')
                    result += stack.pop();
               
                if (!stack.isEmpty() && stack.peek() != '(')
                return "Invalid Expression";            
                else
                    stack.pop();
            }
            else // an operator is encountered
            {
            while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
                        {
                    if(stack.peek() == '(')
                        return "Invalid Expression";
                    result += stack.pop();
            }
                stack.push(c);
            }
   
        }
   
        // pop all the operators from the stack
        while (!stack.isEmpty())
                {
            if(stack.peek() == '(')
                return "Invalid Expression";
            result += stack.pop();
        }
        return result;
    }
   
}
output:

Interview Questions:

Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?
a) operand is always placed in the output
b) operator is placed in the stack when the stack operator has lower precedence
c) parenthesis are included in the output
d) higher and equal priority operators follow the same condition

Answer: c

In infix to postfix conversion algorithm, the operators are associated from?
a) right to left
b) left to right
c) centre to left

d) centre to right

Answer: b

What is the time complexity of an infix to postfix conversion algorithm?
a) O(N log N)
b) O(N)
c) O(N2)

d) O(M log N)

Answer: b

What is the value of the postfix expression 2 3 + 4 5 6 – – *
a) 19
b) 21
c) -4
d) 25

Answer: d

Explanation: Given postfix expression  2 3 + 4 5 6 - - *

Symbol            Stack           

2                         2

3                         2   3

+                         2+3

4                         5   4

5                         5    4     5

6                         5    4     5    6

-                          5    4     5-6

                           5     4     -1

-                          5      4-(-1)   

*                         5      5

                           5*5

                            25

Note: bottom of stack operand     operator     top of stack