package data_structure;

import java.util.Stack;

public class infixtoposfix
{
	static String InfixtoPostFix(char exp[])
	{
		StringBuilder builder=new StringBuilder();
		Stack<Character> stack=new Stack<>();

		for(int i=0;i<exp.length;i++)
		{
			if(Character.isDigit(exp[i]))
				builder.append(exp[i]);
			else if(isOperator(exp[i]))
			{
				while(!stack.isEmpty()&&hasHigherPrecedence(stack.peek(),exp[i])&&!hasOpeningParenthesis(stack.peek()))
				{
					builder.append(stack.pop());
				}

				stack.push(exp[i]);
			}
			else if(hasOpeningParenthesis(exp[i]))
			{
			    stack.push(exp[i]);
			}
			else if(hasClosingParenthesis(exp[i]))
			{
				while(!stack.isEmpty()&&!hasOpeningParenthesis(stack.peek()))
				{
					builder.append(stack.pop());
				}
				stack.pop();
			}
		}

		while(!stack.isEmpty())
		{
			builder.append(stack.pop());
		}

		return builder.toString();
	}

	private static boolean hasOpeningParenthesis(char oper)
	{
		return (oper=='('||oper=='{'||oper=='[');
	}

	private static boolean hasClosingParenthesis(char oper)
	{
		return (oper==')'||oper=='}'||oper==']');
	}



    private static boolean hasHigherPrecedence(char oper1,char oper2)
	{
			if(getPriorityIndex(oper1)>=getPriorityIndex(oper2))
				return true;
			else
				return false;
	}

	private static int getPriorityIndex(char opr)
	{
		if(opr=='*'||opr=='/')
			return 2;
		else if(opr=='+'||opr=='-')
			return 1;
		else
			return 0;
	}

	public static boolean isOperator(char ch)
	{
		return (ch=='+'||ch=='-'||ch=='*'||ch=='/');
	}

	public static void main(String args[])
	{
		String expression="(3+4)*2-2";
		String str=InfixtoPostFix(expression.toCharArray());
		System.out.println("The PostFix expression conversion is "+str);
	}
}