INfix expression to PREfix

Infix notation : we write expression in infix notation, for example: a-b+c , where operators are used in between operands . It is easy for us humans to read, write, and speak in infix notation but the same does not do well with computing devices. An algorithm to process infix notation could be difficult and costly in items of time and space consumption.

Prefix notation : In this notation ,the operator is prefixed to operands i.e. operator is written ahead of operands . for example +ab. This is equivalent to its infix notation a+b. Prefix notation is also known as POLISH NOTATION.

Postfix notation : In this notation ,the operator is postfixed to the operands i.e., the operator is written after the operands . for example ab+. This is equivalent to its infix notation a+b . Postfix notation is also known as REVERSE POLISH NOTATION.

Conversion of an infix expression to its prefix form.

step 1: Consider the given INfix expression  

A^B*C-D+E/F(G+H)

step 2: Reverse the given INfix expression 

(H+G)F/E+D-C*B^A to POSTfix 

step 3: Reverse the obtained POSTfix expression and that expression is the PREfix expression 

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

Symbol Scanned	Stack	POSTfix expression
(	#(
H	#(	H
+	#(+	H
G	#(+	HG
)	#	HG+
F	#	HG+F
/	#/	HG+F
E	#/	HG+FE
+	#+	HG+FE/
D	#+	HG+FE/D
-	#+-	HG+FE/D
C	#+-	HG+FE/DC
*	#+-*	HG+FE/DC
B	#+-*	HG+FE/DCB
^	#+-*^	HG+FE/DCB
A	#+-*^	HG+FE/DCBA
#		HG+FE/DCBA^*-+

Reverse the obtained POSTfix expression and that expression is the PREfix expression +-*^ABCD/EF+GH

Program:

// Java program to convert infix to prefix. 

import java.util.*;
class intopre
{
//Driver code
  public static void main(String args[])
  {
    String s = "((a+b)^c-(d*e)/f)";
    System.out.println( infixToPrefix(s));
  }

 // Function to check if given character is an operator or not.
 static boolean isOperator(char c)
  {
    return (!(c >= 'a' && c <= 'z') && !(c >= '0' && c <= '9') &&             !(c >= 'A' && c <= 'Z')); 
  }

// Function to find priority of given operator.
static int getPriority(char C)
  {
    if (C == '-' || C == '+')
        return 1;
    else if (C == '*' || C == '/')
        return 2;
    else if (C == '^')
        return 3;
    return 0;
  }

// Function that converts infix expression to prefix expression.
static String infixToPrefix(String infix)
  {
    // stack for operators.
    Stack<Character> operators = new Stack<Character>();

    // stack for operands.
    Stack<String> operands = new Stack<String>();

    for (int i = 0; i < infix.length(); i++)
    {

        // If current character is an
        // opening bracket, then
        // push into the operators stack.
        if (infix.charAt(i) == '(')
        {
            operators.push(infix.charAt(i));
        }

        // If current character is a
        // closing bracket, then pop from
        // both stacks and push result
        // in operands stack until
        // matching opening bracket is
        // not found.
        else if (infix.charAt(i) == ')')
        {
            while (!operators.empty() &&
                operators.peek() != '(')
                {

                // operand 1
                String op1 = operands.peek();
                operands.pop();

                // operand 2
                String op2 = operands.peek();
                operands.pop();

                // operator
                char op = operators.peek();
                operators.pop();

                // Add operands and operator
                // in form operator +
                // operand1 + operand2.
                String tmp = op + op2 + op1;
                operands.push(tmp);
            }

            // Pop opening bracket
            // from stack.
            operators.pop();
        }

        // If current character is an
        // operand then push it into
        // operands stack.
        else if (!isOperator(infix.charAt(i)))
        {
            operands.push(infix.charAt(i) + "");
        }

        // If current character is an
        // operator, then push it into
        // operators stack after popping
        // high priority operators from
        // operators stack and pushing
        // result in operands stack.
        else
        {
            while (!operators.empty() &&
                getPriority(infix.charAt(i)) <=
                    getPriority(operators.peek()))
                {

                String op1 = operands.peek();
                operands.pop();

                String op2 = operands.peek();
                operands.pop();

                char op = operators.peek();
                operators.pop();

                String tmp = op + op2 + op1;
                operands.push(tmp);
            }

            operators.push(infix.charAt(i));
        }
    }

    // Pop operators from operators
    // stack until it is empty and
    // operation in add result of
    // each pop operands stack.
    while (!operators.empty())
    {
        String op1 = operands.peek();
        operands.pop();

        String op2 = operands.peek();
        operands.pop();

        char op = operators.peek();
        operators.pop();

        String tmp = op + op2 + op1;
        operands.push(tmp);
    }

    // Final prefix expression is
    // present in operands stack.
    return operands.peek();
   }
}

output:

Interview Questions

Out of the following operators (^, *, +, &, $), the one having highest priority is _________
a) +
b) $
c) ^
d) &

Answer: c

Out of the following operators (|, *, +, &, $), the one having lowest priority is ________
a) +
b) $
c) |
d) &

Answer: c

What would be the solution to the given prefix notation?

- + 5 / 10 5 5

a) 2
b) 5
c) 10
d) 7

Answer: a

Explanation: Reverse the given prefix expression  5 5 10 / 5 + -

Symbol            Stack           

5                        5

5                        5  5 

10                      5  5  10

/                         5   10/5

5                         5    2     5

+                         5    5+2

-                          5     7

                           7-5

                            2         

Note: top of stack operand     operator     bottom of stack 

What would be the solution to the given prefix notation?

- * 1 5 / * / 6 3 6 2

a) 1
b) 0
c) -1
d) -2

Answer:c

Explanation: Reverse the given prefix expression  2  6  3  6  / * / 5 1 * - 

Symbol            Stack    

2                      2

6                      2  6

3                      2  6  3

6                      2  6  3  6

/                       2   6  6/3

                         2   6  2

*                       2    2*6

                          2    12

/                         12/2

                           6

5                         6   5

1                         6    5    1

*                         6    1*5

                           6      5

-                          5-6

                            -1

Note: top of stack operand     operator     bottom of stack 

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