package converter;
import java.util.Stack;
import java.util.Scanner;

public class converter
{
	// check priority the highest is the first
    static int Prec(char ch)
    {
        switch (ch)
        {
        case '+':
        case '-':
            return 1;

        case '*':
        case '/':
            return 2;

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

    // Converter method
    static String ToPostfix(String exp)
    {
        // empty string for result
        String result = new String("");

        // New stack
        Stack<Character> stack = new Stack<>();

        // for loop on the given exp string from main (char by char)
        for (int i = 0; i<exp.length(); ++i)
        {
            char c = exp.charAt(i);

             // is character?
            if (Character.isLetterOrDigit(c))
                result += c;

            // is ( ?
            else if (c == '(')
                stack.push(c);

            // is ) ?
            else if (c == ')')
            {
                // Pop everying inside () ... check everything not inside ()
                while (!stack.isEmpty() && stack.peek() != '(')
                    result += stack.pop();

                if (!stack.isEmpty() && stack.peek() != '(')
                    return "Invalid Expression";
                else
                    stack.pop();
            }
            // is * / + - ?
            else
            {
                // Priority
                while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){
                    if(stack.peek() == '(')
                        return "Invalid Expression";
                    result += stack.pop();
             }
                stack.push(c);
            }
        }

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


    public static void main(String[] args)
    {
        System.out.println("Type your Infix: ");

        Scanner s = new Scanner(System.in);
        String exp = s.next();

        System.out.println(ToPostfix(exp));
    }
}