Question

Java Program to Fully Parenthesize an expression.

Hi guys.

I have a small task which I cannot find the solution for. It involves expressions with Infix I'll need a Java Program to convert an expression,

eg. 3+6*(x-y)+x^2

to

((3 + (6 * (x-y))) + (x ^ 2))

Kindly assist. Thanks

Answer 1

Approach:

We will first convert all the expressions to postfix to normalize all the input expressions and then convert all the valid postfix expression back to full parenthesized expression.

CODE:

import java.util.Stack;

public class InfixPostfix {

   static boolean checkIfOperand(char x) {
       return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z') || (x >= 48 && x <= 57);
   }

   // Function to convert postfix expression into fully parenthesized infix
   // expression
   static String getInfix(String exprsn) {
       // create stack of string
       Stack<String> s = new Stack<String>();
       // iterate and add parenthesis to correct operand pair
       for (int i = 0; i < exprsn.length(); i++) {
           // check for operands and push to stack
           if (checkIfOperand(exprsn.charAt(i))) {
               s.push(exprsn.charAt(i) + "");
           } else {
               String op1 = s.peek();
               s.pop();
               String op2 = s.peek();
               s.pop();
               s.push("(" + op2 + exprsn.charAt(i) + op1 + ")");
           }
       }
       return s.peek();
   }

   // supporting function to determine the priority of operator
   static int priorityChecker(char ch) {
       switch (ch) {
       case '+':
       case '-':
           return 1;
       case '*':
       case '/':
           return 2;

       case '^':
           return 3;
       }
       return -1;
   }

   // Function that converts given infix expression
   static String infixToPostfixParser(String exprsn) {
       // initialize result string
       String result = "";
       // initialize empty stack of chars
       Stack<Character> stack = new Stack<>();

       for (int i = 0; i < exprsn.length(); ++i) {
           char c = exprsn.charAt(i);
           // If char is an operand, add it to result.
           if (Character.isLetterOrDigit(c))
               result += c;
           // If char is an '(', push it to the stack.
           else if (c == '(')
               stack.push(c);
           // If char is an ')', pop and result from the stack until an '(' is found.
           else if (c == ')') {
               while (!stack.isEmpty() && stack.peek() != '(')
                   result += stack.pop();

               if (!stack.isEmpty() && stack.peek() != '(')
                   return "Expression is Invalid";
               else
                   stack.pop();
           }
           // if operator is encountered
           else {
               // perform priority comparison of an operator
               while (!stack.isEmpty() && priorityChecker(c) <= priorityChecker(stack.peek())) {
                   if (stack.peek() == '(')
                       return "Expression is Invalid";
                   result += stack.pop();
               }
               stack.push(c);
           }

       }

       // pop all the operators from the stack
       while (!stack.isEmpty()) {
           if (stack.peek() == '(')
               return "Expression is Invalid";
           result += stack.pop();
       }
       return result;
   }

   // Driver code for calling post fix and infix conversion methods
   public static void main(String[] args) {
       // sample expression which is to be fully parenthesised
       String exprsn = "3+6*(x-y)+x^2";
       // Convert the given expression to postfix expression.
       String postFixExp = infixToPostfixParser(exprsn);

       // check if postfix expression is valid and not empty
       if (postFixExp != null && postFixExp.isEmpty() == false && postFixExp.toLowerCase()!="expression is invalid")
           System.out.println(getInfix(postFixExp));
       else
           System.out.println(
                   "Some error occurred during postfix conversion, please validate your expression and try again");

   }

}

RESULT: