Question

(Convert infix to postfix)

Note:

• Postfix notation is a way of writing expression without using parentheses. For example, the expression ( 11 + 12 ) * 13 would be written as 11 12 + 13 *
• Assume that ALWAYS there is a space between operands and operators in the input expression.
• Use two stacks, one to store the operands and one to store the operators.
• Your program only accpets following operators :
  • ( )
  • +
  • -
  • /
  • *

Write a method to converts an infix expression into a postfix expression using the following method:

String infixToPostfix(String expression)

For example, the method should convert the infix expression

( 13 + 25 ) * 34 to 13 25 + 34 *

and

20 * ( 10 + 30 ) to 20 10 30 + *.

import java.util.*;
import java.lang.*;
import java.io.*;

class InfixToPostfix{
public String infixToPostfix(String expression) {
  
   }
}
class DriverMain{
   public static void main(String args[]){
Scanner input = new Scanner(System.in);
InfixToPostfix postfix = new InfixToPostfix();
try {
System.out.println(postfix.infixToPostfix(input.nextLine()));
}
catch (Exception ex) {
System.out.println("Wrong expression");
}
   }
}

Answer 1

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

import java.util.Stack; 

class Test 
{ 
        // 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"; // 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; 
        } 
        
        // Driver method 
        public static void main(String[] args) 
        { 
                String exp = "a+b*(c^d-e)^(f+g*h)-i"; 
                System.out.println(infixToPostfix(exp)); 
        } 
} 

Output:

abcd^e-fgh*+^*+i-