Problem $2$: Infix to Prefix Conversion

Infix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form $($operand$1$ operator operand$2).$

Example : $(A+B)**(C-D)$

Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form $($operator operand$1$ operand$2).$

Example : $*+$AB$-$CD $($Infix : $(A+B)**(C-D))$

Write a program that converts an infix $($fully parenthesized$)$ expression to a prefix expression. The program will have to handle only the binary operators $+,-,{?}^{**}\frac{,}{,{?}^{?}}.$ parenthesis, letters and numbers.

An example would be an expression like: $(\frac{(A^{**}(B))+(2^{**}(C^3))}{2**(A)}).$

The program must convert this expression $($infix$)$ to the prefix expression: $\frac{?}{?}+{?}^{**}A{B}^{**}{2}^{{?}^{?}}{?}^2$A All expressions of the test cases are expressions with valid syntax.

You are given a InfixtoPrefix.java file fill in your code in that file.

Hint: Use two stacks, one for operators and another for operands $($you can use the Java built$-$in stack$).$

Input

Read input from a file $"$in$1.$txt$".$ Each input is a valid fully parenthesized expression in the infix notation.

Output

For each test case, print the expression converted to prefix expression.

$\backslash$table$[[$Input Sample,Output Sample$],[(A^{**}2),*$A$2],[($:$\frac{((A^{**}2)+c)-d}{2}\},\frac{?}{?}-+{?}^{**}A2cd2$