Question

In Java, write class InfixToPostfixConverter co convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers (to make things easier) such as

(6 + 2) • 5 - 8 / 4

to a postfix expression. The postfix version (no parentheses are needed) of this infix expression is

6 2 + 5 * 8 4 / -

The program should read the expression into StringBuilder or String infix and use the Stack and Stack Interface class (as found in Lesson 8 Programs Classwork) to help create the postfix expression in StringBuuider (or String) postfix. The algorithm for creating a postfix expression is shown below

Push a left parenthesis ' (' onto the stack.

Append a right parenthesis ') ' to the end of infix.

While the stack is not empty, read infix from left to right and do the following:

     If the current character in infix is a digit, append it to postfix.

     If the current character in infix is a left parenthesis, push it onto the stack.

     If the current character in infix is an operator:

            Pop operators (if there are any) at the top of the stack while they have equal or higher

precedence than the current operator, and append the popped operators to postfix.

     Push the current character in infix onto the stack.

     If the current character in infix is a right parenthesis:

            Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack.

            Pop (and discard) the left parenthesis from the stack.

The following arithmetic operations are allowed in an expression:

^ exponentiation

* multiplication

/ division

% remainder

+ addition

- subtraction

Exponents have the highest precedence, multiplication, division and remainder all share the next highest precedence, and addition and subtraction have the lowest precedence.

Some methods you may want to provide are as follows:

Method convertToPostfix, which accepts converts the infix expression to postfix notation by implementing the algorithm described above.

Method is0perator, which determines whether the input parameter c is an operator.

Method precedence, which determines whether the precedence of operator1 (from the infix expression) is less than, equal to or greater than that of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned. Precedence is as defined above.

You will need to use the Stack method peek to perform some of the checks as described above.

Two Sample outputs:

Please enter an infix expression:

(2^5)+(2/4^6)-7

The original infix expression is:

(2^5)+(2/4^6)-7

The expression in postfix notation is:

2 5 ^ 2 4 6 ^ / 7 - +

Please enter an infix expression:

((8*7-5)+2)

The original infix expression is:

((8*7-5)+2)

The expression in postfix notation is:

8 7 * 5 - 2 +

Answer 1

import java.util.*;

class Main{
    
    public static int precedence(char c){
        
        switch (c) {
            
            case '+' :
                return 0;
                
            case '-' :
                return 1;
                
            case '*' : 
            case '/' :
            case '%' :
                return 2;
                
            case '^' : 
                return 3;
            
        }
        
        return -1;
    }
    
    public static boolean isOperator(char c ){
        if(c=='+' || c=='-' || c=='/' || c=='*' || c=='^' || c=='%' )
            return true;
        else 
            return false;
    }
    
    
    public static String convertToPostfix(String exp){
        
         String result = new String(""); 
                 Stack<Character> stack = new Stack<>();         
        
        for (int i = 0; i<exp.length(); ++i) 
                { 
                        char c = exp.charAt(i); 

                        if (Character.isLetterOrDigit(c)) 
                                result += c; 
                        else if (c == '(') 
                                stack.push(c); 
                        else if (c == ')') 
                        { 
                                while (!stack.isEmpty() && stack.peek() != '(') 
                                        result += stack.pop(); 
                                
                                if (!stack.isEmpty() && stack.peek() != '(') 
                                        return "Invalid Expression";                     
                                else
                                        stack.pop(); 
                        } 
                        
                        if(isOperator(c)){
                            
                                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())){ 
                                        if(stack.peek() == '(') 
                                                return "Invalid Expression"; 
                                        result += stack.pop(); 
                           } 
                                stack.push(c); 
                        } 
        
                } 
        
                while (!stack.isEmpty()){ 
                        if(stack.peek() == '(') 
                                return "Invalid Expression"; 
                        result += stack.pop(); 
                } 
                return result; 
    }
    
    
    public static void main (String[] args) {
        
        Scanner sc=new Scanner(System.in);
        
        System.out.println("Please enter an infix expression:");
        String expression=sc.nextLine();
        
        System.out.println("The original infix expression is:");
        System.out.println(expression);
        
        String res=convertToPostfix(expression);
        System.out.println("The expression in postfix notation is:");
        System.out.println(res);
        
    }
    
}

If Precedence method is to be strictly should have return type boolean then replace following two method with Precedence method in above code .

public static int getPrecedence(char c){

 switch (c) {
            
            case '+' :
                return 0;
                
            case '-' :
                return 1;
                
            case '*' : 
            case '/' :
            case '%' :
                return 2;
                
            case '^' : 
                return 3;
            
        }
     return -1;
}

public boolean precedence(char ch1,char ch2){
 
  if(getPrecedence(ch1) <= getPrecedence(ch2))
       return true;
  else 
       return false;

}