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)))");
    }
}