Add Postfix to Infix using Stack (fixes TheAlgorithms#2339) (TheAlgorithms#2970)

nikslyon19 · web-flow · commit 1ac1a5a6a5de · 2022-03-06T08:59:45.000+02:00
diff --git a/src/main/java/com/thealgorithms/datastructures/stacks/PostfixToInfix.java b/src/main/java/com/thealgorithms/datastructures/stacks/PostfixToInfix.java
@@ -0,0 +1,153 @@
+package com.thealgorithms.datastructures.stacks;
+
+import java.util.Stack;
+
+/**
+ * Postfix to Infix implementation via Stack
+ *
+ * Function: String getPostfixToInfix(String postfix)
+ * Returns the Infix Expression for the given postfix parameter.
+ *
+ * Avoid using parentheses/brackets/braces for the postfix string.
+ * Postfix Expressions don't require these.
+ *
+ *
+ * @author nikslyon19 (Nikhil Bisht)
+ *
+ */
+
+public class PostfixToInfix {
+
+
+    public static boolean isOperator(char token)
+    {
+        switch(token)
+        {
+            case '+':
+            case '-':
+            case '/':
+            case '*':
+            case '^':
+                return true;
+        }
+
+        return false;
+    }
+
+
+    public static boolean isValidPostfixExpression(String postfix)
+    {
+        /* Postfix expression length should NOT be less than 3 */
+        if(postfix.length() < 3) return false;
+
+
+        /* First two characters should NOT be operators */
+        if(isOperator(postfix.charAt(0))) return false;
+        if(isOperator(postfix.charAt(1))) return false;
+
+
+        int operandCount = 0;
+        int operatorCount = 0;
+
+
+        /* Traverse the postfix string to check if --> Number of operands = Number of operators + 1 */
+        for(int i = 0; i < postfix.length(); i++)
+        {
+            char token = postfix.charAt(i);
+
+            if(isOperator(token))
+            {
+                operatorCount++;
+                if(operatorCount >= operandCount) return false;
+            }
+
+            else
+            {
+                if(operatorCount == 0)
+                {
+                    operandCount++;
+                    continue;
+                }
+
+                if(operandCount != operatorCount + 1) return false;
+
+
+                /* Operand count is set to 2 because:-
+                 *
+                 * 1) the previous set of operands & operators combined have become a single valid expression,
+                 * which could be considered/assigned as a single operand.
+                 *
+                 * 2) the operand in the current iteration.
+                 */
+                operandCount = 2;
+
+
+                /* Reset operator count */
+                operatorCount = 0;
+            }
+        }
+
+        return (operandCount == operatorCount + 1);
+    }
+
+
+    public static String getPostfixToInfix(String postfix)
+    {
+        String infix = "";
+
+        if(postfix.isEmpty()) return infix;
+
+
+        /* Validate Postfix expression before proceeding with the Infix conversion */
+        if(!isValidPostfixExpression(postfix))
+        {
+            throw new IllegalArgumentException("Invalid Postfix Expression");
+        }
+
+        Stack<String> stack = new Stack<>();
+        StringBuilder valueString = new StringBuilder();
+
+        String operandA, operandB;
+        char operator;
+
+
+        for(int index = 0; index < postfix.length(); index++)
+        {
+            char token = postfix.charAt(index);
+
+            if(!isOperator(token))
+            {
+                stack.push(Character.toString(token));
+                continue;
+            }
+
+            operator = token;
+            operandB = stack.pop();
+            operandA = stack.pop();
+
+            valueString.append('(');
+
+            valueString.append(operandA);
+            valueString.append(operator);
+            valueString.append(operandB);
+
+            valueString.append(')');
+
+            stack.push(valueString.toString());
+            valueString.setLength(0);
+        }
+
+        infix = stack.pop();
+        return infix;
+    }
+
+
+    public static void main(String args[])
+    {
+        assert getPostfixToInfix("ABC+/").equals("(A/(B+C))");
+        assert getPostfixToInfix("AB+CD+*").equals("((A+B)*(C+D))");
+        assert getPostfixToInfix("AB+C+D+").equals("(((A+B)+C)+D)");
+        assert getPostfixToInfix("ABCDE^*/-").equals("(A-(B/(C*(D^E))))");
+        assert getPostfixToInfix("AB+CD^/E*FGH+-^").equals("((((A+B)/(C^D))*E)^(F-(G+H)))");
+    }
+}
